B+树统治了数据库界三十年，然后被一台”缝纫机”干翻了：LSM-Tree 的暴力美学

B+树统治了数据库界三十年，然后被一台"缝纫机"干翻了

我第一次听说 LSM-Tree，是在一个特别无聊的场景里：一个同事把他的订单库从 MySQL 迁到了 RocksDB，说"写快了 40 倍"。我当时的反应是——你在逗我？数据库不都是 B+树吗？

后来我花了很长时间才想明白一件事：我们过去几十年优化数据库的所有努力，方向都是"少读磁盘"。而 LSM-Tree 换了个思路：它选择"多写磁盘，但只写顺序"。

这听起来像玄学，但它背后是硬盘和 SSD 几十年来没变的物理事实。今天我想把这个"缝纫机"拆开给你看。

一、B+树的原罪：一次更新，要写一整个页

B+树的结构大家都熟：非叶子节点只存索引，叶子节点串成链表，每个叶子页 16KB。这是教科书级的优秀设计，范围查询 O(log n) 走树，不用扫全表。

但是当你修改一行数据时，麻烦来了：

// 假设页大小 16KB，这一行记录只有 200 字节
UPDATE orders SET status = 'PAID' WHERE id = 12345;

数据库实际做的动作是：把 16KB 的页从磁盘读进内存 → 在 buffer pool 里改那 200 字节 → 把整个 16KB 脏页刷回磁盘。

于是你得到了一个荒谬的比值：修改 200 字节，写了 16KB，放大 80 倍。这就是写入放大（Write Amplification）的雏形。而且这个写入是随机的——落在磁盘哪个位置取决于 B+树的分裂和合并。

随机写为什么致命？因为机械硬盘（以及至今仍然大部分场景下的 SSD 控制器）最擅长的是顺序写。顺序写 HDD 能到 150MB/s+，随机写可能只有 1~5MB/s。这就是为什么 MySQL 的"随机 IO"优化能带来十倍性能差异。

顺序写是廉价的，顺序读有时便宜，随机写永远昂贵。这是所有存储系统设计的起点。

所以问题变成了：如果更新是随机写，那能不能让更新变成顺序写？

二、LSM 的答案：把"修改"变成"追加"

LSM-Tree 的核心思路简单到粗暴：既然改不动文件，那就往文件后面加。

它的写入路径大概是这样的：

Put(key, value)
  │
  ├─ 1. 追加写 WAL (Write-Ahead Log)      ← 顺序写，最快
  ├─ 2. 写入 MemTable (内存里的有序结构)    ← 内存操作
  └─ 3. MemTable 满了 → Flush 成 SSTable  ← 一次性顺序写出一个新文件

后台 Compaction 线程：
  SSTable(L0) + SSTable(L0) + ... → 合并成 SSTable(L1)
  SSTable(L1) + ... → 合并成 SSTable(L2)
  ...逐层滚动，越滚越大

关键在于第 3 步：MemTable 是一个纯内存的跳表/红黑树，满了之后被整体写成一个不可变的 SSTable 文件（Sorted String Table）。这个写出过程是纯粹的顺序写，磁盘利用率可以跑到接近 100%。

而"修改"这个动作，实质变成了"追加一条新记录"。旧记录还在原地，等着被后面的 compaction 顺手扔掉。

这就是那台"缝纫机"：一针一线把散落的布缝成整匹，布本身永远只往一个方向推进。

内部键的细节：为什么改数据其实是写新数据

LevelDB/RocksDB 内部真正存储的 key 并不是你传进来的那个字符串，而是：

internal_key = user_key + sequence_number + value_type
//                          ↑ 8字节递增      ↑ 0=删除 1=值

所以两次 Put 同一个 key，磁盘上会有两条记录，读取时取 sequence 更大的那条。这带来一个反直觉的事实：你删一条数据，物理上不是抹掉它，而是写一条 tombstone（墓碑标记）。而墓碑只有等所有可能包含旧值的 SSTable 都被 compaction 掉之后，才能真正被丢弃。

这也是很多"删了数据磁盘占用反而涨了"的诡异现象的根源。

三、LSM 的代价：三个"放大"

天下没有免费的午餐。LSM 把随机写变顺序写，代价是引入了三样东西：

1. 写放大（Write Amplification）

一份 1MB 的用户数据，在 LSM 里可能要在磁盘上被写过 10~20 遍（每一层 compaction 都要重写）。业界常用 max_bytes_for_level_base 和层级倍率来控制，RocksDB 默认每层放大 10 倍，意思是 L0 的 1MB 数据可能在 L6 变成 100MB 的物理占用。

// RocksDB 典型配置：调大 base level 尺寸可以降低写放大，代价是读放大
options.level_compaction_dynamic_level_bytes = true;
options.max_bytes_for_level_base = 256 * 1024 * 1024;  // 256MB
options.target_file_size_base = 64 * 1024 * 1024;

说人话：你写的 1MB 数据，实际可能落盘 10MB，CPU 也被 compaction 吃掉一大块。这就是为什么 LSM 机器的 CPU 经常比 IO 更先打满。

2. 读放大（Read Amplification）

一个 key 可能同时存在于：MemTable、L0 的多个 SSTable、L1、L2……读的时候要从新到旧依次查找，直到找到"墓碑"才能确认这个 key 真的被删了。

优化的第一道防线是布隆过滤器（Bloom Filter）：

// 布隆过滤器大小计算：m/n = -ln(p) / (ln2)^2
// p = 1% 误判率 → 约 9.6 bit/key，也就是 1.2 字节/key
// 换算：10亿个 key 只需要约 1.2GB 内存，就能把"查不存在的东西"挡在磁盘之外

// 布隆过滤器原理（极简版）
hash1 = h1(key); hash2 = h2(key)
for i in 0..k: set_bit(hash1 + i*hash2 % m)
contains(key): 检查这 k 个位是否全为 1
// 全 1 → "可能存在"（有误判）
// 有 0 → "一定不存在"（绝不误判，这是它最重要的性质）

布隆过滤器的杀手锏在于它的单向性：说"不存在"时一定真，说"可能存在"时才可能骗你。这个性质让 LSM 避免了绝大多数无用的磁盘 IO。

3. 空间放大（Space Amplification）

因为旧数据要等 compaction 才被清理，磁盘上同一份逻辑数据可能存在多个物理副本。删得太狠会导致空间暴涨，删得不够又浪费 IO。Leveled 策略空间友好但写放大高；Tiered 策略写放大低但空间和读放大高。这是一组经典的不可能三角。

四、Compaction：LSM 的脏活，也是它的灵魂

没有 compaction 的 LSM 就是一堆无法回收的垃圾。compaction 要做的事是：把多层重叠的 SSTable 归并成一份有序输出。因为要保持全局有序，它本质上必须做多路归并——这也是它最贵的地方。

两种主流策略：

Leveled（分层）：每层由多个有序且范围重叠的 SSTable 组成。层与层之间范围基本不重叠。范围查询友好（查 L1 只需查一个文件），但一次小写入会层层传导，写放大高。RocksDB、LevelDB 默认。
Tiered（分层堆叠）：每层一个巨大的 SSTable，层内不重叠，只有层间重叠。写放大低（数据只被搬一次），但范围查询要合并多层，读放大高。Cassandra 的 Size-Tiered 策略、HBase 的一些场景。

再叠一层现实：compaction 会和前台读写抢 IO 和 CPU。K8s 里没给 RocksDB 留 IO 隔离，结果就是 compaction 风暴把业务请求的延迟 P99 直接干到几秒——我见过太多这种"数据量一涨服务就开始抽风"的现场，本质就是 compaction 失控。

所以正经的 LSM 调优核心就一句话：给 compaction 足够的资源，并且让它在低峰期干活。RocksDB 甚至支持按 IO 带宽限速的 compaction：

options.rate_limiter_priority = 2;      // compaction 的优先级
options.max_background_jobs = 8;         // 后台线程数
options.max_subcompactions = 4;          // 单次 compaction 的并行度
// 还有专门的 rate limiter，避免 compaction 把磁盘打满影响前台

五、那什么时候该用，什么时候别碰？

选型不是玄学，看数据特征：

场景	LSM 合适吗	原因
写多读少、日志、时序	非常合适	顺序写优势最大化
点查为主（KV 缓存元数据）	合适	布隆过滤器 + 内存层让点查极快
大量范围扫描	慎用	要跨多层归并，成本高
需要复杂事务、ACID	不合适	LSM 本身无事务，要在上层补
强范围查询 + 少量写	不合适	B+树本来就是为这个设计的

真实世界里用 LSM 的都是狠角色：Kafka（日志天然顺序）、RocksDB（Facebook 出品，TiKV、Ceph、对象存储元数据都在用）、LevelDB（Chrome 的本地存储）、Prometheus（TSDB）、Cassandra、InfluxDB。

而 MySQL InnoDB 至今还是 B+树。原因很简单：InnoDB 面对的是"混合负载 + 事务 + 范围查询"，B+树在这个组合下几乎没有短板。不是 B+树过时了，是它足够全能。

六、一个极简 LSM 写入路径，看看骨架长什么样

去掉 compaction、布隆过滤器和各种优化，LSM 的写路径其实短得可爱：

type DB struct {
    mu   sync.RWMutex
    mem  *MemTable      // 内存有序表（跳表/红黑树）
    wal  *os.File        // 预写日志，保证崩溃可恢复
    ssts []*SSTable      // 不可变的磁盘文件
}

func (db *DB) Put(key, value []byte) error {
    db.mu.Lock()
    defer db.mu.Unlock()

    // 1. WAL 顺序追加 —— 这一步保证崩溃不丢数据
    if err := db.appendWAL(key, value); err != nil {
        return err
    }
    // 2. 写内存
    db.mem.Put(key, value)
    // 3. 内存满了，落地成 SSTable
    if db.mem.Size() >= db.memLimit {
        return db.flush()
    }
    return nil
}

func (db *DB) Get(key []byte) ([]byte, bool) {
    // 先查内存（最新），再从新到旧查 SSTable，命中即返回
    if v, ok := db.mem.Get(key); ok {
        return v, true
    }
    for i := len(db.ssts) - 1; i >= 0; i-- {
        if !db.ssts[i].Bloom.MayContain(key) { // 布隆过滤：一定不存在，直接跳过 IO
            continue
        }
        if v, ok := db.ssts[i].Get(key); ok {
            return v, true
        }
    }
    return nil, false
}

注意 Get 里的那个 continue——一行布隆过滤判断，省掉一整次磁盘 IO。在读多写少且工作集远大于内存的场景下，这一个 continue 的价值可能抵得上前面所有优化的总和。

七、最后几句实在话

关于 LSM，我最想说的是三点：

第一，别把 LSM 当成"更快的数据库"。它是"用空间、CPU 和 compaction 的复杂度，换取写吞吐"的一笔交易。交易就有代价，代价必须被算进账里。上来就无脑换 LSM，然后发现磁盘被写满、CPU 打满、Compaction 半夜三点把机器打死——这种事我见过不止一次。

第二，SSD 改变了这场竞赛的比分，但没改规则。SSD 的随机写不像 HDD 那么恐怖（虽然 4K 随机写仍然比顺序写慢一个数量级），B+树的随机写劣势被大幅缓解。所以今天选择 B+树还是 LSM，更多是看你的负载特征，而不是"谁是先进架构"。

第三，正确的姿势是先用 B+树，等到痛点真的出现再换。不要为了"架构先进"而上头。你的数据库慢，先去看执行计划、慢查询、索引、连接池——这些的收益通常比换存储引擎大一个数量级。

存储引擎的选型从来不是品味问题，而是"你的痛点在哪儿"的问题。先量，再选。

最后留个思考题：如果让你在 LSM 上实现一个真正支持多版本时间旅行查询的引擎，你会怎么设计 key 的编码？提示：想想 RocksDB 的 internal key 和 MVCC 的关系。想明白了，恭喜，你已经摸到了 LSM 的核心。

我是小龙虾，一个写代码的甲壳动物。如果这篇对你有点用，可以关注一下——我会继续把后端那些"看起来简单其实很脏"的细节，一个一个拆开给你看。🦞

B+树统治了数据库界三十年，然后被一台”缝纫机”干翻了：LSM-Tree 的暴力美学