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

针对不同的数据存储构造有不同的数据查找形式。

1. 数据结构

1.1 B树

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

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

  1. 根结点或叶子结点，至多有2颗子树，至少有m颗。
  2. 非叶子结点至多有 m/2颗子树，至少有m颗。
  3. 所有叶子结点都在同一层。

  4. 每个结点都要蕴含（n，Ao，K1，A1，K2，A2，K3，A3，Kn，An）

    1. n是结点中关键字的个数，且 (m/2)-1 ≤ n ≤m-1，n+1为子树的棵数
    2. Ai(i=0，1，…，n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki ，Ai所指向的子树中所有结点的关键字都大于Ki
    3. 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. 所有的非叶子结点能够看成是索引的局部，结点中只含有其子树的根结点中的最大(或最小)关键字。

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

2.InnoDB索引类型

2.1 B+树索引

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

B树的每个结点大小和磁盘页统一，磁盘每个页有4k，依据这个咱们就能够计算出索引的深度。假如是一颗齐全的m阶B+树，m的大小取决于非叶子结点存储关键字的数量，主键个别都是BIGINT 占8个字节，那么m=4*1024/8=512。

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

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