第 18 章 B 树 (B-Trees)
核心结论
-
磁盘 I/O 模型：磁盘随机访问远慢于内存（毫秒 vs. 纳秒，差 5+ 个数量级）；B 树通过大分支因子让单次 I/O 读一整个节点（页面），将树高降到对数 O(log_t n)。
-
B 树定义：度为 t（t ≥ 2）的 B 树满足——根至少 1 键、内部节点 [t−1, 2t−1] 键故 [t, 2t] 子树、所有叶子同深度。t=2 即 2-3-4 树。
-
高度上界：n 键 B 树高 \(h \leq \log_t \frac{n+1}{2}\)；分支因子 1000 时高 2 即可存 10 亿键。
-
基本操作：SEARCH O(t·log_t n) CPU + O(log_t n) 磁盘；INSERT 单趟向下（预分裂满节点）O(h) 磁盘；DELETE 通过旋转/合并避免回溯 O(h) 磁盘。
-
与红黑树对比：同 Θ(lg n) 但底数是 t（可达数百）；实操中磁盘访问数从 5-10 降到 2-3，差距极大。
-
变体：B+ 树（卫星数据全部在叶子、叶子串成链表）；B* 树（节点至少 2/3 满）；Bc 树（数据仅在叶子）。
|
本章主旨
本章是面向磁盘存储的平衡搜索树——B 树。核心思想是「大节点（=一页磁盘）」「少层数」「预分裂以保证单趟向下」。B 树通过把节点大小调到磁盘页大小（典型 2¹¹–2¹⁴ 字节），让每次 I/O 读完整页；分支因子自然提升到 50–2000，树高降到 2–4，使亿级数据可在 2–3 次磁盘访问内定位。B 树是数据库（MySQL InnoDB、PostgreSQL）和文件系统（ext4、NTFS、XFS）的核心索引结构。第 18.1 定义与高度分析、18.2 插入（分裂 + 单趟向下）、18.3 删除（合并 + 旋转 + 例外回溯）三节层层递进。 |
一、核心概念
本章围绕 5 个核心概念展开：先建立磁盘 I/O 模型与 B 树定义（18.1），再深入查询、插入（18.2），最后讨论删除的复杂性（18.3）。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
磁盘 I/O 模型 |
节点等于磁盘页 (2¹¹–2¹⁴ 字节)；访问时间分摊到页内多个 key 的访问 — B 树的核心动机。 |
DISK-READ / DISK-WRITE 显式调用；根常驻内存；CPU 时间 ∝ t（节点内 key 数），磁盘时间 ∝ h。 |
B 树结构与最小度 t |
t ≥ 2 的 B 树：非根节点 [t−1, 2t−1] 键 / [t, 2t] 子树；叶子等高。t 越大 → 分支越大、树矮。 |
§18.1;键单调排列；x.key_i 充当分隔 x.c_i 与 x.c_{i+1} 的「路标」。 |
B-TREE-SEARCH |
节点内线性扫描 + 按 high/low 决定递归子树；O(t h_d) CPU + O(h_d) 磁盘（h_d = 树高）。 |
§18.2 伪代码 (lines 1-9);若内部节点二分搜索则 O(lg n) CPU，但磁盘访问不变。 |
B-TREE-INSERT 单趟向下 |
自顶向下搜索时遇满节点立即分裂；保证递归进入的子节点不满 → 单趟、无回溯。 |
§18.2 B-TREE-SPLIT-CHILD + B-TREE-INSERT-NONFULL;根满时新建根使树增高 — B 树唯一增高方式。 |
B-TREE-DELETE |
删除时保证后续递归的节点至少有 t 个键（多余 1）；否则借兄弟或合并；可能特殊处理根节点的「塌陷」。 |
§18.3 用 6 种情形；根节点变为空时让唯一子节点接管 — B 树唯一降低方式。 |
二、详细笔记
2.1 磁盘 I/O 模型与 B 树定义
What：B 树是为磁盘设计的平衡搜索树——节点大小等于磁盘页（典型 2¹¹–2¹⁴ 字节），分支因子随 t 而非固定 2；高度 O(log_t n)。
Why：磁盘随机访问 ≈ 8 ms，内存 ≈ 50 ns，差 5+ 个数量级（CLRS §18.1）；算法时间复杂度必须按磁盘页访问次数而非 CPU 指令数计——B 树正是为此而生。
How：
| 属性 | 形式化 |
|---|---|
最小度 t |
根至少 1 键；其他节点 [t−1, 2t−1] 键；内部节点 [t, 2t] 子树 |
高度上界 |
\(h \leq \log_t \frac{n+1}{2}\)（定理 18.1） |
每页访问 |
DISK-READ(x) 把节点 x 调入内存，DISK-WRITE(x) 写回 |
CPU 时间 |
节点内线性扫描 → O(th) = O(t log_t n) |
分支因子 |
实际常 50–2000（视 key 大小） |
When：数据量超过内存（如数据库表、文件系统目录）；需随机访问 + 顺序扫描；更新（插入 / 删除）与查询混合。
Example：CLRS 图 18.3——t=1000（节点最多 1999 键 / 2000 子树）的 B 树高 2 可存超过 10⁹ 键；根常驻内存 → 任何查询 ≤ 2 次磁盘读。
2.2 B-TREE-SEARCH 与节点分裂
What：B-TREE-SEARCH 在节点内线性扫描 + 按 high/low 选子树递归；B-TREE-SPLIT-CHILD 把满节点（2t−1 键）一分为二，中间键上提到父节点。
Why：插入先找到叶子位置，但满叶子无法直接插入——必须分裂；但若父节点也满，分裂会向上传播；「预分裂」策略使单趟向下即可完成。
How：
| 操作 | 关键点 |
|---|---|
B-TREE-SEARCH (lines 1-9) |
节点内 while 循环定位 i；DISK-READ(x.c_i) 后递归；返回 (y, i) 或 NIL |
B-TREE-SPLIT-CHILD (lines 1-20) |
y = x.c_i 满；z = ALLOCATE-NODE；z 取 y 的最大 t−1 键 + t 子树；y.key_t 上提 |
B-TREE-CREATE |
分配根节点，T:root = ALLOCATE-NODE；n=0 |
B-TREE-INSERT |
根满时新建根 → 高度 +1；递归 B-TREE-INSERT-NONFULL（非满） |
B-TREE-INSERT-NONFULL |
遇满子节点立即分裂 → 递归必进入非满节点；叶子直接插入 |
When：插入操作的标准实现；与 search 配合构成 B 树基本 API 的两个核心。
Example：CLRS 图 18.5 (t=4) —— 节点 y = {N,P,Q,R,S,T,U,V,W} 有 8 键 (2t−1)，按 t=4 分裂：左侧 y = {N,P,Q,R}，右侧 z = {T,U,V,W}，中间键 S 上提到父节点。
2.3 单趟向下插入
What：插入时自顶向下搜索路径中遇到每个满节点立即分裂，保证递归进入的子节点始终不满 → 不需要「回溯」处理溢出。
Why：B 树的优雅之处——传统自顶向下插入在叶子处分裂后会回溯到父节点（父节点可能因上提而变满）；预分裂消除了回溯，使树只增长（顶部）不增长后再向下。
How：
-
B-TREE-INSERT(T, k)：
-
若 T.root 满 → 新建 s 作为根，原根作为 s.c₁ → B-TREE-SPLIT-CHILD(s, 1) → 树高 +1。
-
否则递归 B-TREE-INSERT-NONFULL(T.root, k)。
-
-
B-TREE-INSERT-NONFULL(x, k)：
-
找 i = x.n 并比较；若 x 为叶子 → 直接插入；否则 DISK-READ(x.c_i)。
-
关键步骤：若 x.c_i 满 → B-TREE-SPLIT-CHILD(x, i)，并按 k 与新上提键的比较调整 i。
-
递归到 x.c_i。
-
-
磁盘访问：O(h)，其中 h = \(\lfloor \log_t \frac{n+1}{2} \rfloor\)。
-
CPU 时间：O(th) = O(t log_t n)；节点内循环 O(t) 步。
When：插入频繁；不需要撤销 / 回滚；典型 KV 存储的写路径。
Example：CLRS 图 18.6 (t=4) —— 根 {F,H,L} 插入新键 P 时满，分裂为 s = {H}、c₁ = {F}、c₂ = {L,…}；树高 +1。
2.4 B-TREE-DELETE 的复杂性
What：删除键时通过 6 种情形处理——保证递归进入的节点至少 t 个键（除了根），避免「向下删到一半发现子树键不够」的回溯。
Why：删除比插入复杂——删除内部节点的键要用后继填补，且补上来的键可能让子树变空；必须保证处理完后整棵树仍满足 B 树不变量。
How：
| 情形 | 处理 | 适用 |
|---|---|---|
1 |
叶子直接删 |
x 是叶子 |
2a |
用前驱 (左子树最大键) 填补后递归删除前驱 |
x 是内部节点，左子树 ≥ t 键 |
2b |
用后继 (右子树最小键) 填补后递归删除后继 |
x 是内部节点，右子树 ≥ t 键 |
2c |
左右子树均仅 t−1 键 → 合并 + 删键 |
x 是内部节点，子树都「临界」 |
3a |
左兄弟 ≥ t 键 → 从左兄弟借一个 |
y 子节点仅 t−1 键，左兄弟够借 |
3b |
右兄弟 ≥ t 键 → 从右兄弟借一个 |
y 子节点仅 t−1 键，右兄弟够借 |
3c |
左右兄弟均仅 t−1 键 → 与兄弟合并 |
y 子节点 + 兄弟均不够借 |
根的特殊情形：递归删除中若根变为「无键且单子」，则让唯一子节点接管（树高 −1）。
When：与查询/插入混合的通用 API；磁盘页换入换出时需配合预读策略（如 ORDER BY 优化）。
Example：CLRS 图 18.8 (t=3) —— 删除 F（情形 1）、删除 M（情形 2a，用前驱 L 替换）、删除 G（情形 2c：合并到 DEGJK 子树）。
2.5 B 树变体与工程权衡
What：B 树有许多工程变体：B+ 树（数据全在叶子、叶子链表）适合范围查询；B* 树（节点至少 2/3 满）提高空间利用率；Bc 树（数据仅在叶子）让内部节点纯索引。
Why：变体针对不同负载设计——数据库 OLTP 用 B+ 树（范围查询 + 高扇出），日志结构存储用 LSM 树（批量写优化），但基本原理一致。
How：
| 变体 | 关键差异 |
|---|---|
适用负载 |
B+ |
数据全在叶子，叶子链表 |
范围查询、OLTP 数据库 |
B* |
节点至少 2/3 满，兄弟满时才分裂 |
高空间利用率 |
Bc |
数据仅在叶子，内部节点无卫星信息 |
最大化分支因子 |
LSM |
多层排序字符串表，定期合并 |
When：实际系统往往不是「纯 B 树」——例如 InnoDB 用 B+ 树 + adaptive hash index；选型需考虑读写比、范围查询比例、空间预算。
Example：PostgreSQL 用 B+ 树作为默认索引；MySQL InnoDB 表数据本身就是 B+ 树组织（clustered index）；SQLite 用 B 树。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 18 章 B 树))
磁盘模型
DISK-READ
DISK-WRITE
页=节点
根常驻内存
B树定义
最小度t
节点[t-1,2t-1]
叶子等高
高度上界
logt底
分支50-2000
高2可存亿键
SEARCH
节点线性扫描
O(t h) CPU
O(h) 磁盘
INSERT
预分裂满节点
单趟向下
根满则分裂生根
DELETE
6种情形
保证子节点≥t
根塌陷特例
变体
B+树数据在叶
B*树2/3满
LSM写优化
工程应用
InnoDB
PostgreSQL
文件系统
== 五、重点与易错点
. B 树 ≠ B+ 树 ≠ B* 树 ≠ 二叉搜索树——区分清楚（CLRS 主要讲 B 树；其他变体在工程中常见）。
. DISK-READ / DISK-WRITE 在伪代码中显式写出，与纯 CPU 算法（如 BST）不同——不要把磁盘访问数等同于 CPU 时间。
. 节点大小选择：太大 → 浪费带宽（读取空键多）；太小 → 树高增加（多次 I/O）。经验：略小于磁盘页，或用缓存行对齐。
. 「预分裂」是 B 树的关键技巧——传统「到叶子再分裂并向上回溯」会因父节点满而引入额外分裂；预分裂保证递归永进入非满节点。
. t ≥ 2 是 B 树的最小度；t=1 不允许（会破坏「子树数 = 键数 + 1」）。
. 删除的 6 种情形：2a / 2b / 2c / 3a / 3b / 3c；不要把情形搞混——情形 2 和情形 3 的区别是「内部节点 vs. 叶子」。
. 根的特殊地位：根可少于 t 个键（B 树的不变量例外）；其他节点必须 ≥ t−1。
. 高扇出 B 树的实际高度 = Θ(lg_t n)；t=1000 时 n=10⁹ 高 2；这就是 B 树「亿级数据 ≤ 3 次 I/O」的来源。
. 在 CLRS 中 B 树专门用于磁盘；在内存场景二叉树（如红黑树、AVL）更优——选型要看数据是否超内存。
. B 树的删除操作比插入复杂得多；许多生产数据库的索引不支持原地删除，而是用 tombstone / 延迟合并。
. B 树的并发访问复杂：SILO / Bw-tree 用 latch-coupling / 乐观并发；纯 B 树在多线程下需细粒度锁设计。
. 「非叶节点也带卫星数据」是 CLRS 的原始 B 树定义；B+ 树把所有数据放到叶子是为了让范围查询只需在叶子链表顺序扫描。
. CLRS 给出的 DISC-READ/DISK-WRITE 抽象简化为「一次访问调入一整页」；现代 SSD 则应按 4 KB / 8 KB 页对齐设计。