当年是谁发明了LSM Tree？为什么能颠覆B-Tree？

为什么今天几乎所有需要"疯狂写入"的数据库——Cassandra、HBase、RocksDB、LevelDB、InfluxDB，甚至 Kafka 的存储引擎思路——都绕不开一个诞生于 1996 年、几乎没有人在当年注意到的冷门论文？

这篇论文既没有炫技的算法，也没有华丽的证明，作者甚至不是搞分布式系统出身的人。但三十年后，它几乎重新定义了"写多读少"系统的存储方式。

它就是 LSM Tree —— Log-Structured Merge-Tree。

时间回到 1990 年代初。

那是关系数据库如日中天的年代。Oracle、Sybase、Informix 这些厂商都在打磨同一件事情：B 树（B-Tree）索引。B 树几乎是那个年代"数据库存储"的代名词——从 IBM 的 System R 到后来的 MySQL InnoDB，B 树统治了几乎所有磁盘数据库。

但有一类系统开始感到吃力：写入密集型系统。

想象一下 90 年代的电信计费系统、银行流水记录、早期的传感器采集系统——它们的特征很一致：

• 数据几乎只追加，很少更新；

• 写入量巨大，且要求持续、稳定；

• 读取相对较少，或者可以接受一点延迟；

• 存储介质是机械硬盘，寻道（seek）是最贵的操作。

这里有一个当时工程师都心知肚明、却很少被系统性解决的痛点：机械硬盘的随机写代价极高。磁头要在盘片上来回移动寻找目标扇区，一次随机 IO 可能是顺序 IO 的成百上千倍慢。而 B 树的更新，恰恰天生是随机的——一条记录改了，就要去磁盘上对应的那个页面原地修改。

数据库厂商当时的做法，是不断优化缓存、优化预读、优化磁盘调度算法，本质上是在"讨好"随机 IO，而不是"消灭"它。

真正提出问题的，是在贝尔实验室系统工作过、后来转向数据库研究的 Patrick O'Neil。他和合作者 Edward Cheng、Dieter Gawlick、Elizabeth O'Neil 注意到一个现象：如果一个系统的写入负载持续高企，那么无论 B 树怎么调优，它终究要为每一次写付出一次随机 IO 的代价。这不是实现问题，是结构性问题。

B 树：为读优化，为写买单。

B 树的设计初衷，是让任意一条记录的查找都能在 O(log n) 的磁盘 IO 次数内完成。这个设计对读非常友好——树的每一层都对应固定的磁盘页面，随手一查就能定位。

但代价是：每次插入或更新，都可能触发一次原地修改，甚至一次页分裂（page split）。在写入频繁的场景下，这意味着磁盘的磁头要不停地在盘片各处"跳来跳去"，效率断崖式下跌。

当年的工程师并非没意识到这一点，他们用了各种缓解手段：写缓冲区、延迟刷盘、批量提交。但这些都是在掩盖问题，而不是改变问题的本质——数据落盘的顺序，仍然由业务逻辑的写入顺序决定，而不是由磁盘最舒服的方式决定。

哈希表、跳表等内存结构：解决不了持久化问题。

哈希表在内存里效率很高，但一旦涉及到持久化到磁盘，同样面临着"如何有序地、批量地落盘"这个老问题。跳表（SkipList，同样是 20 世纪 90 年代 William Pugh 提出）解决的是内存中有序结构的并发和实现简单性问题，本质上也没有回答"磁盘写入模式"这件事。

日志（Log）结构：接近答案，但少了一步。

其实业内已经有"只追加写日志"的思路，用于崩溃恢复（WAL，Write-Ahead Log）。日志文件写入是纯顺序的，磁盘友好。但日志天生的问题是：它只管写，不管查——你要查一条记录，理论上得从头到尾扫一遍日志，这在读多的场景下是灾难。

于是问题变成了：能不能让数据写入像日志一样顺序，同时又能像索引一样被高效查询？

1996 年，Patrick O'Neil、Edward Cheng、Dieter Gawlick 和 Elizabeth O'Neil 在《Acta Informatica》发表了论文《The Log-Structured Merge-Tree (LSM-Tree)》。

他们的洞察非常朴素，却极具颠覆性：与其追求每一次写入都立刻组织成最终形态的索引结构，不如把写入攒起来，先顺序地扔到磁盘，再通过后台"合并"的方式，把这些零散的数据逐步整理成有序的整体。

具体来说，LSM Tree 把存储分成了层级：

• 最新写入的数据先进入内存中的一个有序结构（后来的实现常用跳表或红黑树），这部分叫 MemTable；

• 当内存结构长到一定大小，就整体、顺序地刷写到磁盘上，形成一个不可变的有序文件，这部分叫 SSTable（Sorted String Table）；

• 磁盘上会积累越来越多的 SSTable，后台有一个合并（Compaction）进程，持续地把多个 SSTable 合并成更大、更有序的文件，顺便清理掉过期或被覆盖的数据。

这个设计的精妙之处在于：所有对磁盘的写操作，无论是刷写 MemTable 还是合并 SSTable，都是顺序写。随机写被彻底移出了关键路径，取而代之的是查询时可能需要多查几个文件——但这个代价可以通过布隆过滤器（Bloom Filter）、索引块等手段大幅压低。

这篇论文在发表当年几乎没有激起太大水花——它更像是一篇工程笔记式的理论总结，而不是一鸣惊人的突破。真正让它被全世界知道的，是十年后的两篇工业界论文：Google 的 Bigtable（2006） 和随后的 LevelDB，以及 Amazon 的 Dynamo（2007）。Google 的工程师们在设计 Bigtable 时，独立地走向了与 O'Neil 几乎一致的结论，并第一次把 LSM Tree 的思想在超大规模系统中验证成功。

不需要贴太多代码，只看一件事：为什么查询一条记录，要按照"内存 → 最新 SSTable → 更老的 SSTable"的顺序去找？

以 LevelDB / RocksDB 的思路举例，一次 Get(key) 的核心逻辑大致是：

• 先查 MemTable（最新写入，还没落盘）；

• 再查 Immutable MemTable（正在被刷盘的旧内存表）；

• 再依次查磁盘上各层 SSTable，从最新的层开始。

为什么是这个顺序？因为 LSM Tree 允许同一个 key 出现在多个地方——你更新一条记录，并不是去磁盘上找到它原地覆盖，而是简单地把新版本追加写入。所以，"最新的数据在哪里，就先查哪里"，一旦找到就立刻返回，这样保证了正确性，也保证了大多数情况下不需要扫描全部层级。

这一段设计背后的取舍是明确的：用查询路径上的额外几次比较，换取写入路径上彻底消灭随机 IO。这是典型的"不对称优化"——因为在写多读少的场景里，写的代价被无限放大，而读的代价可以被摊薄。

LSM Tree 之所以耐人寻味，是因为它同时体现了好几种后来被反复验证的工程哲学：

• 顺序 IO 优先：把所有代价高的随机操作，转化为代价低的顺序操作；

• 不可变性（Immutability）：SSTable 一旦写入就不再修改，简化了并发控制，也让缓存和复制变得天然安全；

• 延迟合并 / 惰性整理：不追求每次写入都立刻整理到位，而是把整理work推迟到后台，用时间换取写入吞吐；

• 空间换时间：允许同一个 key 短期内存在多个版本，用额外的存储空间换取写入性能；

• 分层与合并（类似归并排序思想）：SSTable 之间的合并，本质上就是外部归并排序在存储引擎里的复用。

这些思想没有一个是全新发明的，LSM Tree 真正的贡献，是把它们组合在了一个统一、可落地的存储模型里。

进入 2000 年代后期，两件事同时发生：

第一，互联网数据规模爆炸式增长，写入密集型场景（日志、消息、时序数据、用户行为流）越来越普遍，B 树式的关系数据库在这些场景下逐渐力不从心。

第二，Google 用 Bigtable 证明了 LSM Tree 可以在生产环境里支撑起海量、持续的写入压力，并且这套模型被开源出的 LevelDB 直接"复刻"，任何工程师都能读懂它的实现。

于是一大批后来的系统几乎是"抄作业式"地采用了这套思路：Cassandra 直接借鉴了 Dynamo 和 Bigtable 的设计；HBase 是 Bigtable 的开源实现；RocksDB 是 Facebook 在 LevelDB 基础上为高性能场景重写的版本；InfluxDB、ClickHouse 的 MergeTree 系列引擎，虽然细节各不相同，但底层逻辑都能追溯到"先顺序写、再后台合并"这个核心范式；就连 Kafka 的日志分段（log segment）与压缩（log compaction）机制，思想内核也与 LSM Tree 一脉相承。

它赢的原因其实很朴素：它把"磁盘怕随机写"这个物理世界的硬约束,变成了软件设计的第一原则，而不是事后补丁。

今天的硬件环境和 1996 年已经完全不同，这也让 LSM Tree 面临新的审视。

SSD 的普及削弱了"随机写代价远高于顺序写"这个前提——虽然 SSD 依然偏好顺序写（涉及擦除块和写放大问题），但差距不再像机械硬盘那样悬殊。这也是为什么近年出现了不少针对 SSD 特性重新设计的存储引擎，试图在"读放大、写放大、空间放大"这个经典的 LSM 三角权衡里找到更适合闪存的平衡点，比如各种改进型的 Compaction 策略（Leveled、Tiered、Universal）。

新的数据结构也在挑战 LSM 的地位，比如 B-epsilon Tree（Bε-Tree），它试图在 B 树的读性能和 LSM 树的写性能之间找到一个中间态，被用在 TokuDB、BetrFS 等系统中。

计算存储（Computational Storage）与 NVMe 的普及，让一部分 Compaction 这样的后台整理工作有可能下沉到存储设备本身完成，减少 CPU 和主存的参与。

Rust、Go 等语言与异步 IO 模型（如 io_uring）改变的更多是实现效率，而不是架构本身——LSM 的核心思想（顺序写 + 后台合并 + 分层查询）在可预见的未来仍然会是写密集型系统的默认答案，因为它解决的不是某种硬件的局限，而是"追加优于覆写"这个更底层的物理与工程规律。

LSM Tree 及其变种，如今支撑着相当一部分现代基础设施：

• LevelDB / RocksDB：Google 与 Facebook 出品，被无数系统当作嵌入式存储引擎，包括早期以太坊客户端、TiKV 的底层存储；

• Cassandra、HBase：分布式 NoSQL 数据库的经典代表；

• InfluxDB：时序数据库，天然写多读少；

• ClickHouse：MergeTree 系列引擎的命名本身就在向这套思想致敬；

• Kafka：消息系统的日志分段与压缩机制；

• CockroachDB、TiDB：底层存储普遍采用 RocksDB 作为 LSM 引擎。

它们的共同点是：都身处一个写入压力巨大、且能够容忍一定后台整理延迟的世界。

计算机的发展史，从来不是谁写出了最聪明的代码，而是谁看清了那个时代硬件最真实的脾气，并且顺着它，而不是逆着它去设计。