InnoDB是顺序查找B+Tree叶子节点的吗？-一一网

在《为什么MySQL能够支撑千万数据规模的快速查询？》中，我详细讲解了InnoDB B+Tree的结构，同时，我以下面这条SQL举例：

SELECT * FROM user WHERE age >= 15
复制代码

讲解了该查询是如何搜索辅助索引index_age_birth这颗索引树的。其中，我在查找叶子节点时，说到从节点内第一条记录开始，向右遍历该节点内所有记录即可定位到满足条件的第一条记录，然后，遍历该记录后继所有记录，即可得到满足条件的所有记录。

但是，如果叶子节点内的记录太多，而满足条件的第一条记录又不在头部位置，那么，顺序遍历查找的性能是很差的。该如何解决这个问题呢？我想，你可能已经猜到了，是的，由于叶子节点的记录是升序排列的，我们完全可以用二分查找，快速定位到满足条件的第一条记录。

那么，InnoDB具体是怎么做的呢？

我以用户表索引index_age_birth为例，先来看一下该索引叶子节点的结构：

见上图，跟之前我讲的辅助索引B+Tree的叶子节点是不是不一样？是的，之前我讲的比较粗，现在我把它细化了，为了详细讲解一个查询是如何在B+Tree的叶子节点中定位一条记录的。

我们来仔细看下上面这张图，相比之前的叶子节点，这张图多出来三个元素：

infimum：叶子节点中的虚拟记录，该记录的下一条记录即为叶子节点中的最小记录。比如：图中元组记录<15, 2007-06-06, 6>为页4这个叶子节点中的最小记录。

supremum：叶子节点中的虚拟记录，该记录的上一条记录为叶子节点中的最大记录。比如：图中元组记录<18, 2007-06-10, 12>为页4这个叶子节点中的最大记录。

槽：InnoDB将叶子节点内的记录分成几组，每一组叫做slot，也就是槽，这个slot指向分组内最大的一条记录。这个槽有以下几个特点：

槽内存储的是一个偏移量，这个偏移量是从叶子节点0字节开始计算的。比如：
- 图中的99，表示从叶子节点0字节开始第99字节的位置为槽0。
- 图中的252，表示从叶子节点0字节开始第252字节的位置为槽1。
- 图中的112，表示从叶子节点0字节开始第112字节的位置为槽2。
一个槽指向一个分组中的最大记录。比如，图中，浅黄色框代表分组，所以，槽1指向第二个分组的最大记录<17, 2007-06-10, 11>。
槽与槽之间组成一个无序数组，但槽的下标是有序的。比如，图中，99、252、112这3个偏移量是无序的，但是，槽的下标0、1、2是有序的。

这时，你可能会有个疑问：为什么第一个分组只有1条记录，第二个分组有4条记录，而最后一个分组有2条记录？

因为InnoDB引擎规定：对于infimum记录所在的分组只能有 1 条记录，supremum记录所在的分组拥有的记录条数只能在 1 ~ 8 条之间，剩下的分组中记录的条数范围只能在4 ~ 8条之间。

下面，我结合槽的结构定义，详细讲解InnoDB是如何在叶子节点中定位记录的？

InnoDB查找叶子节点的过程采用的是对槽二分查找，槽所指记录所在分组内顺序查找的方式。至于为什么槽内不用二分查找，是因为槽指向的记录所在分组记录总数不会超过8条，所以，没必要使用二分查找来提升查找性能。

我以本章《导读》中的SQL为例，详细讲解InnoDB在叶子节点中如何查找第一条满足查询条件的记录。

SELECT * FROM user WHERE age >= 15
复制代码

见下面5张图，该图为索引index_age_birth这个B+Tree的叶子节点：

定位最小下标的槽为low，即图(1)中的槽0，定位最大下标的槽为high，即图(1)中的槽2。
(low + high) / 2进行二分查找，即(0 + 2) / 2 = 1，所以，定位槽1，见图(2)，找到槽1指向的记录<17, 2007-06-10, 11>。
该记录age = 17，查询条件age的值为15，17 > 15，说明目标记录在该记录左边，所以，见图(2)，high指向槽1，由于low指向槽0，high - low = 1，所以，查找记录在槽0和槽1之间。
见图3，将low_rec指向槽0指向的infimum记录，high_rec指向槽1指向的<17, 2007-06-10, 11>记录，从槽0指向的记录infimum开始向右遍历记录。ps：图(3)、(4)、(5)为了更清晰地描述槽指向记录所在的分组内部的查找过程，将槽移除了。
遍历到第二条记录<15, 2007-06-06, 6>，见图(4)，该记录age = 15，查询条件age的值为15，15 = 15，所以，该记录为满足查询条件的第一条记录，low_rec指向该记录。
遍历到第三条记录<16, 2007-06-08, 8>，见图(5)，该记录age = 16，查询条件age的值为15，16 > 15，所以，high_rec指向该记录。
high_rec和low_rec间隔1，说明查找结束，最终，定位满足查询条件age>=15的第一条记录为<15, 2007-06-06, 6>。