LSM 树：把随机写变成顺序写

一句话结论（30s）

LSM 树的核心就是把随机写转成顺序写——因为磁盘的顺序 IO 比随机 IO 快约 4 倍，B+ 树每次写入要定位磁盘页（随机 IO + 可能页分裂），而 LSM 树只追加 WAL + 写内存 MemTable，批量顺序刷盘，用”读放大”的代价换来写多读少场景下的高写入吞吐，所以 RocksDB/LevelDB 都选它。

核心原理（2min）

写入路径：先写 WAL 防崩溃 → 写内存有序结构 MemTable → 满了 flush 成磁盘上不可变的 SSTable，全程顺序追加。
读取路径：MemTable → Block Cache → 逐层 SSTable 查找，每层前用 Bloom Filter 快速过滤不存在的 key。
Compaction：后台合并多层 SSTable，去重、清除 tombstone 回收空间；分 Leveled（写放大高读放大低）与 Tiered（相反）两种。
取舍：LSM 为磁盘优化，Redis 全内存所以不需要它（内存无寻道，顺序/随机一样快，LSM 反而引入读放大）。

底层深入（5-10min）

LSM 树的核心思想

把随机写转化为顺序写。 传统 B+ 树的写入需要找到正确的磁盘页位置（随机 IO），然后可能触发页分裂（又一次随机 IO）。LSM 树不管数据的位置，直接把所有写入追加到内存中的有序结构（MemTable），然后批量顺序刷到磁盘（SSTable）。

想一想：为什么”顺序写”能比”随机写”快这么多？ 因为磁盘的瓶颈在机械寻道（HDD 尤其明显）——随机写要反复移动磁头到不同位置，顺序写则一路往后追加、磁头几乎不用动，所以顺序 IO 比随机 IO 快约 4 倍。LSM 的巧思就在于：不管业务写的是什么 key、落在什么位置，一律先变成内存里的有序追加，再批量顺序落盘，从源头消灭了随机写。

三组件架构

写入路径:
  1. WAL (Write-Ahead Log)  —— 先写日志防崩溃
  2. MemTable (内存)          —— 有序的跳表/红黑树，内存操作极快
  3. MemTable 满 → flush → SSTable (磁盘，不可变)

读取路径:
  1. MemTable (内存，最近写入)
  2. Block Cache (磁盘热数据缓存)
  3. SSTable 逐层查找，Bloom Filter 快速过滤不存在的 key

压缩（Compaction）:
  后台线程定期合并多层 SSTable，去除重复 key，只保留最新版本

写入为什么快？

B+ 树每次写入：① 二分查找定位页 ② 可能页分裂 ③ 写回磁盘（随机 IO）。单次写入 = 1~3 次随机 IO。

LSM 树每次写入：① 追加写 WAL（顺序 IO）② 插入 MemTable（内存，纳秒级）③ 返回。单次写入 = 1 次顺序 IO。MemTable flush 和 Compaction 都是后台异步执行，不阻塞前台写入。

顺序 IO 比随机 IO 快约 4 倍（HDD）——这是 LSM 树写入性能的物理基础。

想一想：LSM 写入为什么能”快到返回”？ 因为前台写路径只有三步：追加 WAL（1 次顺序 IO）+ 插入 MemTable（内存，纳秒级）+ 返回。真正的重活——flush 刷盘和 Compaction 合并——全被甩到后台异步执行，不阻塞前台。也就是说 LSM 把”单次写入的昂贵成本”摊薄、延后到了后台，用后台吞吐换前台延迟。

读取为什么有放大？

一个 key 可能分布在多处：MemTable（最新）、Level 0 SSTable（最近 flush）、Level 1-N SSTable（已 compaction）。最坏情况需要查遍所有层级才能确定 key 是否存在——读放大。

Bloom Filter 在每层 SSTable 之前做 O(1) 过滤——“该 SSTable 一定不包含此 key”则跳过，99% 的 miss 只查询一次 Bloom Filter 就结束。

想一想：LSM 为什么读会慢、读放大是怎么来的？ 因为写路径是”追加”，同一个 key 的多个版本会散落在 MemTable、Level 0 和各级 SSTable 里，读一个 key 可能要从最新到最旧逐层查找，直到命中或查完所有层才能确认不存在——层级越多、越深的 key 读起来越慢。这正是”用读放大换写快”的代价。Bloom Filter 就是用来缓解它的：先用极小内存判断”这一层肯定没有这个 key”，把绝大多数不存在的查询挡在磁盘 IO 之前。

Compaction：空间换时间

LSM 树的每一层 SSTable 是不可变的——删除操作不真正删除数据，而是写入一个”tombstone”（删除标记）。Compaction 时合并多层 SSTable，移除过期版本和 tombstone，回收空间。

Leveled Compaction：每层大小固定，层级越深越大（通常 ×10），写放大高但读放大低
Tiered Compaction：相似大小的 SSTable 合并为一层，写放大低但读放大高（需查更多层）

想一想：为什么 Leveled 写放大高、Tiered 读放大高？ 因为 Leveled 要求每层内部有序且互不重叠，一个 key 从上层往下迁移时会被反复读写、反复合并（同一份数据写多次 = 写放大），但换来每层只需查一个 SSTable，读很快；Tiered 允许同层多个 SSTable 重叠，合并成本低（写放大低），但读一个 key 可能要在同层的多个 SSTable 里都找一遍（读放大高）。本质是”把成本放在读还是写”的选择。

Redis 为什么不用 LSM 树？

Redis 是全内存数据库——所有数据在内存中，读写都是内存操作（纳秒级）。LSM 树的”顺序写优化”在内存场景下完全没有意义（内存没有寻道时间，随机读写和顺序读写一样快）。LSM 引入的读放大反而会让 Redis 的性能从纳秒级退到微秒级。

LSM 树是为磁盘优化的，Redis 是为内存设计的——两者面向完全不同的物理介质。

想一想：为什么 Redis 不用 LSM 树？ 因为 LSM 的整套设计——顺序写、WAL、Compaction——都是在”磁盘寻道很贵”这个前提下做的优化。Redis 全内存，随机读和顺序读一样快、没有寻道成本，LSM 的优化点全部落空，反而读放大和后台 Compaction 会把性能从纳秒级拖到微秒级。所以选存储引擎的本质是”贴着物理介质的特性来设计”，而不是套模板。

总结

	B+ Tree (InnoDB)	LSM Tree (RocksDB/LevelDB)
写路径	随机写（定位）	顺序写（追加）+ 内存排序
读路径	单路径 O(log n)	多层查找（读放大）
Compaction	不需要	需要（后台合并）
适合场景	读多写少	写多读少（时序数据、日志、消息队列）

章末提问

1. LSM 树为什么写快、读慢？

结论先行：因为 LSM 把随机写转成顺序写（写快），但代价是同一个 key 的多个版本散落在多层结构里，读要逐层查找（读慢）。

因为写路径只做”追加 WAL + 写内存 MemTable + 返回”，重活（flush、Compaction）全甩后台，且顺序 IO 比随机 IO 快约 4 倍；而读一个 key 要从 MemTable、Level 0 一直查到深层 SSTable，层级越深成本越高，最坏要查遍所有层才能确认 key 不存在，这就是读放大。

2. 读放大是怎么产生的？怎么缓解？

结论先行：读放大源于”追加写 + 不可变 SSTable”导致同一 key 多版本分层散落，读要跨层查找；缓解靠 Bloom Filter 减少无谓的磁盘 IO，以及 Compaction 收敛版本、减少层数。

因为 LSM 从不原地覆盖旧数据，删除也只是写 tombstone，旧版本要等 Compaction 才清理，所以读必须从最新层往旧层逐层找。Bloom Filter 用极小内存在每层前做 O(1) 判断”这一层一定没有这个 key”，能把绝大多数 miss 挡在磁盘 IO 之外；Compaction 则把多层旧版本合并去重，从根上降低读放大。

3. WAL 的作用是什么？没有它会怎样？

结论先行：WAL 是为了防崩溃丢失——内存里的 MemTable 一旦进程崩溃就没了，必须先落日志才能在重启后恢复；没有它，已返回成功但尚未 flush 的写会直接丢失。

因为写路径里”写 MemTable”是内存操作、极快，但内存数据是易失的，只有 WAL 是持久化保证。写入顺序是”先写 WAL 再写 MemTable”，这样即使 MemTable 随进程一起消失，重启后也能从 WAL 重放恢复。没有 WAL，L 的写入就失去了持久性承诺。

LSM树——写多读少场景下的存储引擎王者