InnoDB B-TREE 索引怎么计算 WHERE 条件范围内有多少条记录？

MySQL 为一个表选择读取数据的方式，取决于这种方式的执行成本。

如果 WHERE 条件能够命中索引(包含主键索引、二级索引)，计算 WHERE 条件范围内的记录数量，是计算使用索引执行查询的成本的关键指标。

本文我们就一起来看看这个关键指标是怎么计算的?

本文内容基于 MySQL 8.0.29 源码。

正文

1、整体概览

一个 WHERE 条件范围(例如 WHERE a >= 100 AND a <= 200)，就是一个扫描区间 [100,200]，扫描区间有起点和终点，本文中我们把扫描区间的起点叫作 左端点，终点叫作右端点。

计算 WHERE 条件范围内有多少条记录，就是计算其对应的扫描区间有多少条记录，整体来看，会经过两大步骤：

第 1 步，定位索引叶结点中扫描区间左端点、右端点对应的记录。

这个过程是从根结点开始自上而下进行的。

经过索引的每一层，会分别把该层中左端点、右端点记录所在索引页的页号，保存到数组里，得到从根结点到叶结点中的左端点、右端点记录经过的索引页的路径。

左端点路径保存在数组 path1 中，右端点路径保存在数组 path2 中，如下图所示：

以一个 3 层的 B-TREE 索引为例，来说明这个自上而下的定位过程：

定位索引叶结点中扫描区间左端点、右端点记录，是独立进行的，但是执行流程完全一样，所以放在一起介绍了。

首先，在根结点中，左端点、右端点记录都在根结点范围内，path1[0]、path2[0] 中都会保存根结点的页号。

左右端点对应的记录，可能是根结点中的同一条记录或不同记录。

读取根结点中左端点、右端点记录指向的子结点的页号。

然后，进入左端点、右端点记录对应的内结点，path1[1] 中保存左端点记录所在内结点的页号，path2[1] 中保存右端点记录所在内结点的页号。

左右端点对应的记录，可能是不同内结点中的记录，也可能是相同内结点中的同一条记录或不同记录。

读取左端点、右端点在各自内结点中对应的记录指向的叶结点的页号。

最后，进入左端点、右端点记录对应的叶结点，path1[2] 中保存左端点记录所在叶结点的页号，path2[2] 中保存右端点记录所在叶结点的页号。

左右端点对应的记录，可能是不同叶结点中的记录，也可能是相同叶结点中的同一条记录或不同记录。

关于定位扫描区间左端点、右端点记录的过程，上一篇文章中有详细介绍，感兴趣的小伙伴可以点击这个链接阅读：InnoDB B-TREE

索引怎么定位一条记录?

第 2 步，计算扫描区间的记录数量。

经过第 1 步，得到了左右端两个路径数组，数组中保存着从根结点到叶结点，扫描区间左右端点所经过的每一个索引页的页号。

计算扫描区间包含多少条记录，最终是要计算叶结点所在的层级，扫描区间中包含的记录数量。

由于叶结点所在的层级，扫描区间中的记录可能会分散在很多很多个连续的叶结点中，挨个读取扫描区间中的所有叶结点的记录数量是不现实的，这就需要借助叶结点的上层结点了。

上层结点中的记录数量就是其管辖范围内的叶结点的数量。

然而，叶结点的上层结点所在的层级，也可能有很多很多的同级结点，那又需要借助更上一层结点，这样逐层往上推，最终可能需要读取根结点有多少个子结点。

正是因为计算扫描区间包含多少条记录，可能需要依赖上层结点，在源码的实现中，这个过程也是从根结点自上而下进行的。

自上而下进行的过程，就是遍历左端点、右端点路径数组，计算每一层从左端点记录到右端点记录这个区间内包含的记录数量，最终到达叶结点所在的层级，得到扫描区间的记录数量。

源码的实现自上而下进行，文章却不能这么写，否则陷入代码细节，写出来也很晦涩难懂。

接下来，我们根据扫描区间左端点、右端点记录在叶结点中的不同位置，分场景介绍计算扫描区间的记录数量的过程，请大家保持愉悦的心情看下去，可能会更容易看懂

^_^

2、 场景分析

我们分场景进行介绍是为了更好理解，但是，不同场景下都会涉及到一些又臭又长并且需要重复描述的定义。

在更好理解的基础上，我们也要尽量保持内容的简洁，为此，把一些需要重复描述的定义在这里列出来，并用短一点的描述来代替，以简化内容。

左索引页记录数，左端点记录所在的索引页中，从左端点记录的下一条记录开始，直到当前索引页中的 supremum

伪记录的上一条记录为止，这个范围内的记录数量。

右索引页记录数，右端点记录所在的索引页中，从当前索引页中的 infimum伪记录的下一条记录开始，直到右端点记录的上一条记录为止，这个范围内的记录数量。

左右端点之间记录数，除了左端点记录、右端点记录之外，扫描区间中的其它用户记录的数量，也就是说，所有索引页中的 infimum、supremum

伪记录都不包含在内。

（1） 同一条记录

扫描区间左端点、右端点记录是叶结点中的同一条记录，除去左右端点记录之外，区间之内没有其它记录，左右端点之间记录数 = 0。

但是，这并不意味着扫描区间的记录数量就为 0。

因为，扫描区间的记录数量 = 左右端点之间的记录数 + 左端点记录 + 右端点记录。

处理左右端点记录的计数逻辑，然后得到扫描区间记录数量，这个计算过程是所有场景共用的，会在第 2 节的结尾处单独用一个小节来介绍，这里先按下不表。

（2）同一个叶结点中的不同记录

扫描区间左端点、右端点记录是同一个叶结点中的不同记录，计算逻辑也比较简单。

左右端点之间记录数 = 右端点记录之前的记录数量 – 左端点记录之前的记录数量。

左右端点记录之前的记录数量，指的是它们共同所在的索引页中，左右端点记录各自前面有多少条记录，如下图所示：

（3）相邻叶结点中的记录

扫描区间左端点、右端点记录是相邻叶结点中的记录，计算逻辑依然比较简单。

左右端点之间记录数 = 左索引页记录数 + 右索引页记录数。

（4）相隔小于等于 9 个叶结点

扫描区间左端点、右端点记录所在的索引页，中间隔着其它索引页，计算逻辑开始变得有一点点复杂了。

左右端点之间记录数 = 左索引页记录数 + 中间索引页用户记录数之和 + 右索引页记录数。

上面算式中，中间索引页用户记录数之和计算逻辑如下：

从扫描区间左端点记录所在索引页的下一个索引页开始，从每个索引页的头信息 PAGE_N_RECS中读取索引页中的用户记录数量并累加求和，直到扫描区间右端点记录所在索引页的上一个索引页为止。

PAGE_N_RECS 中不包含 infimum、supremum 伪记录。

（5）相隔大于 9 个叶结点

前面几个小节介绍的场景，计算扫描区间记录数量的逻辑，都是精确计算。

本小节介绍的场景是：扫描区间左端点、右端点记录所在的索引页，中间隔着大于 9 个索引页，如下图所示：

此场景下，InnoDB不会读取扫描区间内所有索引页中的用户记录数量，而是只读取前面一部分索引页中的用户记录数量，并据此估算出扫描区间内的用户记录数量，估算过程是这样的：

第 1 步，从扫描区间左端点记录所在索引页的下一个索引页开始，连续读取 9 个索引页中的用户记录数量并累加求和。

每个索引页中的用户记录数量都是从索引页的头信息 PAGE_N_RECS 中读取，不包含 infimum、supremum 伪记录。

第 2 步，第 1 步得到的 9 个索引页的用户记录数量之和 + 左索引页记录数 + 右索引页记录数，得到计算结果，InnoDB 把这个结果当作 10

个索引页的用户记录数量之和。

第 3 步，第 2 步得到的10 个索引页的用户记录数量之和，除以 10，得到的计算结果，作为扫描区间范围内每个索引页的平均用户记录数。

第 4 步，第 3 步得到的平均用户记录数 * 左右端点之间间隔的索引页数(如下图所示)，得到间隔索引页的用户记录数量之和。

左右端点记录之间的索引页数，就是对上一层级进行 2.1 ~ 2.5 小节的计算逻辑得到。

第 5 步，左右端点之间记录数 = 第 4 步得到的左右端点记录之间间隔索引页的用户记录数量之和 + 左索引页记录数 + 右索引页记录数。

前面说了在估算场景下，InnoDB 会用 10 个索引页中的用户记录数量之和计算每个索引的平均用户记录数。

为什么本小节的标题是左右端点之间相隔大于 9 个索引页?

因为 InnoDB 把左索引页记录数、右索引页记录数加起来当作一个索引页的用户记录数量，再加上从扫描区间左端点记录所在索引页的下一个索引页开始读取的 9

个索引页中的用户记录数量之和，就是 10 个索引页的用户记录数量了。

（6） 处理左右端点记录的计数逻辑

前面提到过，扫描区间的记录数量 = 左右端点之间记录数 + 左端点记录(0 或 1) + 右端点记录(0 或 1)。

这是所有场景共用的逻辑，在这里单独用一小节来介绍。

如果扫描区间左端点是闭区间(例如 WHERE a >= 100)，则左端点记录需要计入扫描区间的记录数量，上面算式中，左端点记录括号内取

0。

否则不计入，上面算式中，左端点记录括号内取 1。

如果扫描区间右端点是闭区间(例如 WHERE a <= 200)，则右端点记录需要计入扫描区间的记录数量，上面算式中，右端点记录括号内取

0。

否则不计入，上面算式中，右端点记录括号内取 1。

然后，就得到了扫描区间的记录数量。

不过，别着急，这有可能还不是最终结果。

（7） 修正扫描区间记录数量

经过 2.6 小节中左右端点记录的计数逻辑处理，已经得到了扫描区间的记录数量。

如果扫描区间左端点、右端点记录所在的索引页，中间隔着大于 9

个索引页(也就是估算场景)，计算得到扫描区间的记录数量之后，还需要对这个数量进行一系列修正。

首先，InnoDB 认为估算的记录数量都会比实际数量少，所以，会对前面计算得到的扫描区间记录数量乘以 2，得到扫描区间的修正记录数量，即修正记录数量 =

扫描区间的记录数量 * 2。

然后，InnoDB

不会让估算记录数量大于表中记录数量的一半，如果扫描区间的修正记录数量超过表中记录数量的一半，就把修正记录数量设置为表中记录数量的一半。

最后，修改记录数量就是扫描区间的记录数量，这才是最终结果。

（8）小结

前面分场景介绍计算扫描区间的记录数量的过程，为了保持文章尽量简洁，把处理左右端点记录的计数逻辑(2.6 小节)、修正扫描区间记录数量(2.7小节)独立成为两个小节，有一点零散。

本小节以一张流程图来对前面的计算过程进行总结，如下：

三、 总结

第 2 节 以定位索引叶结点中扫描区间左端点、右端点对应的记录开始，介绍了计算扫描区间记录数量的整体过程。

第 3 节 根据索引叶结点中，左右端点记录所在位置的不同，分 5 种场景介绍了计算扫描区间记录数量的详细过程。

经过 5 种场景计算得到左右端点之间记录数之后，再进行左右端点记录的计数逻辑处理，得到扫描区间的记录数量。

对于精确计算场景，这就是最终的结果了。

对于估算场景，还需要对扫描区间的记录数量进行一系列修正，才能得到估算场景下的最终结果。

本文转载自微信公众号「一树一溪」，可以通过以下二维码关注。转载本文请联系一树一溪公众号。