请详细描述 MySQL 的 B+ 树中查询数据的全过程

回答重点

1）数据从根节点找起，根据比较数据键值与节点中存储的索引键值，确定数据落在哪个区间，从而确定分支，从上到下最终定位到叶子节点
2）叶子节点存储实际的数据行记录，但是一页有 16kb 大小，存储的数据行不止一条
3）叶子节点中数据行以组的形式划分，利用页目录结构，通过二分查找可以定位到对应的组
4）定位组后，利用链表遍历就可以找到对应的数据行

扩展知识

详细流程解析

数据从根节点找起，根据比较数据键值与节点中存储的索引键值，确定数据落在哪个区间，从而确定分支，从上到下最终定位到叶子节点。

定位到叶子节点后，因为一片叶子默认有 16k 大小，所以理论上可以存多条记录。叶子节点的实际构造如下图所示：

从上图可以知晓，叶子节点有页目录结构，它其实就是一个索引，通过它可以快速找到记录。

页目录分为了多个槽，每个槽都指向对应一个分组内的最大记录，每个分组内都会包含若干条记录。

通过二分查询，利用槽就能直接定位到记录所在的组，从而就能获取到对应的记录。

举个例子，现在有 5 个槽，如果想查找主键为 3 的记录，此时的流程是：

1）通过二分得到槽的中间位置，low = 0，high = 4，（0+4)/2 = 2;
2）通过槽定位到第二个分组中的主键为 4 的记录，4 大于 3，low = 0 不变，high = 2;
3）继续二分 (0+2)/2 = 1; 槽 1 中主键 2 小于 3，low = 1，high = 2;
4）此时 high - low = 1，可以确定值在 high 即槽 2 中，但是槽 2 只能定位到主键为 4 的记录，又因为槽之间是挨着的，所以可以得到槽 1 的位置，从槽 1 入手拿到 主键 2 的记录，然后因为记录是通过单向链表串起来的，往下遍历即可定位到主键 3 的记录。

以上就是利用二分查询的定位流程。通过槽可找到对应记录所在的组，或能直接定位到记录，或还需通过链表遍历找到对应的数据。

实际上，每个分组的记录数是有规定的，图中做了省略只画了两条，InnoDB 规定：

• 第一个分组只有一条记录
• 中间的分组 4-8 条记录
• 最后一个分组 1-8 条记录

因此不必担心遍历很长的链表导致性能问题。

这题的重点是先简单提下从根节点遍历到子节点的过程，然后提到叶子节点默认大小为 16KB ，所以理论上能存储很多记录，从而引出页目录，再通过二分查找才能对应记录。