存储基础（5）：B+Tree vs LSM——读写与范围查询的权衡
发布于：
本文是「存储基础系列」的第 5 篇：用“工作负载”的视角比较 B+Tree 与 LSM，两者没有绝对优劣，只有取舍。
1. 两个结构各自擅长什么
B+Tree（典型：MySQL/InnoDB、很多 OLTP 引擎）
- 点查稳定：树高有限（page 粒度），读路径可预测
- 范围扫描友好：叶子节点链表/连续 page，顺序 IO 更容易
- 更新就地写（in-place）：代价是随机写多、需要页分裂/合并
LSM（典型：RocksDB、LevelDB、很多 KV 引擎）
- 写入友好：随机写变顺序写（WAL + memtable + SST）
- 吞吐高：尤其在写多场景
- 读路径复杂：多层文件 + compaction，读放大与写放大互相牵制
1.1 一句话抓住“结构差异”
- B+Tree：读写都围绕“页（page）”做就地维护，代价是随机写与刷脏页的复杂性。
- LSM：写入先变顺序写，读通过 filter/index 缩小范围，后台合并维持有序与空间回收，代价是 compaction 的重写与资源竞争。
2. 范围查询为什么常常更偏爱 B+Tree
范围查询的核心是“连续读”：
- B+Tree 的叶子节点天然按 key 有序，范围扫描常常是顺序读 page
- LSM 虽然每个 SST 也有序，但同一 key 空间被切成多层文件，范围扫描可能要合并多个来源
所以在“范围扫描很多”的工作负载里，B+Tree 往往更自然。
2.1 LSM 范围扫描为什么更难（但也能优化）
LSM 的范围扫描困难点在于：同一 key-range 可能分散在多层多个文件里，需要 iterator 合并多个来源。
常见优化方向：
- 让底层更“稳定”（leveled、减少重叠）
- 更积极的 compaction 把旧版本/tombstone 清掉
- scan 走顺序预取/避免污染 cache（不同系统策略不同）
3. 什么时候 LSM 更合适
典型特征：
- 写入量大，写入模式更随机
- 点查为主（而不是大范围 scan）
- 可以接受一定 compaction 成本（或有足够后台资源）
常见系统会用：
- Bloom Filter 降低读不存在的成本
- block cache / page cache 提高热点命中
- 合理的 compaction 策略控制写放大
3.1 什么时候 B+Tree 更合适
如果你的负载符合这些特征，B+Tree 往往更省心：
- 范围查询/排序/二级索引很多（OLTP/OLAP 混合也常见）
- 对尾延迟抖动敏感（尤其是“写抖动”不可接受）
- 能接受 buffer pool 的内存成本，并且有成熟的刷盘/检查点策略
4. 一个“选型快速问答”
如果你在做系统设计，可以用下面的问题快速收敛：
- 写多还是读多？ 写多 → LSM 倾向更强
- 点查多还是范围查多？ 范围查多 → B+Tree 倾向更强
- 延迟抖动能接受吗？ 不能 → 更偏 B+Tree 或做严格后台隔离
- 是否有大量覆盖/删除？ LSM 需要 compaction 才能真正回收
4.2 一个更“工程决策化”的对照表（建议按你的场景勾选）
| 维度 | B+Tree 倾向 | LSM 倾向 |
|---|---|---|
| 点查稳定性 | 更可预测（树高稳定） | 依赖层数/文件数/缓存命中 |
| 范围扫描 | 更自然（leaf 顺序） | iterator merge 更复杂 |
| 写入吞吐 | 随机写压力更大 | 随机写→顺序写，吞吐更强 |
| 尾延迟抖动 | 更容易靠 buffer pool/刷盘策略控制 | compaction/backlog 更容易抖，需要预算化 |
| 删除/覆盖回收 | 依赖页回收/空间管理 | 依赖 compaction（tombstone） |
| “工程形态” | 更像数据库（多索引/复杂查询） | 更像 KV/日志型系统（写多/简单查询） |
4.1 选型不要忘了“工程形态”
最后提醒一个经常被忽略的维度：更偏向哪种工程形态？
- 更像数据库（事务/多索引/复杂查询）：B+Tree 家族更自然
- 更像 KV/日志型系统（写多、简单查询）：LSM 家族更自然
到这里你已经具备“能读懂大多数存储系统基本 trade-off”的最小知识集。后续系列会逐步补上：缓存层次、分布式复制/一致性、以及真实系统里的工程细节。