算法与数据结构 / B-tree、B+ tree 与 LSM-tree · 磁盘与页的世界 / B+ tree 与 LSM-tree 的分工 待审核 7 / 7
随机写 · 顺序写 · 点查 · 范围查 · 空间

B+ tree 与 LSM-tree 的分工

B+ tree 与 LSM-tree 解决同一个问题，选择了相反的默认值。前者维持一份始终有序、原地更新的结构，读路径短而确定；后者放弃原地更新，把写摊成顺序追加，读路径变长。

本页把两者放在同一组坐标上量，并给出选型的判据。

1 · 五个维度的分工

维度 B+ tree LSM-tree
随机写 定位 hh 次随机读，改页，落盘时重写整页 追加 WAL 加内存表，落盘全是顺序写
顺序写 朴素分裂下叶子只有五成满（见 页与扇出的算术 §4） memtable 满了整块刷出，天然紧凑
点查 hh 次页读，hh 是 3 或 4，确定 逐层找，读放大随层数与策略变化
范围查 一次下降加沿叶链的顺序读 每层各开一个迭代器做多路归并
空间占用 填充因子约 0.69，即多占 45% 旧版本与 tombstone 并存，空间放大 1.19 到 1.93
删除 借与合并，代价 O(h)O(h) 写一条 tombstone，真正回收要等 compaction
图 1-1 · 按点查、范围查、随机写三种操作的比例混合出一份负载，两种结构各自的页 I/O 估算。可拖动三个比例与数据规模，观察交叉点落在哪里。

有两处对照值得单独拎出来。

范围查这一行看起来是 B+ tree 完胜，实际差距没有那么大：LSM 的范围扫描要在每层各开一个迭代器做多路归并，但每个迭代器读的都是顺序的 SSTable 块。真正的差距在结果延迟的确定性上，B+ tree 的一次范围扫描只需一次下降就能开始吐数据。

删除这一行则常被低估。LSM 写一条 tombstone 就返回，看起来极便宜，但它在被 compaction 清掉之前会一直参与读路径；大批量删除后紧接着范围扫描，可能要跳过成千上万条 tombstone 才凑出一行结果。这类「删完就慢」的现象在 Cassandra 上有专门的名字与监控项。

2 · 随机写的字节账

「B+ tree 随机写贵」这句话通常只说到「随机 I/O」为止。把它量化会得到一个更强的结论。

一次行写在磁盘上不是写 128 字节，是重写整个 16 KB 页。字节写放大的上界是 16384/128=12816384/128 = 128。buffer pool 能把同一页上的多次写合并成一次落盘，所以实际值取决于工作集与内存的比例。

1000 万行、16 KB 页、行 128 字节、填充因子 0.69，共 113637 个叶页；20 万次均匀随机写下的实测：

buffer pool 内存 落盘页数 写命中率 字节写放大
114 页（0.1%） 2 MB 199767 0.1% 127.9
5682 页（5%） 89 MB 189994 5.0% 121.6
22727 页（20%） 355 MB 162298 18.9% 103.9
56819 页（50%） 888 MB 116982 41.5% 74.9
113637 页（100%） 1776 MB 93992 53.0% 60.2

同一份负载喂给 LSM：leveled 的字节写放大 56.72，tiered 4.77。

图 2-1 · buffer pool 占索引比例与 B+ tree 字节写放大的关系，横线是同一份负载下 leveled 与 tiered LSM 的写放大。可调 pool 大小、写入次数与行大小，观察三条线何时交叉。

警示 · 这张表推翻了本页原先的写法。原本按常识写的是「LSM 用写放大换写吞吐，B-tree 的写放大更低」。实测正好反过来：即使 buffer pool 装得下整个索引，B+ tree 的字节写放大仍有 60.2，高于 leveled LSM 的 56.72，更远高于 tiered 的 4.77。 错在把「写放大」与「重写量」混为一谈。B-tree 每行写要重写整页，写放大的分母是行大小、分子是页大小，这个比值本身就是 128；buffer pool 只能按命中率打折，打不到 1。LSM 的每一份重写都是把整块数据顺序搬到下一层，分母是全部用户数据而不是单行。 真正属于 B-tree 的优势不在写放大的数值上，而在两处：写放大与数据量无关（不随层数增长），以及不需要后台线程持续消耗 I/O 带宽。LSM 的 compaction 是一项持续的背景负载，尾延迟的抖动多半来自它。

3 · 读侧的分岔

点查在 B+ tree 上是确定的：hh 次页读，hh 由数据量与扇出定死，与写入历史无关。顶部两层常驻内存的话只剩 1 次随机读。

LSM 的点查代价随写入历史漂移。刚 compaction 完与 L0 攒满时，读放大能差好几倍。Bloom filter 把未命中那一侧压得很低（本系列实测从 2.85 降到 0.030），命中那一侧则压不动——要找的 key 确实在某个文件里，那次读省不掉。

这条差别决定了两类系统对 p99 延迟的态度。B+ tree 的 p99 主要来自 buffer pool 未命中与页分裂；LSM 的 p99 主要来自 compaction 抢占 I/O 与 L0 堆积。前者可以靠加内存单调改善，后者要靠调 compaction 参数，而那些参数彼此耦合。

4 · 落到具体系统

原地更新一侧：InnoDB、PostgreSQL、SQLite、Oracle、SQL Server 的主索引都是 B+ tree 或其变体。它们的共同前提是读多写少、需要稳定的低延迟、且数据集与内存的比例不算太糟。

追加一侧：LevelDB 与 RocksDB 是 LSM 的两个参考实现，Cassandra、HBase、ScyllaDB、TiKV、CockroachDB 的存储层都建在这一侧。共同前提是写入吞吐优先、可以接受读放大、且愿意为 compaction 留出 I/O 预算。

两侧并非互斥。MyRocks 把 RocksDB 接进 MySQL，用的是 InnoDB 的上层加 LSM 的存储层；WiredTiger 同时提供 B-tree 与 LSM 两种表类型。选型的实际问题往往不是「哪个更好」，而是「这份负载的写入量与工作集比例落在哪一档」，而这一档可以用本页的两张表估出来。

5 · 参考文献

  1. Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing access methods: The RUM conjecture. Proceedings of EDBT '16, 461–466.
  2. Luo, C., & Carey, M. J. (2020). LSM-based storage techniques: A survey. The VLDB Journal, 29(1), 393–418.
  3. Matsunobu, Y., Dong, S., & Lee, H. (2020). MyRocks: LSM-tree database storage engine serving Facebook's social graph. Proceedings of the VLDB Endowment, 13(12), 3217–3230.
  4. Graefe, G. (2011). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 203–402.
  5. Kleppmann, M. (2017). Designing Data-Intensive Applications, Chapter 3: Storage and Retrieval. O'Reilly.