MySQL B+ 树查询全过程详解

MySQL B+ 树查询全过程详解

基于 InnoDB 存储引擎，以单次等值查询为主线，贯穿从根节点到数据行的完整路径。

---

一、前置知识：B+ 树结构

1.1 一棵 InnoDB B+ 树长什么样

┌─────────────────────┐ │ [根节点] Page 3 │ │ 100 │ 500 │ 900 │ └──┬────┼───────┼────┬─┘ ┌────────────┘ │ │ └────────────┐ ▼ ▼ ▼ ▼ ┌─────────────────┐ ┌─────────┐ ┌─────────┐ ┌─────────────────┐ │ [内节点] Page 5 │ │ Page 7 │ │ Page 11 │ │ [内节点] Page 13│ │ 10 │ 50 │ 80 │ │150│300 │ │550│700 │ │ 950 │ 1100 │ 1500│ └─┬───┼───┼──┬────┘ └──┬───┬──┘ └──┬───┬──┘ └─┬───┼──────┼────┘ │ │ │ │ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ 叶子节点（双向链表，存储完整行数据） ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 10 │→│ 50 │→ ... →│ 80 │→ ... →│1500│ │data│ │data│ │data│ │data│ └────┘ └────┘ └────┘ └────┘

关键特征：

特征	说明
数据只存叶子节点	内节点仅存索引键 + 子页指针，不存数据
叶子节点双向链表	每个叶子页有prev/next指针，支持范围扫描
节点 = 页（Page）	InnoDB 默认 16KB，所有节点统一按页组织
非叶子节点也称"内节点"	只起导航作用

---

1.2 一个 Page（页）内部长什么样

┌─────────────────────── 16KB ───────────────────────┐ │ File Header (38B) │ ← 页类型、页号、校验和 ├─────────────────────────────────────────────────────┤ │ Page Header (56B) │ ← 记录数量、槽数量、层级 ├─────────────────────────────────────────────────────┤ │ Infimum + Supremum (26B) │ ← 虚拟最小/最大记录，边界哨兵 ├─────────────────────────────────────────────────────┤ │ User Records │ ← 真正的数据行（按主键有序） │ ┌────┬────┬────┬────┬────┐ │ │ │ 10 │ 50 │ 80 │100 │150 │ ... │ │ └────┴────┴────┴────┴────┘ │ ├─────────────────────────────────────────────────────┤ │ Free Space │ ← 剩余空间 ├─────────────────────────────────────────────────────┤ │ Page Directory (槽数组) │ ← 二分查找用的"目录" │ Slot0 → Infimum │ │ Slot1 → 第1组（含记录 10） │ │ Slot2 → 第2组（含记录 50, 80） │ │ ... │ ├─────────────────────────────────────────────────────┤ │ File Trailer (8B) │ ← 校验和、LSN └─────────────────────────────────────────────────────┘

Page Directory（页目录）是页内二分查找的关键——它不是为每条记录建一个槽，而是将记录分组（每组 4-8 条），每组有一个槽指向该组最大的记录。

---

二、查询全过程（以SELECT * FROM user WHERE id = 80为例）

假设表结构：

CREATETABLEuser(idINTPRIMARYKEY,-- 主键索引（聚簇索引）nameVARCHAR(50),ageINT,KEYidx_age(age)-- 二级索引（辅助索引）)ENGINE=InnoDB;

B+ 树元信息（3层结构）：

┌──────────────────────┐ 根节点 │ Page 3 (层级=2) │ │ keys: [100, 500, 900]│ │ ptrs: [P5, P7, P11,P13]│ └──┬───┬───┬───┬──────┘ ┌────────┘ │ │ └──────────┐ ▼ ▼ ▼ ▼ ┌─────────┐ ┌─────────┐ ┌──────────┐ │Page 5 │ │Page 7 │ │Page 13 │ ← 内节点 (层级=1) │[10,50,80]│ │[150,300]│ │[1100,1500]│ └──┬──┬──┬─┘ └──┬──┬──┘ └──┬───┬───┘ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ┌──────┐ ┌──────┐ ┌──────┐ 叶子节点 (层级=0) │Page 6│ │Page 8│ │Page 14│ ← 存完整行数据 │id=10 │ │id=80 │ │id=500│ │id=50 │ │id=100│ │ ... │ └──────┘ └──────┘ └──────┘

---

第 1 步：连接层接收 SQL，进入优化器

客户端 │ SELECT * FROM user WHERE id = 80 ▼ MySQL Server 层 ├─ 解析器 → AST 语法树 ├─ 优化器 → 选择执行计划 │ ├─ 候选计划1：PRIMARY 聚簇索引，等值查找 │ └─ 选择：PRIMARY 索引，(cost 最低) └─ 执行器 → 调用 InnoDB 引擎接口 │ └── ha_innobase::index_read(idx=PRIMARY, key=80)

优化器决策：WHERE id = 80且id是主键 →直接走聚簇索引等值查找。

---

第 2 步：从 Buffer Pool 查找根节点页

执行器调用 InnoDB: "在 PRIMARY 索引中找 key=80" InnoDB 第一步：获取根节点 │ ├─ 查 Buffer Pool (内存中的页缓存) │ ├─ 命中？→ 直接使用内存中的 Page 3 │ └─ 未命中？→ 从磁盘读取 Page 3 到 Buffer Pool │ └─ 发起一次磁盘随机 I/O │ └─ Page 3 内容（根节点，层级=2）: keys: [100, 500, 900] ptrs: [P5 , P7, P11, P13]

---

第 3 步：根节点内二分查找，确定下一层子节点

在 Page 3 中二分查找 key=80： Page Directory（简化）: Slot0 → Infimum (最小哨兵) Slot1 → 记录组 {100} Slot2 → 记录组 {500, 900} Slot3 → Supremum (最大哨兵) 二分查找过程： ┌─ low=0, high=3 ├─ mid=1 → 指向记录 {100}, key=100 ├─ 100 > 80？是 → high=1 ├─ mid=0 → Infimum, 不是真正的用户记录 ├─ low=1 └─ 最终定位：key=100 的槽 结论：80 < 100，所以沿指针 P5（第一个子指针）进入下一层。 key=80 属于 (-∞, 100) 区间 ↓ P5 → Page 5

示意图：

Page 3 (根节点) ┌─────────────────────────────────────┐ │ keys: [100, 500, 900] │ │ ptrs: [P5, P7, P11, P13] │ │ ↑ │ │ 80<100, 走 P5 │ └─────────────────────────────────────┘ │ ▼ Page 5

---

第 4 步：进入内节点 Page 5，再次二分查找

同样先查 Buffer Pool，缺页则磁盘读取。 Page 5 (内节点, 层级=1): keys: [10, 50, 80] ptrs: [P20, P21, P22, P23] 二分查找 key=80： Slot1 → 记录组 {10, 50} Slot2 → 记录组 {80} 定位到 key=80 → 命中！ 对于非叶子节点，指针规则是： 当 key == 内节点键值时，走右侧指针 P23 （因为 80 >= 80，属于 [80, +∞) 区间） 结论：沿 P23 → Page 8

Page 5 (内节点) ┌──────────────────────────────┐ │ keys: [10, 50, 80] │ │ ptrs: [P20, P21, P22, P23]│ │ ↑ │ │ 80>=80, 走 P23 │ └──────────────────────────────┘ │ ▼ Page 8 (叶子节点)

---

第 5 步：到达叶子节点 Page 8，二分查找目标记录

Page 8 (叶子节点, 层级=0): 存放完整的行数据： ┌──────────────────────────────┐ │ Infimum │ │ ┌──────┬──────────┬──────┐ │ │ │id=80 │ name=张三│ age=25│ │ ← 目标行！ │ ├──────┼──────────┼──────┤ │ │ │id=100│ name=李四│ age=30│ │ │ └──────┴──────────┴──────┘ │ │ Supremum │ └──────────────────────────────┘ 二分查找 key=80 → 命中！ 读取该行完整数据。

---

第 6 步：返回数据

InnoDB 将找到的行数据返回给 MySQL Server 层： ┌─────────────────────────────┐ │ id=80, name='张三', age=25 │ └─────────────────────────────┘ Server 层检查权限？→ 通过 Server 层将结果发送给客户端

---

三、完整时间线总览

时刻 操作 Buffer Pool 磁盘IO ──────────────────────────────────────────────────────── T0 Server 层解析 SQL - - T1 优化器选 PRIMARY 索引 - - T2 InnoDB 查根节点 Page 3 [命中] 0次 T3 二分定位 → P5(Page 5) - - T4 查内节点 Page 5 [未命中] 1次随机读 T5 二分定位 → P23(Page 8) - - T6 查叶子 Page 8 [未命中] 1次随机读 T7 二分定位 → id=80 行 - - T8 返回行数据给 Server 层 - - ──────────────────────────────────────────────────────── 总计：3层B+树查询 = 最多 0~3 次磁盘 I/O （实际几乎都在内存中，因为热数据一直 cached）

---

四、覆盖索引（Covering Index）的查询过程

-- 假设有索引 idx_age(age)，查询只取 ageSELECTageFROMuserWHEREage=25;

二级索引 B+ 树 (idx_age)： ┌─────────┐ 根节点 │ [30,60] │ └──┬───┬──┘ ┌────┘ └───┐ ▼ ▼ ┌───────┐ ┌───────┐ ← 叶子节点存 (age, id) │15,20,25│ │30,40,60│ │(id=10) │ │(id=15) │ ← 主键 id 作为二级索引的"数据" └───────┘ └───────┘ 查询过程： 1. 遍历 idx_age B+ 树到叶子节点 2. 在叶子节点找到 age=25 3. 直接读取 age=25 的值返回 ⚡ 无需回表！因为 age 本身就是索引键。 EXPLAIN 会显示 Extra: Using index

---

五、二级索引 + 回表的查询过程

-- idx_age 是二级索引，但 SELECT * 需要所有列SELECT*FROMuserWHEREage=25;

二级索引 B+ 树 (idx_age) 聚簇索引 B+ 树 (PRIMARY) ┌─────────┐ ┌─────────┐ 根节点│ [30,60] │ 根节点 │ [100,500]│ └──┬───┬──┘ └──┬───┬──┘ ┌────┘ └───┐ ┌────┘ └───┐ ▼ ▼ ▼ ▼ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ │15,20,25│ │30,40,60│ │10,50,80│ │100,500│ │id=3 │ │id=1 │ │完整数据│ │完整数据│ │id=7 │ │id=15 │ └───────┘ └───────┘ │id=99 │←──│找到 id=15 ▲ └───────┘ └───────┘ │ 拿着 id=15 │ 再去聚簇索引查一次 └──── 这就是"回表"

完整步骤：

步骤1: 在 idx_age 的 B+ 树中查找 age=25 → 在叶子节点找到 age=25, id=99（该记录的主键） 步骤2: 拿着 id=99，去聚簇索引（主键 B+ 树）再查一次 → 从根节点开始，逐层定位到叶子节点 → 找到 id=99 的完整行 → 取出 name 等列 步骤3: 返回完整行给 Server 层 ⏱ 回表 = 又走一遍 B+ 树，多若干次磁盘 I/O 💡 这就是为什么大范围扫描时 MySQL 可能放弃索引全表扫描： 回表代价大于直接扫聚簇索引的代价。

---

六、范围查询的过程

SELECT*FROMuserWHEREidBETWEEN80AND300;

步骤1: 等值查找定位左边界 id=80 → 同第三节，找到叶子节点中 id=80 的记录 步骤2: 利用叶子节点的双向链表，向右遍历 ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 80 │ → │100 │ → │150 │ → │300 │ → ... └────┘ └────┘ └────┘ └────┘ ↑ ↓ 左边界 id<=300, 停止 步骤3: 将符合条件的行 (80, 100, 150, 300) 逐行返回 步骤4: 如果跨页，顺着 next 指针到相邻叶子页继续读取 ⚡ 范围查询的精髓：一次定位左边界 + 链表顺序读取 相邻页物理上大概率连续 → 顺序IO → 非常快

---

七、一个 Page 内的二分查找细节（Page Directory 机制）

这是很多人忽略的细节——页内并不是一条条遍历，而是用槽做二分查找：

Page 8 中的实际物理存储： 偏移量 记录内容 槽 ─────────────────────────────────────────── 0 Infimum (最小哨兵) ←── Slot0 60 记录: id=80, name=张三 ←── Slot1 (该组最大记录) 110 记录: id=100, name=李四 160 记录: id=150, name=王五 ←── Slot2 (该组最大记录) 210 记录: id=200, name=赵六 260 记录: id=250, name=小明 ←── Slot3 (该组最大记录) 310 Supremum (最大哨兵) ←── Slot4 查找 id=150 的过程： 1. low=0, high=4 (槽的范围) 2. mid=2 → Slot2 指向的记录是 id=150 3. 二分直接命中！无需逐个扫描记录。

槽的思想：每 4-8 条记录分为一组，组内最大记录的偏移量存入 Page Directory。查找时先二分定位到槽，再在组内（最多 8 条）顺序扫描。这样页内查找从 O(n) 降为 O(log n)。

---

八、B+ 树层级与容量估算

以 InnoDB 默认 16KB 页、假设一行数据 1KB 为例：

层级	能容纳的行数	说明
1 层	~16 行	仅根节点（即叶子节点），数据量很小时存在
2 层	~16 × 1600 ≈2.5 万	根节点存约 1600 个键值指针
3 层	~16 × 1600² ≈4000 万	绝大多数表的实际层级
4 层	~16 × 1600³ ≈640 亿	极少见

绝大多数生产库的 B+ 树只有 3 层，一次等值查询最多 3 次磁盘 I/O。

---

九、总结

一条 SELECT * FROM user WHERE id = 80 的执行路径： Server 层 InnoDB 层 ──────── ────────── 解析SQL │ 优化器选索引 │ 调用引擎接口 ──────────────► Buffer Pool 找根节点 Page │ │ │ 二分定位下一层指针 │ │ │ 重复 2~3 次 │ │ │ 到达叶子节点 │ │ │ 页内二分定位目标行 │ │ ◄──────────────────────── 返回行数据 │ 发送给客户端

核心要点：

1. 树的高度决定了 IO 次数，3 层树最多 3 次随机 IO
2. 内节点只导航，数据全在叶子——这是 B+ 树区别于 B 树的关键
3. 叶子节点成链表——范围查询只需定位左边界，然后顺序扫描
4. 页内二分靠 Page Directory——先在槽上二分，再在组内顺序找
5. 回表是性能杀手——覆盖索引能避免，也是索引优化的核心思路