索引是检索图书资料的一种工具，把书刊中的内容或项目分类摘录，注明页数，按一定次序排列。

针对不同的数据存储结构有不同的数据查找方式。

1. 数据结构

1.1 B树

B树又名平衡多路查找树，主要用于文件系统中，在B树中，每个结点的大小为一个磁盘页，结点中所包含的关键字及其孩子的数目取决于页的大小。

image.png

对于一颗度为m的B树，需要满足：

1. 根结点或叶子结点，至少有2颗子树，至多有m颗。
2. 非叶子结点至少有 m/2颗子树，至多有m颗。
3. 所有叶子结点都在同一层。
4. 每个结点都要包含（n，Ao，K1，A1，K2，A2，K3，A3，Kn，An）
5. n是结点中关键字的个数，且 (m/2)-1 ≤ n ≤m-1，n+1为子树的棵数
6. Ai(i=0，1，…，n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki ，Ai所指向的子树中所有结点的关键字都大于Ki
7. Ki(1≤i≤n)是关键字，且Ki<Ki+1 (1≤i≤n-1)

B树使用二分查找，包含两个基本操作：

1. 在B树上查找结点：遍历整个树。
2. 在结点中查找关键字：每个结点中包含m个关键字，通过二分查找查询目标关键字。

B树上关键字的增加和删除通过平衡算法达到平衡。

1.2 B+树

B+树是B树的变体，在实际的文件系统中基本上不使用B树。B+树和B树的差异点：

1. 若一个结点有n棵子树，则必含有n个关键字；
2. 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接；
3. 所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。

image.png

B+树的非叶子结点不保存数据记录的指针信息，这意味着深度相同时B+树比B树的关键字更多。

2.InnoDB索引类型

2.1 B+树索引

InnoDB中的主键索引和辅助索引都是采用B+树。

image.png

B树的每个结点大小和磁盘页一致，磁盘每个页有4k，根据这个我们就可以计算出索引的深度。假设是一颗完全的m阶B+树，m的大小取决于非叶子结点存储关键字的数量，主键一般都是BIGINT 占8个字节，那么m=4*1024/8=512。

辅助索引的关键字按索引创建时定义列的顺序来的，如：status + create_time，10 2020-8-1

image.png

B+树结点中的关键字都是按顺序组织的，所以关键字的长度和类型决定了索引的性能：

1. 关键字越短，B+树的结点就越多，树的深度也会在预期内。
2. 关键字值分布的越均匀（重复少），B+树就越平衡。
3. 数字比字符串要快，因为字符串需要先做转换再做排序：字符串排序算法。

在某些特殊场景关键字的值不需要均匀，如：status字段有 1、2这两个值，1 -> 100条数据，2 -> 100万条数据，业务上只需要查询status为1的记录就会非常快，否则需要扫全表。

了解InnoDB索引的查找方法有助于我们创建高效的索引：

1. 全值匹配：比较完整的关键字。
2. 匹配最左前缀：只和索引定义的第一列进行匹配。
3. 匹配列前缀：只匹配第一列并且匹配关键字的前缀而非全值匹配。
4. 匹配范围值：匹配两个关键字之间的值。（在B树中关键字是顺序组织的，只要查询到当前关键字的父结点就能直接确认范围）
5. 只访问索引：不会查询数据行，像count这种操作就不需要再去查具体的行。

2.2 哈希索引

InnoDB中的哈希函数使用除留余数法，冲突采用链地址法。

2.3 自适应哈希索引

哈希是一种非常快的查找方法，时间复杂度为O(1)，即只需要查询一次就能定位数据，而B+树的查找次数取决于树的高度。InnoDB存储引擎会监控对表上各索引页的查询。如果观察到建立哈希 索引可以带来速度提升，则建立哈希索引，称之为自适应哈希索引 (Adaptive Hash Index，AHI)。AHI是通过缓冲池的B+树页构造而来，因此建立的速度很快，而且不需要对整张表构建哈希索引。InnoDB存储引擎会自动根据访问的频率和模式来自动地为某些热点页 建立哈希索引。

AHI有一个要求，即对这个页的连续访问模式必须是一样的。例如对 于(a，b)这样的联合索引页，其访问模式可以是以下情况。

模式：

• WHERE a=xxx
• WHERE a=xxx and b=xxx

条件：

• 以该模式访问了100次
• 页通过该模式访问了N次，其中N=页中记录*1/16

自适应hash索引是mysql的功能，开发者并不能控制，尽管如此还是要尽可能的利用，如果性能无法满足再选择缓存中间件。

参考：

• Mysql官方文档
• 《Mysql及时内幕 InnoDB存储引擎》
• https://blog.csdn.net/voidccc/article/details/40077329
• Jeremy Cole The physical structure of InnoDB index pages
• Jeremy Cole B+Tree index structures in InnoDB
• Jeremy Cole The physical structure of records in InnoDB