MySQL索引结构

mysql的查询速度主要看磁盘io的时间，所以需要尽可能的减少磁盘io的次数，这也是为什么会选用数才作为存储结构的原因O(logN)

MySQL内置的存储引擎对各种索引技术有不同的实现方式，包括：B+Tree，R-Tree索引、hash索引、full-text全文索引

Innodb中使用的是B+Tree索引，并不是找到一个给定键值的具体行，而是找到被查找的数据行所在的页，然后通过把页读入到内存，在内存中进行查找，最后得到要查找的数据
MyISAM中使用的是FullText全文索引， InnoDB在5.6之后支持，5.7之后使用ngram插件开始支持中文
Memory中使用的是Hash索引

索引结构

为什么不使用二叉树

二叉树可能会出现链表的方式存储，这样磁盘IO次数就变成了O(N)

为什么不使用红黑树

红黑树确实可以保证O(logN)的次数，但是其只有两个子节点，数据大的话树的深度太高了

为了减少深度，采用了B树，B树可以有N个孩子节点

B-Tree

B-Tree的结构

B-Tree中有两种节点类型：索引节点和叶子节点。叶子节点是用来存储数据的，而索引节点则用来告诉用户存储在叶子节点中的数据顺序，并帮助用户找到相应的数据。

B-Tree的搜索，从根节点开始，对节点内的关键字有序进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点，重复。直到所对应的子指针为空，或已经是叶子节点

无法处理范围查询，只能定位到一个索引位置

B-Tree是一种多路搜索树：

定义任意非叶子节点最多有M个儿子，且M>2
根节点的儿子数为[2,M]
除根节点以外的非叶子节点的儿子数为[M/2,M]
每个节点存放至少M/2-1(取上整)和至多M-1个关键字
非叶子节点的关键字个数=指向儿子节点的指针的个数-1
非叶子节点的关键字：k[i]<k[i+1]
非叶子节点的指针：p[1]，p[2]，·····，p[M]；其中p[1]指向的关键字小于k[1]的子树，p[M]指向的关键字大于K[m-1]的子树
所有的叶子节点位于同一层

B+Tree

在平时使用的Innodb存储引擎中创建的BTREE索引，就是B+Tree的结构

B+树索引分为聚集索引（clustered index)和非聚集索引（secondary index)，这两种索引的共同点是内部都是B+树，高度都是平衡的，叶节点存放着所有数据。不同点是叶节点是否存放着一整行数据

加载时是以页为基本单位的，每次加载一页或多页，InnoDB的pageSize可以通过命令show variables like 'innodb_page_size'得到，默认值是16k

存储方式

聚簇索引

Innodb存储引擎表是索引组织表，即表中数据按主键顺序存放，而聚集索引就是按每张表的主键构造一棵B+树。并且叶节点存放整张表的行记录数据，每张表只能有一个聚簇索引（一个主键），对于聚簇索引，叶子结点即存储了真实的数据行，索引和数据在一起存储，不再有另外单独的数据页，聚簇索引的另一个好处是它对于主键的排序查找和范围的速度非常快，叶节点的数据就是我们要找的数据，聚簇索引也被称为主键索引

非聚簇索引

表数据存储顺序与索引顺序无关。对于非聚簇索引，叶结点包含索引字段值以及主键索引值，并不包含数据，该层紧邻数据页，其行数量与数据表行数据量一致
非聚簇索引的存在并不影响数据在聚簇索引中的组织，因此一个表可以有多个非聚簇索引。当通过非聚簇索引查找数据时，innodb会遍历非聚簇索引并通过叶级别的指针获得指向主键索引的主键。然后再通过主键索引找到一行完整的数据

非聚簇索引的叶子节点内容是主键的值，也被称为二级索引或非主键索引

也就是说会先根据非主键索引扫描一棵索引树，得到id的值之后，再根据id的索引树搜索一次，这个过程称为回表；如果查询的数据只需要id和索引字段，则不需要回表操作，直接从当前索引中获取值返回，这个操作叫做索引覆盖

B+树的结构

B+树是有序数组链表+平衡多叉树

相对Hash索引，B+Tree在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以它更受欢迎

B+树的所有索引数据都在叶子节点上，并且增加了顺序访问指针(双向链表)，每个叶子节点都有指向相邻叶子节点的指针，这样可以提高区间效率，当进行范围查找时，如查找key为10到20之间的数据，找到10之后就可以顺着节点和指针顺序遍历查找此范围的所有数据节点

B+树索引分裂

Innodb存储引擎的Page Header中有PAGE_LAST_INSERT、PAGE_DIRECTION、PAGE_N_DIRECTION三个字段来存储插入的顺序信息，通过这些信息Innodb可以决定是向左分裂还是向右分裂

为什么不使用B树做索引呢？

先来看一下B树和B+树的区别

B树

每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为nul，叶子结点不包含任何关键字信息

B+树

所有的叶子结点中包含了全部关键字的信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接，所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字

B+树数据结构是B-树实现的增强版本，尽管B+树支持B-树索引的所有特性，它们之间最显著的不同点在于B+树中底层数据是根据被提及的索引列进行排序的，B+树还通过叶子节点之间的附加引用来优化扫描性能。

B+搜索和B-搜索不同，区别是B+树只有达到叶子节点才命中（B-树可以在非叶子节点命中），其性能等价于关键字全集做一次二分搜索。

B+树的特性：

所有关键字都出现在叶子节点中，且以链表形式关联，叶子节点相当于存储数据的数据层
不可能在非叶子节点上命中
非叶子节点相当于是叶子节点的索引，叶子节点相当于数据层
叶子节点的值是有序的

根据两种结构的特性可以看到，与B树相比，B+树的数据全部都在叶子节点中，非叶子节点不保存数据，非叶子节点占用的内容更少，同样大小的文件可以存放更多的非叶子节点，MySql 将数据按照页来存储，默认一页为 16kb，在查询时，将这个数据所在的页都加载到 pageCache 中，这样每页可以取到的索引数据就多，在查找时IO次数会相对较少；而且在叶子节点之间又存在指针，在进行范围查找时也可以很快的将数据节点取到

总结一下分为两点

非叶子节点不存储数据，每页可存储的非叶子节点更多，减少了磁盘io
叶子节点之间存在指针，可以范围查询

B+树索引并不能找到一个给定键值的具体行，它找到的只是被查找数据行所在的页，接着数据库会把页读入到内存，再在内存中进行查找，最后得到要查找的数据

使用B+树访问或者修改一条数据的 SQL 的时间复杂度都是O(log n)，也就是树的高度

操作系统中页是一个逻辑单位，由于局部性原理，一页的数据是4K，这样可以减少磁盘IO

hash索引

hash索引是基于哈希表实现的，只有精确匹配索引所有列的查询才有效

在默认MySQL的引擎索引中，只有MEMORY引擎支持散列数据结构，散列结构的强度可以表示为直接键查找的简单性，散列索引的相似度模式匹配查询比直接查询慢，Hash索引把数据以hash形式组织起来，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可,是无序的，因此当查找某一条记录的时候，速度非常快。但是因为hash结构，每个键只对应一个值，而且是散列的方式分布。所以它并不支持范围查找和排序等功能

如果出现hash碰撞，则使用链地址法进行解决的，使用链表进行存储

不支持范围查询，只支持等值查询
无法避免数据的排序操作
不支持部分索引列的匹配查找，因为hash索引始终使用索引列的全部内容进行计算哈希值
当出现hash冲突时，必须遍历链表

在Innodb中存在一个自适应哈希索引功能，如果某些索引值使用的非常频繁的话，会在内存中基于B-Tree索引之上在创建一个哈希索引

散列表结构

散列表数据结构是一种很简单的概念，它将一种算法应用到给定值中以在底层数据存储系统中返回一个唯一的指针或位置。散列表的优点是始终以线性时间复杂度找到需要读取的行的位置，而不像B-树那样需要横跨多层节点来确定位置

R-Tree

R-Tree称为空间数据索引，可以用做地理数据存储，数据结构支持基于数据类型对几何数据进行管理。目前只有MyISAM使用R-树实现支持空间索引，使用空间索引也有很多限制，比如只支持唯一的NOT NULL列等

全文索引

全文本结构也是一种MySQL采用的基本数据结构，只能添加在 char, varchar, text类型的字段，查询字段较大的字符串类型的字段时可以提高速率，查找的是文本中的关键词，而不是直接比较索引中的值

主键的设计

MySql 的主键不能太大，如果使用 UUID 这种，将会浪费 B+ 树的非叶子节点。
MySql 的主键最好是自增的，如果使用 UUID 这种，每次插入都会调整 B+树，从而导致页分裂，严重影响性能