DDIA 第 4 章学习复盘（中）：B 树
创建时间：2026-07-19；最近更新：2026-07-19
这是我读《数据密集型应用系统设计》（DDIA）第 4 章第二次的学习复盘。本以为本次可以全部写完，发现内容还是太多了，于是将部分内容留到下次。
这次我们来接触另一种比较流行的数据库的存储结构，B 树。
B 树和 LSM 的根本区别一句话就能说完：B 树允许修改已写入磁盘的最小存储单元，LSM 只能新写。 原地覆盖 vs 只追加。LSM 的已写文件不可变，更新靠新文件取代旧文件。
B 树的最小存储单元叫页（page）。页类似于上篇的段，但有两个关键区别：页可以修改内容；页很小，通常只有 4KB，而段是 MB 级的，差了三个数量级。
这里我一度觉得 B 树是优于 LSM 的："可以修改"直接避免了 LSM 反复压实"逝去"数据的开销，也就不存在压实追不上写入、引擎被迫拒绝服务的风险。但先保留这个判断——后文会理解，"可以修改"本身是有代价的（页级写放大、随机写），而 B 树在写入过猛时同样会因脏页刷盘跟不上而停顿。代价没有消失，只是在不同的地方体现。
页和页之间靠引用连成一棵树。查一个 key，从根页开始，通过每一层页定位大致范围，快速缩小到指定页。终点叫做叶页（leaf page）——树最底层的页，里面不再有指向子页的引用，装的就是 key 和值本身。上层的页负责指路，叶页负责交付。
我们来看一个例子吧，用一棵两层的小树来演示，假设每页最多装 4 个值：
txt
根页 P： [ →A | 30 | →B | 60 | →C ]
叶页 A: [10, 20, 25, 28] ← 管"小于30"的一切，已满
叶页 B: [30, 42, 55] ← 管"30到60"
叶页 C: [60, 77, 90, 95] ← 管"60以上"的一切，已满最基础的插入场景，来了一个 key "57"，根据根和页的指定在目标叶页中添加即可。
txt
根页 P： [ →A | 30 | →B | 60 | →C ]
B: [30, 42, 55, 57]往满页插 26 ，同层分裂：
txt
P: [ →A | 25 | →D | 30 | →B | 60 | →C ]
A: [10, 20] D: [25, 26, 28]那如果父页也满了呢？父页也分裂成两个页，同时更新爷爷层级的指针，依次类推。如果一路分裂到树顶、树顶也满了——就新建一个树顶，原树顶降级为二级。
我们把上面那棵树推到临界状态：先插 29，D 变成 [25, 26, 28, 29]，已满；再插一个 70，C 满了分裂出新叶页 F，把 90 推给 P——现在 P 也满了：
txt
P: [ →A | 25 | →D | 30 | →B | 60 | →C | 90 | →F ]
A:[10,20] D:[25,26,28,29] B:[30,42,55,57] C:[60,70,77] F:[90,95]此时插 27：D 已满，分裂成 [25, 26, 27] 和 [28, 29]，把 28 往上推——但 P 也满了，P 只好也分裂，把中间的键 30 继续往上推——P 已经是根，头顶没人了，于是新根 R 诞生：
txt
R: [ →P | 30 | →Q ] ← 新根诞生
P: [ →A | 25 | →D | 28 | →E ] Q: [ →B | 60 | →C | 90 | →F ]
A:[10,20] D:[25,26,27] E:[28,29] B:[30,42,55,57] C:[60,70,77] F:[90,95]我一度以为"等深"最多是每个局部子树内部自己等深。但实际答案是所有叶页等深。为什么呢？
因为 B 树里根本不存在"往下长"。高度变化只有一个触发点：下层分裂把键一路上推到根，而根也满了。为了能让根永远保持对所有子树的掌控，需要老根分裂退位，新根上位。
不平衡压根没有产生的入口：某个子树想自己变深？它做不到，分裂完还是那么深。唯一能调整树高度的开关是那个全树共享的顶点。树不是被"维护"平衡的，而是从分裂规则而言，就不存在子树层级不一样的情况。
我想我们有必要回头放大看一下同层分裂：它不是写一个地方，而是要按顺序写三个页——① 把 A 原地覆盖成 [10, 20]；② 在新位置写出 D: [25, 26, 28]；③ 更新父页 P。
B 树"原地覆盖"这个操作好用但也危险，如果没有别的机制的情况下，在 ① 步骤结束的瞬间机器断电，会发生什么？
重启后查 key 28：P 只有指向 A 的引用 → 进 A → A 里只剩 [10, 20] → 返回"不存在"。
没错，数据丢了，并且操作不可逆。更关键的是，查询丢失 key 的 null 值会返回给应用，应用是真的会当作 null 处理。应用和数据库的协作基础就是默认数据库返回的一定是正确数据。如果不去核查所有的数据录入记录，甚至无法发现数据丢了。
对比一下 LSM 的断电场景：坏的只可能是那个没写完的新文件（残段），旧段从头到尾没被碰过、完好无损。所以处理方式简单粗暴，残段直接删掉，memtable 根据**预写日志（WAL）**重建即可。
B 树解决此问题的做法也是预写日志（WAL），不过写的内容有所区别：A 将被覆盖成什么、D 是什么内容、P 怎么改，三步全记下、落盘，然后才允许操作任何一个页。出问题直接根据日志重做即可。
调整写入顺序行不行？比如先写新页 D、最后才动 A 和 P。顺序确实能缩小危险发生的时间窗口，实际实现也会这么考虑——但 A 和 P 是两次独立的磁盘写，无法原子地同时完成，断电总能精确地插进两步之间。所以顺序优化不能替代 WAL，只能是辅助操作。
这里 WAL 记的不是"给 A 加一个 key"这种增量指令，而是"A 页的完整新内容是这 4KB"这种终态快照。区别在于：增量指令不能重复执行（'余额 += 100'重放两次就多加了一百；'余额 = 500'重放多少次都是 500）；终态快照可以无数次重放而结果不变。这个性质叫幂等。恢复流程也就非常简单：不诊断哪些页坏了，我保证你按照我记的来重做，就一定是对的。
这让我想起过去参与的一个项目。我们组对配置库做版本管理的方式是全量导出、上线时全量覆盖；隔壁组用增量提交。回滚时我们很方便——全量数据一次性覆盖运行即可，无论几遍都是对的；隔壁组出问题得找到基版、把后续所有增量逐次重放，比较麻烦。不过我们这么操作也有代价：几百张表一把覆盖，变化不可见，只能人肉确认版本对不对——用"恢复简单"换掉了"变更可审计"。实际上，我们组的做法肯定是不规范的，也不建议采用。工业数据库的做法是两种都要：关键时刻记全页快照保幂等，平时记增量省空间。
再补充一点：工业数据库并非只靠全页快照换幂等。增量日志也有标准的幂等化技巧——每个页头记录一个 LSN（日志序列号），重放时发现页上的 LSN 已不小于日志记录的 LSN 就跳过这条。PostgreSQL 的实际做法是混合式：每次 checkpoint（检查点，数据库周期性把内存脏页刷盘并在日志里做标记的时刻）后页的第一次修改记全页镜像（full page write，顺便防御"页只写了一半"的撕裂写），之后的修改记增量。
B 树存在问题吗？
写入放大：WAL 一遍 + 页本身一遍，至少两遍——而且期望和实际写入差距可能非常夸张：改 3 个字节，也得落盘整个 4KB 的页，放大一千多倍。
随机写：B 树的页由指针指引，散落在文件各处，改哪个页就得跳到哪里去写，这种模式叫随机写；LSM 整段顺序写出，叫顺序写。从磁盘的物理性质来说，磁盘特别是机械磁盘更偏好顺序写（磁头不用来回跳），SSD 上差距缩小但仍然存在。两边都写得多，但多得不一样：B 树整页重写、分散；LSM 压实反复搬、连续。
LSM 和 B 树没有全能冠军，只有特定场景的赢家。
- 写多、能容忍读延迟波动 → LSM。日志、消息队列、监控数据这类频繁写入的场景。
- 读多、要延迟稳定（含范围查询） → B 树。这是关系数据库的主战场，MySQL、PostgreSQL 的默认索引都是它。LSM 支持范围查询，只是要跨段归并、延迟不如 B 树稳定。
第 4 章还剩下一（二？）部分，后续我将继续带来学习复盘分享。
如果内容有错，欢迎指出，一起讨论。