查询数据时，到了B+树的叶子节点，之后的查找数据是如何做？

当查询到达 B+ 树的叶子节点后，后续的查找工作主要分为两个阶段：在叶子节点内部进行精确查找，以及根据叶子节点存储的信息获取完整数据。

具体步骤如下：

1. 在叶子节点内部进行二分查找

• 节点结构：每个叶子节点内部通常是一个有序的键值对数组。数组中的每个元素包含一个键（Key）和该键对应的数据地址或数据本身。
• 查找方式：由于数组是有序的，数据库不会逐一遍历，而是使用二分查找算法（或其变种，如线性插值查找）。时间复杂度为 O(log M)，其中 M 是单个叶子节点能容纳的键值数量（通常几百到上千）。这一步能迅速定位到你要查的那个键具体在叶子节点的哪个位置。

2. 根据存储模式获取数据

找到具体的键值对后，如何获取数据取决于数据库的索引类型（以 MySQL InnoDB 为例）：

情况A：聚簇索引（主键索引）

• 叶子节点存储：直接存储完整的行数据。
• 操作：在叶子节点找到主键后，该节点上的数据页就是实际的行记录。数据库直接将这些数据返回给客户端。无需回表，性能最高。

情况B：二级索引（辅助索引）

• 叶子节点存储：不存完整数据，只存储索引列的值 + 主键的值。

• 操作：

  1. 在二级索引的叶子节点找到目标索引值和对应的主键。
  2. 回表：拿着这个主键，再回到聚簇索引（主键索引）中查找。
  3. 在聚簇索引的根节点重复查找过程，到达其叶子节点，最终拿到完整行数据。

  如果索引包含了查询所需的所有列（覆盖索引），则可以直接从二级索引叶子节点返回数据，不需要回表。

情况C：堆表组织（如 Oracle、SQL Server 部分情况）

• 叶子节点存储：存储键值 + 物理地址（RowID）。
• 操作：在叶子节点找到键后，直接获取 RowID（记录在数据文件中的具体位置），然后根据该地址直接读取数据行。这也相当于一次“地址寻址”。

3. 范围查询时的后续遍历

如果是范围查询（如 WHERE id BETWEEN 10 AND 20）：

• 当定位到范围起点（如 id=10）在叶子节点中的位置后，数据库会沿着叶子节点向右顺序扫描。
• 这是因为 B+ 树的叶子节点之间通过双向链表连接（MySQL InnoDB 是双向，有些实现是单向）。
• 数据库依次读取链表中的下一个键值对，直到值超过范围终点（如 >20）。在扫描过程中，如果涉及二级索引，则对每个命中的主键执行回表。

总结流程图

查询开始
    ↓
从根节点向下找到目标叶子节点
    ↓
在叶子节点的有序数组中进行【二分查找】
    ↓
找到目标键
    ↓
┌─────────────┴─────────────┐
│ 索引类型？                 │
↓                           ↓
聚簇索引                  二级索引
↓                           ↓
直接返回                  拿到主键
完整行数据                    ↓
                          回表到聚簇索引
                              ↓
                          拿到完整行数据

所以，“到了叶子节点之后”的关键操作是：内部二分查找 + 数据提取（直接/回表） + 链表顺序遍历（范围查询时）。