B-Tree 变体

一句话

这一章不是介绍四个新数据结构，而是把「B-Tree = 按页组织 + 原地修改 + 加闩保护」这个捆绑拆开，逐项替换掉。核心命题只有一句反直觉的话：B-Tree 的成本重心早就从「查一次要跑几趟盘」挪到了「改一次要写多少字节、要让多少线程等」——所以本章所有变体，几乎没有一个是为了让查找更快，它们都是为了让写更少、等更短、对闪存更友好。而它们共同的第一步动作惊人地一致：不再原地修改。

Glossary · 术语表

坐标

本章位于 Part I「存储引擎」的第 6 章。Ch2–Ch4 建起了教科书式的 B-Tree（结构、页格式、分裂与合并的工程细节），Ch5 用页缓存 + 预写日志 + 并发控制让它扛住崩溃与并发。这一章是同一条线上的变奏：既然经典 B-Tree 的痛点都源自「原地修改」，那把这个前提换掉会长出什么样子。它同时是通向下一章的桥——Ch7 的 LSM-Tree 就是把「不原地改、攒批顺序写」推到极致；而 Bw-Tree 用到的兄弟指针来自 Ch5 提过的 Blink-tree，MVCC 快照的思路则和 Ch5 的并发控制一脉相承。

这章要解决什么

经典 B-Tree 在「找」这件事上几乎无可挑剔：10 亿条记录、扇出几百的树高也就 4 层，一次点查最多几趟 I/O。问题全在「改」的那一侧，可以摊成三笔账。

第一笔，写放大。改一条 100 字节的记录，磁盘上最少重写一个 8–16 KB 的页——页级放大就有 80–160 倍。这还只是开头：为防止「页写到一半断电」留下半新半旧的撕裂页（torn page），引擎还得交税——MySQL InnoDB 的双写缓冲（doublewrite buffer）把同一页写两遍，PostgreSQL 的 full_page_writes 要求每次检查点后第一次改某页时把整页塞进 WAL。再往下，固态盘按擦除块（常见几 MB）管理，零散随机写诱发内部搬迁，又叠一层。「原地更新」不是免费的默认选项，它是一串税单的源头。

第二笔，并发。Ch5 的闩蟹行已经把根节点持闩时间压得很短，但压不掉一个事实：每次查找和修改都必须从根开始，而根只有一个。单机 64–128 核的今天，瓶颈不再是磁盘寻道，而是热点页上的缓存行来回弹跳——一个核动了根上的闩，其他核缓存里的副本就作废。越是内存驻留、越是多核，加闩本身的开销占比越高。

第三笔，碎片与空间。节点通常只装到七成满，分裂后一度只有五成；反复增删之后，页内空洞与页间顺序错乱一起累积，顺序扫描从「顺着读」退化成「到处跳」。

不解决会怎样？也没怎样——几十年主流数据库都这么活着。但三种场景里这三笔账会变成致命伤：写密集负载（吃掉带宽与 SSD 寿命）、多核内存数据库（加闩开销压过一切）、要求崩溃后零恢复时间的嵌入式场景。本章的变体分别冲着它们去。

核心内容，讲透

一、写时复制 B-Tree：把「改」变成「换指向」

思路一句话：任何页都不再被覆盖。要修改某个叶子，就复制一份、改在副本上；副本换了地址，父节点里那个指针就得跟着改——于是父节点也得复制一份……一路复制到根（这叫路径拷贝）。最后把「树根在哪」这一个指针原子地切到新根上。切换之前，整棵新树对外不存在；切换完成的一瞬间，它整个生效。没有中间态，也就不需要日志来擦屁股。

它顺手买一送三。其一，崩溃安全免费：根指针要么旧要么新，磁盘上永远是一棵自洽的树，不需要 redo / undo，重启即可用。其二，天然 MVCC：读事务开始时抓住当时的根，之后写者怎么折腾都碰不到它，读路径上一把闩都不用加。其三，读可以直接走内存映射：LMDB 把整个数据库 mmap 进地址空间，取数据直接从映射内存返回，不 malloc 不 memcpy。

代价在三处，都不轻。其一，单次写放大更大：树高 4 的树改一条记录要新写 4 页，100 字节付出 32–64 KB。其二，写者只能有一个：路径拷贝 + 换根天然串行，好处是写者永不死锁，坏处是写吞吐锁死在单线程。其三，旧页回收：换下来的页要进空闲页表等复用，而只要还有一个老读事务钉着旧根，那批页就一页也不能复用——一个跑了半小时的只读事务就能让文件肉眼可见地膨胀，和 PostgreSQL 里长事务拖住 vacuum 是同一个病。

二、抽象节点更新与惰性 B-Tree：让内存形态和磁盘形态分家

写时复制解决了原子性和读并发，却没解决写放大——改一个字节仍要重写整页。惰性（lazy）路线换了个角度：既然重写整页贵，就别每次都重写；把更新先攒在内存里，攒够了再算出一个新页。

关键是承认一件事：页在内存里的形态，没必要等于它在磁盘上的形态。磁盘形态要紧凑、能顺序扫描，内存形态则可以用指针、跳表这类对 CPU 友好的结构。WiredTiger（MongoDB 的默认存储引擎）就是典型：磁盘上的页镜像读进内存后保持只读，新的插入与更新挂进这一页附带的更新链，读取时把「基础镜像 + 更新链」合起来看；等到这页被驱逐或做检查点时，才执行一次归并（reconciliation），把两边算成一个干净的新页写出去。

算一笔账就明白它值在哪：如果一页在两次检查点之间被改了 50 次，经典做法是把这页刷 50 次（或至少多次），惰性做法只在归并时写一次——写放大按更新链长度摊薄。代价是读路径变重（要合并两处数据）、内存里驻着尚未落盘的更新（崩溃时靠预写日志补回）。同一路线上还有一支惰性自适应树（LA-Tree）：把缓冲区挂在子树上而不是单页上，缓冲满了就把更新级联下推到下一层的缓冲区，一路推到叶子——已经很接近下一章 LSM 的味道了。

三、FD-Tree：为固态盘重排的形状

前两招都还在「一棵树」的框架里。FD-Tree 换了形状，动机非常具体：闪存上随机写远比顺序写贵（不能就地改写，必须整块擦除后重写，零散小写会诱发内部搬迁）。既然如此，那就把所有写变成顺序写。

结构分两部分：顶上是一棵很小的 B-Tree（head tree），装得下最新的少量数据；下面是若干层不可变的有序段，容量按固定倍数逐层放大。新数据先进头部小树，满了就与下一层归并成一个新的有序段——归并是从头到尾顺着写的，正合闪存胃口。写路径上再没有一次随机写。

但分层带来一个新麻烦：查一个键要逐层去找，每层一次二分查找就是一次随机读，层数一多读就塌了。分数级联是这里的点睛之笔：在上层的段里预先埋下指向下层对应位置的指针（书里叫 fence，栅栏）。于是查完第 1 层，你手里已经攥着「第 2 层该从哪个位置看起」，不必重新二分。原论文给出的结论是：更新只花 O(logB n) 次顺序 I/O，查找花 O(logB n) 次随机 I/O（B 是闪存页大小）——白话说就是查找的成本和普通 B-Tree 同量级，写入的成本却降到了写优化结构的水平。

四、Bw-Tree：把「加闩」整个删掉

Bw-Tree（Microsoft Research，2013）冲的是第二笔账——并发。它的目标极端：整棵树一把闩都不加，全靠 CAS 推进。三个零件缺一不可。

零件一：增量记录。要改一页，不动这页，写一条只说「这次改了什么」的小记录，让它指向原页——形成一条增量链。读的时候从链头往下走，把沿途的改动叠加到基础页上。写的成本从「重写一页」降成「追加一条几十字节的记录」。

零件二：映射表。这是全章最值得学的一招。树里所有指针存的都不是物理地址，而是逻辑页号；另有一张映射表把页号翻译成当前物理地址。于是「用新版本替换某一页」就退化成在映射表里改一个槽位——一条 CAS 指令，原子完成。父节点里的指针一个字节都不用动，这正是无闩得以成立的关键：修改一页从来不需要同时锁住它的父亲。CAS 失败也不要紧，说明别人抢先了，重读、重试即可。

零件三：合并与回收。链越长读越慢（原论文的实测曲线里，吞吐随链变长明显下降），所以链长超过阈值就合并（consolidation）：把基础页和整条链算成一个新页，再 CAS 进映射表。换下来的旧页与旧增量不能立刻释放——可能还有线程正在读，而无闩结构里没人能告诉你「读完了」。解法是基于纪元的回收（epoch-based reclamation）：待释放对象挂进当前纪元，等进入过该纪元的线程都离开了再统一释放。

分裂怎么办？这是最难的部分：分裂要同时改自己和父亲两个节点，而 CAS 一次只能原子地改一处。做法是拆成两个各自原子的步骤：第一步在被分裂节点上装一条「分裂增量」，附带指向新兄弟的侧向指针（Blink-tree 的思路）——此时结构已可用，父节点虽不知情，走到这里的线程顺着侧向指针也能找到目标；第二步再往父节点装一条「索引项增量」。撞见半完成分裂的线程不干等，而是顺手把第二步替它做完。

五、缓存无关 B-Tree：把页大小这个参数也删掉

最后一支路线来自算法领域，思想漂亮但工程上少见。经典 B-Tree 要调一个参数：节点多大才配得上页大小。可存储层级不止一层——L1 / L2 / L3 缓存、内存、SSD，每层的「块」都不一样，一个节点大小不可能同时讨好所有层。缓存无关 B-Tree 用递归的 van Emde Boas 布局把树摊平：反复把树从中间高度切开，上半棵与每个下半棵各自连续存放。于是无论上层用多大的块来读，读到的那段里都恰好含一条连续的树路径，不知道块大小也能拿到接近最优的 I/O。代价是更新时维护这个布局很贵——它是一种启发，而非生产选项。

关键权衡与选型

表 1 · 四条变体路线：各治什么病，代价是什么

表 2 · 原地更新 vs 不原地更新：一次决定引出的一串连锁反应

落到选型上的判据：

• 读极多写极少、嵌入进程内、崩溃后要立刻可用（配置库、目录服务、本地缓存）→ 写时复制：读路径零加闩零拷贝、不需要恢复流程，前提是能接受单写者。
• 通用 OLTP，写有一定量，要压缩与多核写并发 → 惰性 / 缓冲路线，WiredTiger 的定位正是这里。
• 写远多于读、跑在闪存上 → 分层归并的形状（FD-Tree 是它在 B-Tree 语境下的表达，工业界的答案是下一章的 LSM-Tree）。愿意用读放大换写放大时才选。
• 数据全在内存、核数很多、闩争用是首要瓶颈 → 无闩路线。但先读完下面「争议」那条再决定。

为什么重要 / 落到真实系统

这一章的价值不在于让你去实现一棵 Bw-Tree，而在于一张可迁移的权衡地图：不可变 + 间接层 + 缓冲 + 延迟回收。ZFS、Btrfs 的写时复制与 LMDB 同源；容器镜像的分层、Git 的对象存储也是「不改旧的、只加新的、最后换一个引用」。凡是把「原地修改」换成「新写一份 + 原子换指向」的系统，都会同时收获快照能力与崩溃安全，也同时欠下一笔垃圾回收的债。面试里「LMDB 为什么不需要 WAL」「无闩就一定更快吗」「为什么写优化存储都长得像分层归并」，考的都是这一章。

易错点与争议

• 以为写时复制省写。恰恰相反：单次写放大更大（要拷贝整条路径）。它赢的地方在别处——免掉 WAL 与撕裂页的双写、免掉恢复流程、送你一份快照。省不省，要按端到端算，不是按单次写算。
• 以为 LMDB「无锁」意味着高写并发。它的无锁是给读者的；写者永远只有一个。读多写少时惊艳，写密集时这就是硬天花板。
• 忘了不可变结构的账单在后面。旧版本必须有人回收：写时复制靠空闲页表、Bw-Tree 靠 epoch、惰性路线靠归并与检查点。一个长读事务钉住旧版本，就能让文件持续膨胀。
• 把 Bw-Tree 的「无闩」等同于「更快」。这是本章最大的争议点。SIGMOD 2018 的复现指出，增量链的指针追逐、映射表的额外一跳、epoch 回收的开销加起来可能盖过省掉闩的收益；而现代的乐观锁耦合（读只校验版本号、不真加锁）用简单得多的手段拿到了相近的可扩展性。无闩是权衡，不是免费加速。
• 把 FD-Tree 当成 LSM-Tree。形状很像（分层、归并、顺序写），但它顶上仍是一棵可原地更新的 B-Tree，并用栅栏指针专门压低多层查找的读放大。是「B-Tree 向 LSM 借力」，不是 LSM 本身。
• 时代局限。本章的成本模型建立在「随机写远贵于顺序写、页是不可分割的读写单位」之上，这两条正被 NVMe 与字节可寻址持久内存松动；B-Tree 与 LSM 的边界也在模糊。而更根本的一点是：这些变体没有免费午餐，它们只是把成本从写路径挪到读路径、从运行时挪到后台。

要点