B+ 树：结构、分裂与页 IO

一句话定义

B+ 树（B+ Tree）是一种多路平衡搜索树：内部节点只存键与子指针、全部数据在叶子节点，叶子间用链表串联，使等值与范围查询都能在「树高次数的页读」内完成。

为什么重要

它是绝大多数 OLTP 数据库索引的默认结构（InnoDB 聚簇/二级索引、PostgreSQL 主索引均为 B+ 树变体），不懂 B+ 树就看不懂任何执行计划。
「树高决定 IO 次数」这一句话能解释联合索引顺序、覆盖索引、自增主键等一系列工程结论的「为什么」。
与 LSM 树（kp-021）构成存储引擎读写放大的两大流派，是选型讨论的基本盘。

前置知识

kp-001（内模式与页的概念）。

核心概念

页（Page）：磁盘与内存交换的最小单位，InnoDB 默认 16KB；B+ 树每个节点恰好占一页。
扇出（Fanout）：一个内部节点的子指针数；千量级扇出让三层树即可索引上亿行。
树高（Height）：根到叶的层数；一次点查的随机页读次数 ≈ 树高。
聚簇索引（Clustered Index）：叶子存整行数据，表即索引（InnoDB 主键）；二级索引（Secondary Index）叶子存「索引列 + 主键」，需要「回表」查整行。
叶子链表：支撑 BETWEEN、ORDER BY ... LIMIT 的顺序扫描。
写路径：插入从叶开始满则分裂（中点分裂、兄弟再平衡），删除空则合并或借键。

原理与机制

设扇出 f ≈ 1000、叶子每页放 100 行：两层树容纳 10 万行，三层约 1 亿行。因此一次点查通常只需 3~4 次页访问，而根与内部节点常驻缓冲池（kp-022），真实磁盘 IO 往往只有 1 次左右——这就是 B+ 树「矮胖」设计的全部动机。相比二叉树（每节点 1 键，亿行数据高约 27 层），多路扇出把高度压缩了约一个数量级。随机写主键（如 UUID）会让新行落在树的任意位置，页频繁分裂且缓存命中率低；自增主键总是追加到最右叶子，分裂少、缓存热，这是「主键尽量自增有序」的机制级原因。二级索引查询「索引列命中 → 取主键 → 回聚簇索引取行」，回表次数 = 命中行数，这正是 kp-011 覆盖索引优化的出发点。

实例或案例

SELECT * FROM users WHERE user_id = 88（user_id 为主键）：沿根 [1|1000|100000] 判定走第二层页 [50|200|1000]，再到叶子页内二分定位行，共约 3 次页访问。而 WHERE age = 25（age 无索引）需全表扫描所有叶子页，代价差 4~5 个数量级——同一张表、同一台机器，仅因索引不同性能差百万倍。

常见误区

认为索引越多越好：每个索引都是一棵独立的 B+ 树，写入时要同步维护全部索引，且占存储，写多读少场景是净负担。
用 UUID 随机主键「更安全」：安全性应靠权限与脱敏（kp-032），随机主键带来的是持续的页分裂与碎片。
以为 B+ 树查询是「内存查找」：树高层的每次未命中缓存都是一次随机磁盘读，SSD 时代仍是执行计划里最贵的部分。

自测题

为什么 B+ 树数据全放叶子而 B 树可以放内部节点？答：数据上提会挤占内部节点的键空间、降低扇出、抬高树高；且范围查询在 B+ 树只需扫叶子链表，B 树则要中序回溯，代价高。
二级索引为什么需要回表，如何避免？答：二级索引叶子只存「索引列 + 主键」；避免方式是让查询所需列全部包含在索引里（覆盖索引，见 kp-011）。

公式或模型

容量估算：N ≈ (f)^(h-1) × m，N 行数、h 树高、f 扇出、m 每叶行数。取 f=1000、m=100：h=3 时 N ≈ 10⁸。随机点查 IO ≈ h − (常驻缓存层数)。

图示

B+ 树：内部节点只存键做路标，数据在叶子层，叶子链表支撑范围扫描

直观类比

B+ 树像图书馆的书架编号体系：每层楼（内部节点）只挂区间路标，真正放书的全在底层库房（叶子），库房之间有传送带（链表）——找一本书走三层路标，找「某区间所有书」沿着传送带走即可。

与其他知识点的关系

kp-011 把「树高与回表」翻译成联合索引设计规则；kp-012 用 EXPLAIN 验证索引是否被用上；kp-021 是读写放大上的对照流派；kp-022 解释为什么常驻缓存让实际 IO 低于树高。

前置知识点

相关知识点