鲁班 - 系统设计大全

44.1 存储引擎：B+ 树与 LSM 树

一句话

B+ 树是 “就地更新 + 原地读”：写入改页、读取走索引；LSM 是 “只追加 + 后台合并”：写入进内存表、满了刷成有序文件、后台合并——前者读快写稳，后者写快、读要付出 “查多层” 的代价。

两种结构

维度 B+ 树 LSM 树
写路径 找到页 → 修改 → 刷页（可能随机写） 写内存表 → 刷成 SSTable → 后台 compaction
读路径 从根到叶 O(log n) 次页访问 内存表 → L0 → L1…（可能要查多层）
写放大 低（约 1–2×，取决于页大小与分裂） 高（compaction 反复重写，常见 10–30×）
读放大 低（一次索引定位） 高（多层 + 无索引时线性扫）
空间放大 低（页内空隙） 中（多版本文件 + 待合并数据）
典型 MySQL InnoDB、PostgreSQL RocksDB、LevelDB、Cassandra、HBase

实测：写路径与读路径的差别（本机）

5 万条 100B 记录：

引擎 写入耗时 文件大小 点读
B+ 树（sqlite3，WAL 模式） 86ms 5.4MB 2 万次 71ms
LSM 模拟（内存表 1000 条 + 4 层合并） 21ms — 5000 次 7ms（无布隆）/ 5ms（有布隆）

两个可迁移的结论：① 写路径 LSM 快约 4 倍（追加 vs 就地改页 + 随机 IO）；② LSM 的读路径依赖 “布隆过滤器 + 层内有序”——实测布隆过滤器让 5000 次点读少读了 2521 个文件（33%）。没有索引的 LSM（直接线性扫）在本机 2000 次点读要 2981ms、扫了 4900 万条记录——这就是 “读放大” 的真实样子。

# LSM 的读路径：逐层找，先过布隆过滤器
def get(k):
    if k in memtable: return memtable[k]
    for level in levels:                 # L0 → L1 → ...
        for run in level:
            if k not in run.bloom: continue   # 90%+ 的文件在这一步被跳过
            i = bisect(run.keys, k)            # 层内有序 → 二分
            if i < len(run) and run.keys[i] == k: return run.values[i]

反模式

反模式 后果
用 LSM 存 “大量小记录 + 频繁点查” 读放大 + compaction 抖动，P99 飙升
用 B+ 树存 “写多读少 + 顺序追加” 随机写放大，写吞吐上不去
LSM 不做布隆过滤器 每次点查扫多层文件
compaction 不限速 后台合并抢 IO，前台延迟尖刺
大 value（> 1MB）直接进 LSM compaction 搬运巨大，写放大爆表
只看平均延迟 compaction 尖峰被平均掩盖

三条铁律

🔑 写多读少选 LSM，读多写少选 B+ 树；两者都没有 “全面更优”。

🔑 LSM 的读性能靠 “索引 + 布隆 + 层数控制”，不靠 “文件少”。

🔑 compaction 必须限速与可观测，否则它会在你最忙的时候抢 IO。

自检

Q1 为什么 LSM 的写放大比 B+ 树高，写入却更快？

▸ 答案：因为 写放大发生在后台：前台只写内存表（顺序追加，极快），compaction 在后台慢慢重写。B+ 树则是 “前台就地改页”，可能触发随机 IO 与页分裂。所以 “写快” 指前台延迟，“写放大” 指总 IO 量——两者不是一回事。

Q2 LSM 的读放大从哪来？

▸ 答案：来自 “要查多层”：一条记录可能在 memtable、L0、L1…直到最底层，最坏要查遍所有层。缓解手段是布隆过滤器（跳过不含该 key 的文件）、层内二分、以及控制层数（fanout 越大层越少）。

Q3 实测中布隆过滤器省了 33% 的文件读取，为什么不是 90%？

▸ 答案：因为布隆过滤器只能排除 “确定不包含” 的文件，命中率取决于 key 的分布与每层文件数：本实验里 5000 次查询涉及 7462 次文件读取，布隆跳过 2521 次（33%）。真实系统中如果 key 集中或层数少，跳过比例会变化——所以 “布隆能省多少” 必须实测，不能假设。

Q4 什么场景下 B+ 树明显优于 LSM？

▸ 答案：点查多、写少、要求稳定低延迟：读路径只需一次索引定位，没有多层查找与 compaction 抖动。典型如 OLTP 主库、账户/订单查询。反过来，写入吞吐要求极高、能接受读放大时，LSM 更合适。

Q5 LSM 的 “空间放大” 指什么？

▸ 答案：指同一份数据在多个文件中存在多个版本（旧版本要等 compaction 才清理），以及 “待合并的临时空间”。加上删除标记（tombstone）也要占空间，所以磁盘占用会高于逻辑数据量，直到 compaction 完成。

Q6 为什么 “大 value” 不适合直接进 LSM？

▸ 答案：因为 compaction 要把 value 整体搬运、重写多次：value 越大，写放大与内存压力越大。常见做法是 “大 value 存单独的文件/对象存储，LSM 只存引用（路径 + 偏移）”，把 “元数据” 与 “大块数据” 分开。

Q7 怎样判断 “该换存储引擎了”？

▸ 答案：看三个信号：写放大导致的 IO 饱和（compaction 长期追不上）、读放大导致的 P99 恶化（层数多、布隆失效）、空间放大导致的磁盘告警。三者任一持续出现，说明当前引擎与负载不匹配，而不是 “参数没调好”。

关联