算法与数据结构 / B-tree、B+ tree 与 LSM-tree · 磁盘与页的世界 待审核 7 页

B-tree、B+ tree 与 LSM-tree · 磁盘与页的世界

内存里的查找树按比较次数计费，磁盘上的不是。块设备的最小读取单位是页——4 KB 或 16 KB，读一个字节和读一整页的代价几乎相同，而这一次读的延迟比一次内存访问高三到五个数量级。代价模型一换，最优结构随之改变：要压的不再是树高的对数常数，而是树高本身。

本系列分三条线。第一条把账算清楚：同样 1000 万条记录，完全平衡的二叉查找树高 24，而 16 KB 页、8 字节 key 的 B-tree 扇出 1170、树高只有 3。代价从 24 次随机读降到 3 次，付出的是节点内的比较次数上升——100 万条记录的实测里，阶 4 的树每次点查比较 21.8 次，阶 256 的树是 197.6 次。省访存的手段就是多比较。

第二条线是 B-tree 家族本身：插入时节点满则分裂、中位 key 上提，树高只从根往上长；删除要在借 key 与合并之间选，比插入麻烦得多。B+ tree 把数据全部下沉到叶子、内部节点只留路标，于是同样的页装得下更多路标，叶子之间还能用链表串起来，让范围扫描从随机读变成顺序读。数据库索引选 B+ 而不是 B，理由全在这两条上。

第三条线走向另一种取舍。LSM-tree 不再原地改页：写入先追加 WAL 再进内存表，满了整块冻结成不可变的 SSTable 刷盘，后台 compaction 分层归并。读因此要摸多层，靠 Bloom filter 把「这个文件肯定没有该 key」判掉。写放大、读放大、空间放大三者不可能同时最优，leveled 与 tiered 两种 compaction 各占三角形的一边。

页作为代价的单位

一次随机读的代价与读多少字节几乎无关，于是「访问了几个节点」取代「做了几次比较」成为主指标。这一条改写了整个结构设计：节点被撑到一整页大，扇出从 2 变成上千，树高塌成个位数。

page · 扇出 · 树高 · 随机读

页作为代价的单位：树高与比较次数

块设备的最小读取单位是页，一次随机读的代价与读多少字节几乎无关。要最小化的量因此从比较次数换成访存次数，也就是树高。同样 1000 万条记录，完全平衡的二叉查找树高 24，扇出 1170 的 B-tree 高 3。

与平衡 BST 的分界线

树 · 遍历、平衡 BST 与前缀 / 度量树里的红黑树、AVL、treap 全都在压同一个量：树高的常数因子。它们的分歧是「用颜色还是用高度还是用随机 priority 维持平衡」，而扇出恒为 2 从不在议题上。 B-tree 换掉的正是这个默认值。扇出一旦可调，树高就从

\log_2 n

变成

\log_f n

，

f

由页大小除以 entry 大小决定，通常是几百到一千多。同样 1000 万条记录，二叉树 24 层、B-tree 3 层。代价模型的改变比算法的改进更能压低代价，这是本系列反复出现的一条。

页、代价模型与 B-tree 起源 · 延伸阅读

Bayer & McCreight · Organization and Maintenance of Large Ordered Indices (1972) link.springer.com B-tree 的原始论文。1970 年在 Boeing 写就，问题背景就是「索引放不进内存」，节点大小直接对齐磁盘页。
Comer, D. · The Ubiquitous B-Tree (1979) dl.acm.org 把 B-tree、B*-tree、B+ tree 的变体谱系梳理清楚的综述，「B+ tree」这个叫法的通行版本出自这里。
Latency Numbers Every Programmer Should Know colin-scott.github.io Jeff Dean 那张延迟表的可交互版本，可按年份看各级存储延迟的变化。B-tree 存在的全部理由，就是这张表上内存与块设备之间那三到五个数量级。

B-tree 家族

同一套阶 $m$ 的约束长出两种树。B-tree 的 key 与数据散布在全部层级，B+ tree 把数据压进叶子、内部节点只当路标。分裂与合并的规则两者共享，范围查询的代价则天差地别。

阶 m · split · 中位 key 上提

B-tree 的分裂：从下往上长高

阶 m 的三条约束（key 数区间、孩子数等于 key 数加一、所有叶子同深）如何靠一条规则维持：节点溢出就一分为二、中位 key 上提到父。树高只在根分裂时增加，所以 B-tree 是从叶子往根长的。

下溢 · borrow · merge · 前驱顶替

删除的三种修复：借与合并

删除一个 key 可能让节点掉到下限以下。修复只有三条出路：从左兄弟借、从右兄弟借、与兄弟合并，且必须按这个顺序试。B-tree 还多一种情形：被删的 key 落在内部节点上，得先用左子树的最大 key 顶替。

separator · 叶链 · 范围扫描 · 覆盖索引

B+ tree：数据下沉到叶子

内部节点只留路标、数据全在叶子，于是同样的页装得下更多路标；叶子之间用链表串起来，范围扫描从随机读变成顺序读。数据库索引选 B+ 而不是 B，理由全在这两条上。

fanout · 填充因子 · 回表 · 索引体积

页与扇出的算术

从页大小、key 大小、指针大小算出扇出与树高，再算出索引占多少页、一次二级索引查询要摸几页。填充因子把这些数字整体放大：随机插入下叶子只有约七成满，顺序插入在朴素分裂下只有五成。

删除比插入难，难在修复的分支数

插入的修复只有一种形态：节点溢出就分裂，中位 key 交给父节点，父节点若也溢出再分裂，一路到根。整条链上每个环节的动作完全相同。删除不是。一个下溢的节点有三条出路——从左兄弟借、从右兄弟借、与某个兄弟合并，且必须按这个顺序试；B-tree 还多一种情形：被删的 key 落在内部节点上，得先用左子树的最大 key 顶替，把问题转成删叶子里的那个 key。实测

m = 5

的 B-tree 装 1000 个 key 再删光，插入侧只有 365 次分裂，删除侧是 356 次借 + 365 次合并 + 296 次前驱顶替。

B+ tree 与数据库索引 · 延伸阅读

MySQL · InnoDB Physical Row Structure dev.mysql.com 16 KB 页、聚簇索引、二级索引回主键的一手文档。本系列的页算术全部对着这套参数算。
PostgreSQL · B-Tree Indexes postgresql.org Lehman & Yao 的高并发 B-tree 变体在生产系统里的样子，含 right-link 与 page split 的并发处理。
Lehman & Yao · Efficient Locking for Concurrent Operations on B-Trees (1981) dl.acm.org 给每个节点加一条指向右兄弟的 link，使分裂中途的树对并发读者仍然自洽。现代 B+ tree 实现的并发基础。
Yao, A. C. · On Random 2-3 Trees (1978) link.springer.com fringe analysis 的开山之作，也是「随机插入下高阶 B-tree 的存储利用率收敛到 $\ln 2 \approx 69.3\%$ 」这一结论的出处。本系列 20 万个 key 的实测是 70.8%。

LSM-tree 与写优化

原地更新意味着随机写。LSM-tree 换成「只追加、后台归并」，把随机写摊成顺序写，代价是同一个 key 的多个版本散在各层，读要逐层找、空间要为旧版本买单。三个放大之间的取舍由 compaction 策略决定。

memtable · SSTable · compaction · Bloom filter

LSM-tree：不改页，只追加

写入先追加 WAL 再进内存表，满了冻结成不可变的 SSTable 刷盘，后台 compaction 分层归并。读要摸多层，靠 Bloom filter 判掉不含该 key 的文件。leveled 与 tiered 各占取舍三角的一边。

随机写 · 顺序写 · 点查 · 范围查 · 空间

B+ tree 与 LSM-tree 的分工

把两种结构放在随机写、顺序写、点查、范围查、空间占用五个维度上对照。B+ tree 的随机写要重写整页，实测字节写放大 127.9；leveled LSM 是 56.72、tiered 是 4.77，且全部是顺序写。

三个放大不可能同时最优

写放大、读放大、空间放大构成一个取舍三角，任何 compaction 策略只能占其中两个角。同一份负载（20 万次写、10 万个 key、

T = 10

）在本系列引擎上的实测： leveled 每层是一条不重叠的有序 run，点查每层至多摸一个文件——不带 Bloom filter 的未命中读放大 2.85，空间放大 1.19，代价是写放大 56.61。 tiered 每层攒够

T

个 run 才整层合并，写放大只有 4.77，代价是未命中读放大 14.92、空间放大 1.93。两者的读放大差 5.2 倍、写放大差 11.9 倍。选哪个不取决于哪个「更好」，只取决于负载是写多还是读多。

LSM-tree 与 compaction · 延伸阅读

O'Neil et al. · The Log-Structured Merge-Tree (1996) cs.umb.edu LSM-tree 的原始论文。 $C_0$ 在内存、 $C_1$ 及以下在磁盘，rolling merge 就是今天 compaction 的雏形。
Chang et al. · Bigtable (OSDI 2006) research.google memtable、SSTable、Bloom filter 这套词汇的出处。LevelDB 与 RocksDB 都是它的开源后裔。
RocksDB Wiki · Leveled Compaction github.com leveled 策略的工程细节：层容量倍率、L0 的特殊待遇、compaction 优先级与写放大估算。
Dayan, Athanassoulis & Idreos · Monkey (SIGMOD 2017) nivdayan.github.io 给各层分配不同的 Bloom filter 位数，在同样内存下把未命中读放大压到更低。三个放大取舍的定量分析出自这一系列工作。
Athanassoulis et al. · Designing Access Methods: The RUM Conjecture (2016) openproceedings.org Read、Update、Memory 三项开销不可能同时最优的猜想，本系列三个放大的取舍三角即其一例。