在深入数据系统的世界时，我们常常惊叹于上层架构的宏伟，但支撑这一切的，往往是那些看似朴素却充满智慧的底层设计。在 DDIA 第三章中，SSTable 与 LSM 树无疑就是这样的基石。

这趟探索之旅，始于一个简单构件——SSTable，它像一块块乐高积木，虽好用但略显呆板。随后，我们将看到 LSM 树这套“动态系统”是如何赋予这些积木生命，搭建出能抵御写入洪流的坚固堡垒。最后，我们将站在更高的视角，探讨一个经典问题：既然 LSM 树如此强大，为何像 MySQL 这样的关系型数据库巨头，却选择坚守 B+ 树的阵地？

这不仅是对一个数据结构的剖析，更是一场关于设计哲学与工程权衡的深度思辨。

第一幕：SSTable——一块有序且不可变的坚实地基

SSTable（Sorted String Table）是 LSM 树在磁盘上的基本组成单位。它的设计法则纯粹而简单，牢记两点即可：

  1. 内部有序：文件内的键值对，严格按照键（Key）排序。
  2. 不可变（Immutable）：一旦写入，永不修改。

一个 SSTable 文件并非一块铁板，而是由多个部分精密组成的，好比一本字典：

  • 数据块 (Data Block)：字典的“书页”，存储着一小段连续的、有序的键值对。一个 SST 文件中通常会有成百上千个 Data Block（取决于文件大小和 block size 配置，例如 4MB 数据 flush 下来，block size=16KB，大约会有 256 个 Data Block）。
  • 索引块 (Index Block)：字典的“页眉导引词”，记录每个 Data Block 的边界键及其位置，便于快速定位。
  • 元索引块 (Metaindex Block)：记录 Bloom Filter、属性信息等元数据块的位置。
  • 文件尾 (Footer)：固定在文件末尾，记录索引块和元索引块的位置，并带有魔数，是读取 SSTable 的入口。

这种结构带来了显而易见的好处：

  • 读取高效：在常见缓存命中的场景下，查找通常只需一次磁盘 I/O（目标 Data Block），范围查询更是高效的磁盘顺序读。
  • 合并顺序化：多个 SSTable 的合并过程逻辑上类似归并排序，以顺序读写为主，相对高效。但同时，也会带来 写放大 的问题。

然而，“不可变”的特性，也带来了致命的弱点：无法高效地处理单次写入。为一个新键值对而重写整个几 GB 的文件，无异于天方夜谭。SSTable 是优秀的“只读”构件，但它需要一套动态系统来盘活它。

第二幕：LSM 树的诞生——化零为整的写入艺术

LSM 树（Log-Structured Merge-Tree）就是那套盘活 SSTable 的系统。它没有改变 SSTable，而是设计了一套全新的工作流，其核心思想是：将所有随机、零散的写入，在内存中“攒”成有序的大块，再“铸造”成新的 SSTable。

这个过程由两大核心组件驱动：

  1. MemTable (内存表)：一个内存中的有序数据结构（如跳表）。所有写请求（增、删、改）都先在这里完成，速度如电光石火。
  2. 刷盘 (Flush)：当 MemTable 达到预设大小（例如 4MB），它会被冻结为 Immutable MemTable。随后后台线程会将它的内容整体写入磁盘，生成一个新的 SST 文件。

关键点：一次 flush = 一个新的 SST 文件。但这个文件内部会根据配置的 block size（如 16KB）被切分成多个 Data Block（例如 4MB ÷ 16KB ≈ 256 个 Data Block），并在文件末尾生成索引块、元索引块和 Footer。

这个过程周而复始。随着系统运行，磁盘上会不断出现新的 SST 文件：0001.sst, 0002.sst, 0003.sst…

第三幕：与“熵增”的对抗——在混沌中维持秩序

多个 SST 文件的存在，引出了 LSM 树设计中最核心的一个事实，也是初学者最容易困惑的地方：新生成的 SST 文件之间，键范围是会重叠的，它们并非全局有序！

0001.sst 可能存储了键 apple 和 zebra，而 0002.sst 可能存储了键 banana。这种“混沌”状态，是为换取极致写入性能的必然结果，但也给系统带来了新的挑战：

  • 读放大：在 Level-0，由于文件范围可能重叠，查找一个键需要从最新文件开始逐个回溯。而在更高层（L1+），文件范围不重叠，可以二分定位到唯一文件，大幅优化读取效率。
  • 空间放大：被更新或删除的旧数据，依然躺在旧 SST 文件中，浪费着磁盘空间。

为了对抗这种无序带来的“熵增”，LSM 树必须依赖它的第三个核心组件： 后台合并 (Compaction)：这是一个持续运行的“内务整理”线程。它不知疲倦地：

  • 选择磁盘上若干个 SST 文件；
  • 将它们读入内存，进行归并，丢弃所有过时和已删除的数据；
  • 将合并后的、更紧凑、更干净的结果，写入一个新的、更大的 SST 文件；
  • 最后，安全地删除那些被合并的旧文件。

在更精巧的实现（如 RocksDB）中，Compaction 还引入了**分层（Levels）**策略。新刷盘的文件都位于允许键范围重叠的 Level-0，而 Compaction 会将它们不断合并、推向更高层级（Level-1, Level-2…）。在这些高层级中，SST 文件之间保证键范围互不重叠，从而极大地优化了读取效率。

至此，LSM 树的全貌浮出水面：它是一个由 MemTable、磁盘上 动态增删的 SST 文件集合、以及 后台 Compaction 三者协同工作的精密系统。它牺牲了数据的“规整性”，换来了写入的“流畅性”，再通过后台任务，孜孜不倦地将系统从混沌中拉回秩序。

终幕：B+树之辩——为什么 MySQL 不选择 LSM 树？

理解了 LSM 树的内在权衡，我们便能回答那个经典问题：为何 MySQL（InnoDB）坚守着 B+ 树的阵地？

答案是：它们的“天命”不同。

MySQL/InnoDB 的使命，是服务在线事务处理（OLTP）。 它的战场是电商、金融、社交应用。这些场景最需要的是：

  • 稳定且极低的读取延迟：B+ 树紧凑的页结构，保证了通过主键查找，通常只需 3–4 次磁盘 I/O，延迟稳定可控。LSM 树的读取路径则更长，延迟抖动也更大。
  • 高效的更新模型：B+ 树支持页级原位修改，通常能在少量页操作中完成更新。虽然可能发生页分裂，但整体延迟比 LSM 的“追加新版本”模式更可控。
  • 成熟的事务与锁：B+ 树的行、页结构，是实现行级锁、间隙锁等复杂并发控制的天然土壤。

LSM 树的使命，是服务写入密集型负载。 它的战场在日志、监控、物联网等数据摄取场景。它优先保证的是 极致的写入吞吐量。

因此，这不是一场谁更先进的较量，而是一场 场景适配性 的选择。MySQL 为了最广泛的 OLTP 用户，选择了 B+ 树这件“通用性最强、读取最稳的甲胄”。

当然，世界在融合。Facebook 为 MySQL 开发的 MyRocks 存储引擎，就是将 LSM 树的心脏植入了 MySQL 的身体，以应对其自身独特的、写入超密集且空间敏感的业务。这恰恰证明，没有万能的架构，只有最合适的选择。

结语

从 SSTable 的静态之美，到 LSM 树的动态之衡，再到与 B+ 树的哲学之辩，我们完成了一次深入数据引擎核心的旅行。我们看到，任何一个优秀的设计，都不是在追求某个单一指标的极致，而是在一系列相互冲突的目标之间，寻找一个优雅的平衡点。理解这些权衡，并内化为自己的设计直觉，正是我们“把 DDIA 读厚”的意义所在。