数据库索引融会贯通

摘要：索引的各种规则纷繁复杂，不了解索引的组织形式就没办法真正地理解数据库索引。顺畅地阅读这篇文章需要了解索引联合索引聚集索引分别都是什么，如果你还不了解，可以通过另一篇文章来轻松理解数据库索引是什么新华字典来帮你。

索引的各种规则纷繁复杂，不了解索引的组织形式就没办法真正地理解数据库索引。通过本文，你可以深入地理解数据库索引在数据库中究竟是如何组织的，从此以后索引的规则对于你将变得清清楚楚、明明白白，再也不需要死记硬背。

顺畅地阅读这篇文章需要了解索引、联合索引、聚集索引分别都是什么，如果你还不了解，可以通过另一篇文章来轻松理解——数据库索引是什么？新华字典来帮你。

这篇文章是一系列数据库索引文章中的第二篇，这个系列包括了下面四篇文章：

数据库索引是什么？新华字典来帮你 —— 理解

数据库索引融会贯通 —— 深入

20分钟数据库索引设计实战 —— 实战

数据库索引为什么用B+树实现？ —— 扩展

这一系列涵盖了数据库索引从理论到实践的一系列知识，一站式解决了从理解到融会贯通的全过程，相信每一篇文章都可以给你带来更深入的体验。

通过之前的内容，我们已经对数据库索引有了相当程度的抽象了解，那么在数据库中，索引实际是以什么样的形式进行组织的呢？同一张表上的多个索引又是怎样分工合作的呢？

目前绝大多数情况下使用的数据库索引都是使用B+树实现的，下面就以MySQL的InnoDB为例，介绍一下数据库索引的具体实现。

下面是一个以B+树形式组织的拼音索引，在B+树中，每一个节点里都有N个按顺序排列的值，且每个值的中间和节点的头尾都有指向下一级节点的指针。在查找过程中，按顺序从头到尾遍历一个节点中的值，当发现要找的目标值恰好在一个指针的前一个值之前、后一个值之后时，就通过这个指针进入下一级节点。当最后到达叶子节点，也就是最下层的节点时，就能够找到自己希望查找的数据记录了。

在上图中如果希望找到险字，那么我们首先通过拼音首字母在根节点上按顺序查找到了X和Y之间的指针，然后通过这个指针进入了第二级节点···, xia, xian, xiang, ···。之后在该节点上找到了xian和xiang之间的指针，这样就定位到了第519页开始的一个目标数据块，其中就包含了我们想要找到的险字。

因为拼音索引是聚集索引，所以我们在叶子节点上直接就找到了我们想找的数据。

下面是一个模拟部首索引的组织形式。我们由根节点逐级往下查询，但是在最后的叶子节点上并没有找到我们想找的数据，那么在使用这个索引时我们是如何得到最终的结果的呢？回忆之前字典中“检字表”的内容，我们可以看到，在每个字边上都有一个页码，这就相当于下面这一个索引中叶子节点上险字与院字中间的指针，这个指针会告诉我们真正的数据在什么地方。

下图中，我们把非聚集索引（部首索引）和聚集索引（拼音索引）合在一起就能看出非聚集索引最后到底如何查找到实际数据了。非聚集索引叶子节点上的指针会直接指向聚集索引的叶子节点，因为根据聚集索引的定义，所有数据都是按聚集索引组织存储的，所以所有实际数据都保存在聚集索引的叶子节点中。而从非聚集索引的叶子节点链接到聚集索引的叶子节点查询实际数据的过程就叫做——回表。

那么如果我们只是想要验证险字的偏旁是否是双耳旁“阝”呢？这种情况下，我们只要在部首索引中阝下游的叶子节点中找到了险字就足够了。这种在索引中就获取到了SQL语句中需要的所有字段，所以不需要再回表查询的情况中，这个索引就被称为这个SQL语句的全覆盖索引。

在实际的数据库中，非聚集索引的叶子节点上保存的“指针”就是聚集索引中所有字段的值，要获取一条实际数据，就需要通过这几个聚集索引字段的值重新在聚集索引上执行一遍查询操作。如果数据量不多，这个开销是非常小的；但如果非聚集索引的查询结果中包含了大量数据，那么就会导致回表的开销非常大，甚至超过不走索引的成本。所以全覆盖索引可以节约回表的开销这一点在一些回表开销很大的情况下就非常重要了。

上图是一个联合索引idx_eg(col_a, col_b)的结构，如果我们希望查询一条满足条件col_a = 64 and col_b = 128的记录，那么我们可以一路确定地往下找到唯一的下级节点最终找到实际数据。这种情况下，索引上的col_a和col_b两个字段都能被使用。

但是如果我们将查询条件改为范围查询col_a > 63 and col_b = 128，那么我们就会需要查找所有符合条件col_a > 63的下级节点指针，最后不得不遍历非常多的节点及其子节点。这样的话对于索引来说就得不偿失了，所以在这种情况下，数据库会选择直接遍历所有满足条件col_a > 63的记录，而不再使用索引上剩下的col_b字段。数据库会从第一条满足col_a > 63的记录开始，横向遍历之后的所有记录，从里面排除掉所有不满足col_b = 128的记录。

这就是范围条件会终止使用联合索引上的后续字段的原因。