MySQL B+树完全可视化指南

什么是B+树？

B+树是MySQL InnoDB存储引擎索引的底层数据结构，是一种多路自平衡查找树。理解它，就理解了MySQL索引的核心。

📖 核心定义

B+树（B-plus Tree） 是一种B树的变种，是N叉排序树。它将所有数据都存储在叶子节点，非叶子节点只存索引键值；且所有叶子节点通过双向链表连接，形成有序的数据层。

🔑 B+树的四大特征

非叶子节点只存键值

内部节点不保存数据记录，仅存储「键值 + 子指针」，使每个节点能容纳更多索引项，降低树的高度。

所有数据在叶节点

真实数据行指针/聚簇索引数据全部在叶子节点，查询必须走到叶子才结束。

叶子节点链式相连

所有叶子节点通过双向链表串联，支持高效的范围扫描与排序。

完美平衡

从根到任意叶子节点的路径长度完全相同，保证查询性能稳定为 O(log N)。

🎨 B+树整体形态

一棵 m阶 = 4 的 B+树示例（每个节点最多容纳4个key / 5个指针）

    💡 为什么InnoDB选择B+树而不是B树或Hash？

    B树：非叶子也存数据 → 节点能存的key更少 → 树更高 → 更多IO

    Hash：不支持范围查询、排序，等值查询快但不适合数据库场景

    B+树：非叶子纯索引 → 扁平树（通常3~4层）→ 极少磁盘IO + 叶子链表支持范围扫描

节点数据结构详解

InnoDB中，一个B+树节点本质上是一个「数据页」（Page），默认16KB。我们来看它的精确内存布局。

📦 InnoDB 数据页（Page）完整结构 — 16KB = 16384 字节

┌─────────────────────────────────────────────────────────────┐
│                    File Header (38 字节)                     │
│  FIL_PAGE_SPACE(4) | FIL_PAGE_OFFSET(4) | FIL_PAGE_TYPE(4) │
│  FIL_PAGE_PREV(4)  | FIL_PAGE_NEXT(4)   | FIL_PAGE_LSN(8)   │
│  FIL_PAGE_TYPE(4)  | FIL_PAGE_FLUSH_LSN(8) | CHECKSUM(4)     │
├─────────────────────────────────────────────────────────────┤
│                  Page Header (56 字节)                       │
│  PAGE_N_DIR_SLOTS(2) | PAGE_HEAP_TOP(2) | PAGE_N_HEAP(2)   │
│  PAGE_FREE(2) | PAGE_GARBAGE(2) | PAGE_LAST_INSERT(2)      │
│  PAGE_LAST(2) | PAGE_N_RECS(2) | PAGE_MAX_TRX_ID(8)       │
│  PAGE_LEVEL(2) | PAGE_INDEX_ID(8) | PAGE_BTR_SEG_LEAF(10)  │
├─────────────────────────────────────────────────────────────┤
│              Infimum + Supremum 虚拟记录 (~40 字节)           │
│         最小虚拟记录 "infimum"  |  最大虚拟记录 "supremum"     │
├───────────────────┬─────────────────────────────────────────┤
│                   │         User Records 区域               │
│                   │    ┌─────────────────────────┐          │
│                   │    │  Record 1 (变长)        │          │
│   Free Space      │    │  Record 2 (变长)        │ ◄── 从上往下增长
│   (空闲空间)       │    │  Record 3 ...          │          │
│                   │    │                         │          │
│                   │    └─────────────────────────┘          │
│                   │                                          │
│                   │    ┌─────────────────────────┐          │
│                   │    │  偏移数组 (Slot Directory) │         │
│                   │    │  [ptr] [ptr] [ptr] ...  │ ◄── 从下往上增长
│                   │    └─────────────────────────┘          │
├───────────────────┴─────────────────────────────────────────┤
│                  Page Trailer (8 字节)                       │
│                    PAGE_CHECKSUM (校验和)                      │
└─────────────────────────────────────────────────────────────┘
                              总大小：16384 字节 (16KB)

组成部分	大小	作用
File Header	38 bytes	描述页的基本信息：页号、页类型（索引页/数据页）、前后页指针（用于双向链表）、LSN号、校验和
Page Header	56 bytes	页的专有信息：记录数、堆顶偏移、空闲空间偏移、B+树层级(PAGE_LEVEL)、垃圾回收等
Infimum + Supremum	~40 bytes	两个虚拟边界记录，用于简化边界处理（比最小值还小 / 比最大值还大）
User Records	动态	用户实际存储的记录，从页头部向下增长。每条记录长度不定
Free Space	动态	未使用的空闲空间，位于User Records和Slot Directory之间
Slot Directory	动态	记录偏移数组，也叫「页目录」。每个slot指向一条记录（或一组记录），用于二分查找加速定位
Trailer	8 bytes	页校验和，用于检测页损坏

🟣 非叶子节点（Internal Node）— 只存索引，不存数据

非叶子节点的作用只有一个：快速导航到下一层。

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃             非叶子节点（Internal / Non-Leaf Page）          ┃
┠───────────────────────────────────────────────────────────╈──┨
║  ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬        ║  ╱
║  │ P₀   │ K₁   │ P₁   │ K₂   │ P₂   │ K₃   │ P₃   │ ...   ║ ╱
║  │ ↓    │      │ ↓    │      │ ↓    │      │ ↓    │        ║╱
║  └──┬───┴──────┴──┬───┴──────┴──┬───┴──────┴──┬───┴        ┃
║     ↓             ↓             ↓             ↓           ┃
║  [子节点0]     [子节点1]     [子节点2]     [子节点3]       ┃
┠───────────────────────────────────────────────────────────┃
┃                                                            ┃
┃  Pₙ = Page Pointer (6字节) — 指向子页面的文件偏移量         ┃
┃  Kₙ = Key Value (变长)    — 索引键值（如主键ID）           ┃
┃                                                            ┃
┃  ⚠️ 注意：Kₙ 是「最小分隔值」                                ┃
┃     K₁ 表示：子节点P₀的所有 key < K₁ ≤ 子节点P₁的所有 key    ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

        关键点： 非叶子节点的一条记录 = 6字节页指针 + 键值。

        因为不存数据，一条记录非常小！这意味着一个16KB的非叶子页可以存放大量索引项，让树变得很扁。

🟢 叶子节点（Leaf Node）— 存储真实数据

叶子节点才是真正干活的地方——存储完整的数据记录。

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃                叶子节点（Leaf Page）                       ┃
┠───────────────────────────────────────────────────────────┨
║                                                           ║
║  ┌───────────────────────────────────────────────────┐   ║
║  │  Record 1                                         │   ║
║  │  ┌──────────┬──────────────┬─────────────────┐    │   ║
║  │  │ Next(6B) │ Key(主键值)   │ Data(完整行)    │    │   ║
║  │  └──────────┴──────────────┴─────────────────┘    │   ║
║  ├───────────────────────────────────────────────────┤   ║
║  │  Record 2                                         │   ║
║  │  ┌──────────┬──────────────┬─────────────────┐    │   ║
║  │  │ Prev(6B) │ Key(主键值)   │ Data(完整行)    │    │   ║
║  │  └──────────┴──────────────┴─────────────────┘    │   ║
║  ├───────────────────────────────────────────────────┤   ║
║  │  Record 3 ...                                    │   ║
║  └───────────────────────────────────────────────────┘   ║
║                                                           ║
║  ←←←←←←←←←←←← 双向链表指针 ←←←←←←←←←←←←←←←              ║
║  prev_page ←──【当前Leaf】──→ next_page                      ║
║                                                           ║
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

  聚簇索引（Clustered Index）:
  ┌──────────────────────────────────────┐
  │ Key = 主键值  │ Data = 完整行记录     │  ← 数据就在叶子节点里
  └──────────────────────────────────────┘

  二级索引（Secondary Index）:
  ┌──────────────────────────────────────┐
  │ Key = 索引列值 │ Data = 主键值(回表用) │  ← 还需要回表查聚簇索引
  └──────────────────────────────────────┘

📝 单条记录的存储格式（Record Format）

每条记录在页内的物理存储结构：

┌──────────────────────────────────────────────────────────────────┐
│                        一条记录 (Record)                          │
├────────────┬──────────────┬────────────┬──────────────────────────┤
│  变长字段   │   NULL标志位  │  记录头信息  │      列数据 (Column Data)  │
│  列表长度   │   (NULL BM)  │ (Rec Header)│                           │
│  (可变)     │  (1~32字节)  │ (固定5字节)  │       (根据表定义变化)      │
├────────────┼──────────────┼────────────┼──────────────────────────┤
│ • 如果有    │ • 每个可为NULL│ • next_record(偏移量)                 │
│   变长字段  │   的列占1bit  │ • n_owned(slot归属)                  │
│   则记录各  │ • 位图逆序排列│ • heap_no(堆位置)                    │
│   变长字段  │              • • n_fields(列数)                     │
│   的字节长度│              • • record_type(普通/节点指针/BLOB等)    │
│   占1~2字节 │              • • status(是否被删除/首条记录标记)      │
└────────────┴──────────────┴────────────┴──────────────────────────┘

示例：表 user(id INT, name VARCHAR(20), age INT)
插入记录 (1, "张三", 25):

┌──────────┬──────────┬──────────────────────────────┬───────────────────┐
│ 变长列表  │ NULL位图  │        Record Header         │    Column Data     │
│          │          │                              │                   │
│ 02(UTF8  │ 00(无不  │ 38 00 00 00 10 01           │ 01 00 00 00( id=1)│
│  名字占2  │ 为NULL)  │ ↑next_rec↑n_own↑heap_no     │ E5 BC A0 E4 B8 89 │
│ 字节)     │          │ ↑n_field↑rec_type↑status    │ (name="张三")     │
│          │          │                              │ 19 00 00 00(age=25)│
└──────────┴──────────┴──────────────────────────────┴───────────────────┘

节点大小计算 — 一个页到底能存多少？

这是最关键的计算：一个16KB的页，到底能放多少个key？决定了B+树有多高、查询多快。

🧮 非叶子节点容量计算

假设主键类型为 BIGINT（8字节）：

一条非叶子记录 = 6字节(Page指针) + 8字节(Key值) = 14 字节

计算过程：

• 页总大小 = 16384 字节 (16KB)

• 固定开销 = FileHeader(38) + PageHeader(56) + Infimum+Supremum(~40) + Trailer(8) ≈ 142 字节

• 有效可用空间 ≈ 16384 - 142 = 16242 字节

• 可存储记录数 = floor(16242 / 14) = ≈ 1160 条

✅ 即：每个非叶子节点最多有 1160 个 key → 1161 个子指针
→ 这就是所谓的「m = 1170」左右（m阶B+树）

主键类型	Key大小	单条记录	每页记录数
INT (4B)	4	10	≈ 1624
BIGINT (8B)	8	14	≈ 1160
VARCHAR(20)	~22*	~28	≈ 580
VARCHAR(255)	~257*	~263	≈ 61

* VARCHAR还需要额外存储变长字段长度（1~2字节），这里估算含长度前缀

📊 叶子节点容量计算

叶子节点存的是完整记录，容量取决于单行数据大小。

假设一张典型业务表，单行约 1KB：

每页可存行数 = floor(16242 / 1024) = ≈ 15 行

不同行大小的对比：

单行大小	每页行数	场景举例
128 B	≈ 126 行	窄表（少量INT列）
512 B	≈ 31 行	中等宽度表
1 KB	≈ 15 行	常见业务表
4 KB	≈ 3 行	宽表（大TEXT/BLOB）
8 KB+	1~2 行	超宽行（溢出页）

🌳 树高度计算 — 决定查询IO次数

以 BIGINT 主键、每页15行为例，算一下不同数据量的树高：

      🎯 核心结论：

      • 1层树：数据 ≤ 15行 → 1次IO（根即叶）

      • 2层树：数据 ≤ 15 × 1160 ≈ 1.74万行 → 2次IO

      • 3层树：数据 ≤ 15 × 1160² ≈ 2018万行 → 3次IO

      • 4层树：数据 ≤ 15 × 1160³ ≈ 234亿行 → 4次IO

      绝大多数应用场景下，B+树只有 3 层！这就是为什么主键查询这么快。

B+树构建流程 — 从空树到平衡

B+树的构建本质上是有序插入 + 自平衡分裂的过程。我们一步步来演示。

📥 插入操作完整流程

Step 1: 定位目标叶子节点

从根节点出发，逐层比较Key值，选择合适的子指针向下走，直到到达叶子节点层。这个过程就是「查找插入位置」，时间复杂度 O(log N)。

Step 2: 在叶子节点中找到正确位置

叶子节点内部，记录按Key有序排列。通过页目录（Slot Directory）进行二分定位，确定新记录应插入哪个槽位之后。

Step 3: 插入记录

将新记录写入 User Records 区域（如果Free Space足够）。更新页目录中的槽位信息，维护记录间的链表关系。

Step 4: 检查是否溢出

判断当前叶子节点是否已满（User Records + 新记录 > 页可用空间）。如果未满，插入完成 ✅

Step 5: 节点分裂（如已满）

如果已满，触发分裂操作：创建新节点，将一半记录迁移到新节点，中间Key提升到父节点。递归检查父节点是否也需要分裂（可能级联到根）。

✂️ 节点分裂（Split）— B+树保持平衡的关键机制

当一个节点（叶子或非叶子）的记录数达到上限时，就需要分裂。

        分裂规则总结：

        1️⃣ 将满节点中的记录按中间位置分成两半

        2️⃣ 左半部分留在原节点，右半部分复制到新创建的节点

        3️⃣ 中间那个Key（分隔键）提升到父节点作为新的索引项

        4️⃣ 更新父子指针、叶子间链表关系

        5️⃣ 若父节点也满了 → 递归向上分裂，直到根节点（根分裂则树高+1）

🎬 动态构建演示

点击按钮，逐步观看一棵B+树的构建过程（m=3，每个节点最多2个key / 3个指针）：

准备就绪，点击开始

B+树查询流程 — 从SQL到磁盘IO

当执行 `SELECT * FROM user WHERE id = 888` 时，MySQL底层发生了什么？

🔍 等值查询（Point Query）

以查询 Key = 50 为例：

① 加载根节点（第1次IO）

从磁盘读取根节点页（常驻内存的可能跳过）。比较 50 与根节点各Key：30 < 50 < 70 → 选择 P1 指针

② 加载中间层节点（第2次IO）

P1指向的内部节点加载。比较：40 < 50 < 60 → 选择 P1 指针继续向下

③ 加载叶子节点（第3次IO）

到达叶子节点层。在叶子节点内通过页目录二分查找定位到 Key=50 的记录

④ 返回结果

找到匹配记录，返回给SQL引擎。如果是聚簇索引直接返回行数据；如果是二级索引拿到主键后再回表

📊 范围查询（Range Scan）

以查询 `WHERE id BETWEEN 30 AND 65` 为例：

① 定位起始位置

像等值查询一样，先找到 Key≥30 的第一条记录所在的叶子节点

② 顺序扫描

在该叶子节点内顺序遍历 ≥30 且 ≤65 的记录

③ 跨节点追踪

当前叶子扫完后，通过双向链表的 next 指针跳到下一个叶子节点继续扫描

④ 终止条件

遇到 Key > 65 的记录或到达链表末端时停止，返回所有符合条件的记录集合

🎬 查询路径动态演示

点击按钮模拟在以下B+树中查找 Key = 的过程：

点击开始搜索演示

B+树 vs 其他索引结构对比

为什么数据库最终选择了B+树？让我们横向对比。

⚖️ 四大数据结构全面对比

特性	B+树	B树	Hash索引	二叉搜索树
等值查询	O(log N) ✓	O(log N) ✓	O(1) 最佳	O(log N) 平均 / O(N) 最差
范围查询	O(log N + K) ✓✓	O(log N + K)，但需中序遍历复杂	✗ 不支持	O(K)，但可能退化
排序 / ORDER BY	✓ 天然有序	△ 需额外遍历	✗ 无序	△ 中序遍历
树的高度	极矮（3~4层）	较高（同数据量更高）	N/A	可能退化到 O(N)
磁盘IO次数	3~4次（海量数据）	更多（节点含数据，扇出低）	1~2次	不可控
空间利用率	较高（~75%）	较低（~50%）	取决于负载因子	取决于平衡性
适用场景	数据库索引首选	文件系统	等值查询为主（Memcached等）	内存数据结构

🆚 B+树 vs B树：核心区别可视化

⚠️ B树: 非叶子节点也存数据(D) → 扇出低 → 树更高 ✅ B+树: 非叶子只存Key → 扁平树 → IO少 + 叶子链表支持范围查询

💡 B+树的六大设计优势

① 极低的树高度
非叶子节点不存数据，单个页可存上千个索引项 → 海量数据只需3~4次IO

② 范围查询天然高效
叶子节点双向链表 → 获取起点后顺序扫描即可，无需回溯上层

③ 查询性能稳定
所有查询都必须走到叶子 → 所有查询IO次数相同，不会因命中非叶子而波动

④ 缓存命中率极高
非叶子节点纯索引、数据量小 → 整棵树的上层可以全部缓存在 Buffer Pool 中

⑤ 全局有序天然支持
叶子链表天然有序 → ORDER BY / GROUP BY / MIN() / MAX() 直接利用索引顺序

⑥ 页对齐友好
节点大小 = 数据库页大小(16KB) → 一次IO正好读入一个节点，无浪费

InnoDB中的B+树实战细节

理论结合实际——看看MySQL InnoDB是如何具体使用B+树的。

🗄️ 聚簇索引（Clustered Index）

InnoDB中，表数据本身就是按B+树组织存储的：

  表: CREATE TABLE user (
    id BIGINT PRIMARY KEY,
    name VARCHAR(50),
    age INT
  );

  聚簇索引（以 id 为主键）:

  ┌──────────────┐
  │    Root      │  非叶子页: [id] + [子页指针]
  ├──────────────┤
  │  Internal    │  非叶子页: [id] + [子页指针]
  ├──────────────┤
  │  Leaf Pages  │  叶子页: [id] + [完整行数据(name,age,...)]
  │  ↔↔↔↔↔↔↔↔  │         双向链表连接
  └──────────────┘

  特点：
  ✓ 数据文件(.ibd) 就是 B+树 的叶子节点
  ✓ 叶子节点存储完整的行记录
  ✓ 一张表只能有一个聚簇索引（主键索引）
  ✓ 查询通过主键 → 直接拿到完整行数据（不需要回表）

📑 二级索引（Secondary Index）

除了主键外创建的其他索引，都是二级索引：

  CREATE INDEX idx_name ON user(name);

  二级索引 B+树:

  ┌──────────────┐
  │    Root      │  非叶子页: [name] + [子页指针]
  ├──────────────┤
  │  Internal    │  非叶子页: [name] + [子页指针]
  ├──────────────┤
  │  Leaf Pages  │  叶子页: [name值] + [主键id值]
  │  ↔↔↔↔↔↔↔↔  │         双向链表连接
  └──────────────┘

  ⚠️ 回表（Lookup / Bookmark Lookup）:
  SELECT * FROM user WHERE name = '张三';

  1. 通过 idx_name B+树 → 找到 name='张三' → 得到主键 id=42
  2. 通过 id=42 回到 聚簇索引 B+树 → 找到完整行数据
  
  → 二级索引查询 = 两次 B+树 查找（覆盖索引除外）

  💡 覆盖索引优化:
  SELECT id, name FROM user WHERE name = '张三';
  → 二级索引叶子已经包含 id 和 name → 无需回表！

⚡ 性能优化关键要点

要点	说明	建议
主键设计	主键越小 → 非叶子节点存越多key → 树越矮 → IO越少	优先使用 `BIGINT AUTO_INCREMENT` 或雪花算法，避免使用 UUID/长字符串做主键
索引选择性	选择性 = distinct值数 / 总行数，越接近1越好	选择性低的列（如性别、状态）不适合单独建索引
最左前缀	联合索引 (a,b,c) 可以加速 a, (a,b), (a,b,c) 的查询	将高选择性列放在联合索引最左边
覆盖索引	查询字段全部包含在索引中 → 无需回表	SELECT 时尽量只选索引中的字段
避免索引失效	函数运算、隐式转换、LIKE '%xx' 都会让索引失效	WHERE 条件中对索引列不要使用函数或表达式

🔄 B+树的维护操作（除分裂外）

🗑️ 删除（Delete）

逻辑删除先标记记录为"已删除"（打删除标记），物理删除由 purge 线程异步完成。若节点记录太少会触发合并（Merge）或借用（Redistribute）兄弟节点记录。

✏️ 更新（Update）

若更新的列不在索引中 → 原地修改。若更新的列是索引键值 → 先删除旧记录再插入新记录（等同于 Delete + Insert）。

🔀 合并（Merge）

当相邻两兄弟节点记录都很少时（合计未超过阈值），合并为一个节点，释放的空间还给 Free Space。同时从父节点移除对应的分隔Key。