MySQL 索引（上）

索引初识

首先通过一个例子来直观认识下索引对查询效率的提升。例子中使用的表为 employees（建表语句见附录）。在为 emp_no 字段加索引之前，查询 emp_no 为 401060 的职员信息，sql 如下：

select * from employees where emp_no = 401060;

查询结果如下：

运行时间如下：

在为 emp_no 字段加索引之后，再重新执行如下 sql ：

select * from employees where emp_no = 401060;

查询结果如下：

运行时间如下：

从前后的运行时间对比可以看出，加索引之后，查询效率有了千倍的提升。那么索引到底是什么？为什么能够提高查询效率呢？

现在以查词典为例来说明下索引的作用。小学的时候，我们都学过怎么查词典。比如，要查找索字，可以先通过拼音查找到索字在那一页。如下图所示：

然后再到相应的页中去查找索字。

这样便可以很快找到相应的字，比把词典从头翻到尾快多了，这里的拼音目录便相当于数据库表中的索引。

数据库的索引

二叉查找树

那么数据库表中的索引是怎么实现的呢？其实，数据库表中的索引就是一种数据结构。以 MySQL 的 InnoDB 存储引擎为例，它使用的数据结构是 B+ 树。为什么使用 B+ 树这种数据结构呢？

在讲解 B+ 树之前，先来介绍下二分查找法。二分查找法也称为折半查找法，用来查找一组有序记录中的某一项记录。其基本思想是，先将要查找的记录值和有序数列中位于中间点位置的记录值进行比较，如果小于位于中间点位置记录的值，则要查找的记录值在数列的左半部分，否则为右半部分。这样通过一次查找便可以将查找区间缩小一半。例如，我们有 3、5、8、13、21、34、55、89、144、233 十个数，假设我们要查找 144 这个数字，其查找过程如下图所示：

从图中可以看出，使用三次比较就找到了 144 这个数，如果用顺序查找则需要 9 次。基于上面 10 个数字，如果用顺序查找，则平均查找次数为 （1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10）/ 10 = 5.5 次。二分查找的平均查找次数为 （4 + 3 + 2 + 4 + 3 + 1 + 4 + 3 + 2 + 3）/ 10 = 2.9 次。二分查找具有查找速度快、平均性能好的优点，但是要求待查表为有序表，当要向表中插入或删除记录时，代价比较高。这样便出现了二叉查找树。对于上面的 10 个数字，假如数字的顺序为 21、5、89、3、8、34、144、13、55、233 可以构建如下二叉查找树：

假设要查找的数值为 a，则在上述二叉查找树中的查找步骤为：

1. 如果 a 大于根节点，则在右子树中进行查找。
2. 如果 a 小于根节点，则在左子树中进行查找。
3. 如果 a 等于根节点，也就是找到了这个节点，返回根节点即可。

在上述这个二叉树中查找值的最大比较次数为 4 次，这属于比较理想情况，查询的时间复杂度为 O(logn)。假如给出的数字顺序为 3、5、8、13、21、34、55、89、144、233，则构造的二叉查找树如下：

这时候二叉查找树已经退化成了一条链表，查找数据的时间复杂度变成了 O(n)。为了解决这个问题，提出了平衡二叉查找树（AVL 树），它在二叉查找树的基础上增加了约束，每个节点的左子树和右子树的高度差不能超过 1。刚才构建的第一棵二叉树便属于平衡二叉查找树。

现在有了平衡二叉树，是不是就意味着可以使用平衡二叉树来作为索引的存储结构呢？非也！原因是，索引不止存在于内存中，还要写在磁盘上。假设某个数据表有 100 万行数据，如果使用平衡二叉树来建索引，则得到的平衡二叉树树高为 20。一次查询可能需要访问 20 个数据块，也就是有可能会有 20 次磁盘 IO。当前的机械磁盘一次 IO 的大概时间为 10ms，20 次磁盘 IO 的时间为 200 ms。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 200 ms，这个时间是不能接受的。为了减少磁盘 IO，需要降低树的高度，让树变的更“矮胖”，为了让树变”矮胖“，需要增加每个节点的子节点的数目，这便是 M 叉树（M > 2）。还以刚才的 100 万行数据为例，如果 M = 10，则这时的树高为 4 。考虑到树根的数据块总是在内存中，查找一个值最多只需访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。M 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

B 树

B 树便是 M 叉树的一种，B 树的结构如下图所示：

B 树作为平衡的多路搜索树，它的每一个节点最多可以包含 M 个子节点，M 称为 B 树的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块包含了 N 个关键字，那么指针数就是 N + 1。一个 M 阶的 B 树（M > 2）有以下的特性：

1. 根节点的儿子数的范围是 2, M。
2. 每个中间节点包含 k - 1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 + 1，k 的取值范围为 ceil(M/2), M。
3. 叶子节点包含 k - 1 个关键字（叶子节点没有孩子），k 的取值范围为 ceil(M/2), M。
4. 假设中间节点的关键字为：key1, key2, ..., keyk - 1，且关键字按照升序排序，即 ki < ki + 1。此时 k - 1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P1, P2, ..., Pk，其中 P1 指向关键字小于 key1 的子树，Pi 指向关键字属于 （keyi-1, keyi）的子树，Pk 指向关键字大于 keyk-1 的子树。
5. 所有叶子节点位于同一层。

现在我们来看下如何用 B 树进行查找，假设我们要查找关键字 36，则查找步骤如下：

1. 将 36 与根节点比较，36 大于 35 得到指针 P3。
2. 根据指针 P3 找到磁盘块 4，36 小于 65 得到指针 P1。
3. 根据指针 P1 找到磁盘块 6，然后找到了关键字 36。

从查询的过程可以看出，B 树相对于平衡二叉树来说磁盘 I/O 操作更少，在数据查询中比平衡二叉树效率要高。

B+ 树

B+ 树是对 B 树的改进，B+ 树和 B 树的差异在以下几点：

1. 有 k 个孩子的节点就有 k 个关键字。
2. 非叶子节点的关键字也会同时存在于子节点中，并且是在子节点中所有关键字的最大或最小。
3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。
4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

下面便是一棵 B+ 树：

假如我们要查找关键字 60，则查找过程为：

1. 与根节点进行比较，得到指针 P2。
2. 顺着指针 P2 来到磁盘块3，与磁盘块 3 中的关键字进行比较，得到指针 P3。
3. 顺着指针 P3 来到磁盘块10，与磁盘块 10 中的关键字进行比较，找到关键字 60。

从查询过程来看，B+ 树和 B 树差不多，但是 B+ 树和 B 树的根本差异在于，B+ 树的中间节点不直接存储数据。这样做的好处是：

1. B+ 树查询效率更稳定，因为每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，有时候需要访问到叶子节点才能找到关键字。
2. B+ 树的查询效率更高，因为 B+ 树通常比 B 树更矮胖，查询所需的磁盘 I/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。

总结

本文首先通过一个例子直观看到索引对查询效率的提升。接下来对索引为什么能够提升查询效率做了讲解。最后介绍了 MySQL 中索引的存储结构。