原文地址：https://blog.csdn.net/bruce_6/article/details/84938307
用过 MySQL 的应该都知道索引是干啥的吧，应该多少都设置过索引，但是若是问你索引是怎么实现的，你能说上来吗？

索引是什么？

MySQL 官方对索引的定义为：索引是帮助 MySQL 高效获取数据的数据结构。

在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
索引的出现就是为了提高查询效率，就像书的目录。其实说白了，索引要解决的就是查询问题。
查询，是数据库所提供的一个重要功能，我们都想尽可能快的获取到目标数据，因此就需要优化数据库的查询算法，选择合适的查询模型来实现索引。
另外，为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间，因为索引也要随之变动。

常见查询模型

索引的实现模型有很多，这里我们先了解一下常用的查询模型。

顺序数组

顺序数组是一种特殊的数组，里面的元素，按一定的顺序排列。
顺序数组在查询上有着一定的优势，因为是有序的数据，采用二分查找的话，时间复杂度是 O(log(N))。

顺序数组的优点就是查询效率非常高，但是要更新数据的话，就非常麻烦了。删除和插入元素都要涉及到大量元素位置的移动，成本很高。
因此，对于顺序数组更适合用于查询的领域，适合存储一些改动较小的静态存储引擎。

哈希索引

哈希表是一种以 键-值（key-value） 存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 value。
哈希索引采用一定的哈希算法，对于每一行，存储引擎计算出了被索引字段的哈希码（Hash Code），把哈希码保存在索引中，并且保存了一个指向哈希表中的每一行的指针。
这样在检索时只需一次哈希算法即可立刻定位到相应的位置，速度非常快。
Hash 索引结构的特殊性，其检索效率非常之高，应该是 O(1) 的时间复杂度。

虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些：
1、Hash索引仅仅能满足 =，IN 和 <=> 查询，如果是范围查询检索，这时候哈希索引就毫无用武之地了。
因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；
2、Hash 索引无法利用索引完成排序，因为存放的时候是经过 Hash 计算过的，计算的 Hash 值和原始数据不一定相等，所以无法排序；
3、联合索引中，Hash 索引不能利用部分索引键查询。
Hash 索引在计算 Hash 值的时候是联合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值。
所以对于联合索引中的多个列，Hash 是要么全部使用，要么全部不使用。通过前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
4、Hash索引在任何时候都不能避免表扫描。
前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键可能存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
5、在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。
综上，哈希表这种结构适用于只有等值查询的场景，比如 Memcached、redis 及其他一些 NoSQL 引擎。

二叉搜索树索引

二叉搜索树的每个节点都只存储一个键值，并且左子树（如果有）所有节点的值都要小于根节点的值，右子树（如果有）所有节点的值都要大于根节点的值。
当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时（平衡），这时树的搜索性能逼近二分查找；并且它比连续内存空间的二分查找更有优势的是，改变树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。
特殊情况下，根节点的左右子树的高度相差不超过 1 时，这样的二叉树被称为平衡二叉树；与之相对的是，二叉搜索树有可能退化成线性树。

下图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。

为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。

B树

看得出来，二叉树在查询和修改上做到了一个平衡，都有着不错的效率，但是现实是很少有数据库引擎使用二叉树来实现索引，为什么呢？
数据库存储大多不适用二叉树，数据量较大时，树高会过高。
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20，每个叶子结点就是一个块，每个块包含两个数据，块之间通过链式方式链接。

树高 20 的话，就要遍历 20 个块才能得到目标数据，索引存储在磁盘时，这将是非常耗时的。
因此，为了减少磁盘的读取，查询时就要尽量少的遍历数据块，因此一般使用 N 叉树。

---

这里就有了 B树（Balanced Tree）。

究竟什么是 B 树？

我们先看一个例子：

从上图你能轻易的看到，一个内结点 x 若含有 n[x] 个关键字，那么 x 将含有 n[x]+1 个子女。如含有 2 个关键字 D H 的内结点有 3 个子女，而含有 3 个关键字 Q T X 的内结点有 4 个子女。

B 树的特性

普及一些概念：

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；

首先定义两个变量：d 为大于 1 的一个正整数，称为 B 树的度。h 为一个正整数，称为 B 树的高度。
B 树是满足下列条件的数据结构：
1、每个非叶子节点由 n-1 个 key 和 n 个指针组成，其中 d<=n<=2d。
2、每个叶子节点最少包含一个 key 和两个指针，最多包含 2d-1 个 key 和 2d 个指针，叶节点的指针均为 null 。
3、除根结点和叶子结点外，其它每个结点至少有 [ceil(m / 2)] 个孩子（其中 ceil(x) 是一个取上限的函数）；
4、所有叶节点具有相同的深度，等于树高 h，且叶子结点不包含任何关键字信息。
5、key 和指针互相间隔，节点两端是指针。
6、一个节点中的 key 从左到右非递减排列。
7、每个指针要么为 null，要么指向另外一个节点。
8、每个非终端结点中包含有 n 个关键字信息： (n，P0，K1，P1，K2，P2，…，Kn，Pn)。
其中：
a) Ki (i=1…n) 为关键字，且关键字按顺序升序排序 K(i-1)< Ki。
b) Pi 为指向子树根的接点，且指针 P(i-1) 指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)。
c) 关键字的个数 n 必须满足： [ceil(m / 2)-1]<= n <= m-1。

B 树查找过程

由于 B 树的特性，在 B 树中按 key 检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的 data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到 null 指针，前者查找成功，后者查找失败。

如上图所示，我们来模拟下查找文件 29 的过程：
1、根据根结点指针找到文件目录的根磁盘块 1，将其中的信息导入内存。【磁盘 IO 操作 1 次】
2、此时内存中有两个文件名 17、35 和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针 p2；
3、根据 p2 指针，我们定位到磁盘块 3，并将其中的信息导入内存。【磁盘 IO 操作 20次】
4、此时内存中有两个文件名 26，30 和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针 p2；
5、根据 p2 指针，我们定位到磁盘块 8，并将其中的信息导入内存。【磁盘 IO 操作 3 次】；
6、此时内存中有两个文件名 28，29。根据算法我们查找到文件名 29，并定位了该文件内存的磁盘地址。
分析上面的过程，发现需要 3 次磁盘 IO 操作和 3 次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。

B+ 树

B+ 树：是应文件系统所需而产生的一种 B 树的变形树。
一棵 m 阶的 B+ 树和 m 阶的 B 树的异同点在于：
1、每个节点的指针上限为 2d 而不是2d+1。
2、所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。（B 树的叶子节点并没有包括全部需要查找的信息）
3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字，不存储 data。（B 树的非终节点也包含需要查找的有效信息。

为什么说 B+ 树比 B 树更适合做数据库索引？

1）B+ 树的磁盘读写代价更低
B+ 树的内部结点并没有存储关键字具体信息。因此其内部结点相对 B 树更小。
如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了。
2）B+ 树的查询效率更加稳定
由于非终端结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，进而每一个数据的查询效率相当。

几种树的对比

以上，为了介绍索引内容，我们花费了大量的篇幅介绍了几种数据结构模型，特别是树的相关概念。
另外，涉及到树的添加和删除元素，操作更加复杂，本文篇幅有限（其实是小编也搞不太明白），这里就不再展开。
有兴趣的，强烈建议钻研下参考链接里的内容。
好了，下面我们来看 MySQL 中的 InnoDB 引擎的索引是如何实现的。

MySQL 的索引模型

说了这么多，终于到索引出场了。
索引就是这种神奇伟大的存在。索引相当于数据库的表数据之外新建的数据结构，该数据结构的数据段中存储着字段的值以及指向实际数据记录的指针。
数据库表的索引从数据存储方式上可以分为聚簇索引和非聚簇索引（又叫二级索引）两种。

1、聚簇索引

表数据按照索引的顺序来存储的，也就是说索引项的顺序与表中记录的物理顺序一致。
对于聚簇索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。 在一张表上最多只能创建一个聚集索引，因为真实数据的物理顺序只能有一种。
聚簇集是指实际的数据行和相关的键值都保存在一起。
注意：数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。
如果主键不是自增 id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。
聚簇索引的二级索引：叶子节点不会保存引用的行的物理位置,而是保存了行的主键值

2、非聚集索引

表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。
聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。一般情况下主键会默认创建聚簇索引，且一张表只允许存在一个聚簇索引。
这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。
下面，我们可以看一下 MYSQL 中 MyISAM 和 InnoDB 两种引擎的索引结构。

MyISAM索引实现

MyISAM 引擎使用 B+ 树作为索引结构，叶节点的 data 域存放的是数据记录的地址，就是非聚集索引。
下图是 MyISAM 索引的原理图：


在 MyISAM 中，主键索引和辅助索引（Secondary key）在结构上没有任何区别，只是主键索引要求 key 是唯一的，而辅助索引的 key 可以重复。

InnoDB索引实现

虽然 InnoDB 也使用 B+ 树作为索引结构，但具体实现方式却与 MyISAM 截然不同。
第一个重大区别是 InnoDB 的数据文件本身就是索引文件。
在 InnoDB 中，表数据文件本身就是按 B+ 树组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。
另外，第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。
对于聚簇索引存储来说，行数据和主键 B+ 树存储在一起，辅助索引只存储辅助键和主键，主键和非主键 B+ 树几乎是两种类型的树。
对于非聚簇索引存储来说，主键 B+ 树在叶子节点存储指向真正数据行的指针，而非主键。
为了更形象说明这两种索引的区别，我们假想一个表如下图存储了 4 行数据。其中 Id 作为主索引，Name 作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。


对于聚簇索引，若使用主键索引进行查询，where id = 14 这样的条件查找主键，则按照 B+ 树的检索算法即可查找到对应的叶节点，之后获得行数据。
若使用辅助索引进行查询，对 Name 列进行条件搜索，则需要两个步骤：
1、第一步在辅助索引 B+ 树中检索 Name，到达其叶子节点获取对应的主键。
2、第二步根据主键在主索引 B+ 树种再执行一次 B+ 树检索操作，最终到达叶子节点即可获取整行数据。这个过程称为回表。

聚簇索引的优势在哪？

1、由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键 Id 来组织数据，获得数据更快。
2、辅助索引使用主键作为指针而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作。
使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是 InnoDB 在移动行时无须更新辅助索引中的这个指针。
也就是说行的位置会随着数据库里数据的修改而发生变化，使用聚簇索引就可以保证不管这个主键 B+ 树的节点如何变化，辅助索引树都不受影响。

小结

这次内容比较多，涉及到了一些数据结构的内容，我也是翻了很多博客才搞懂那么一点点。主要是要搞懂，为什么要用索引，以及索引的查询流程。
希望对你有用。

参考：

http://blog.codinglabs.org/articles/theory-of-mysql-index.html
https://blog.csdn.net/v_JULY_v/article/details/6530142