← 返回画廊

数据库为什么这样存：B+Tree 与 LSM-Tree 的取舍

读者画像：会写 CREATE INDEX、会用数据库，但没深究过存储引擎内部的工程师。目标：读完能回答「为什么 MySQL 选 B+Tree、RocksDB/Cassandra 选 LSM-Tree」，并能据此做技术选型和排查慢查询。

目录

  1. 一切的起点：磁盘/SSD 的物理约束
  2. B+Tree：为教科书里"最优雅"的结构
  3. LSM-Tree：把随机写变成顺序写的工程妥协
  4. 对照表：B+Tree vs LSM-Tree
  5. 真实场景选型
  6. 索引实战：最左前缀、覆盖索引、回表
  7. 总结

1. 一切的起点：磁盘/SSD 的物理约束

存储引擎的所有设计，最终都是在向物理硬件的脾气妥协。理解这一点，后面 B+Tree 和 LSM-Tree 的设计动机会豁然开朗。

1.1 机械磁盘（HDD）：随机写慢是物理定律

HDD 写数据需要磁头移动到目标磁道（寻道，seek）、等待目标扇区转到磁头下方（旋转延迟，rotational latency），然后才能写入。

也就是说，一次随机写的绝大部分时间花在"跑位置"上，而不是真正写数据。如果是顺序写，磁头几乎不需要大幅移动，一次寻道后可以连续写完一大片数据，单次开销被摊薄到可以忽略。这就是为什么 HDD 上随机 IOPS 通常只有几百，而顺序吞吐能达到 100~200+ MB/s——量级差异可以到百倍。

1.2 SSD：没有磁头，但一样怕随机写，只是原因换了

很多人以为 SSD 没有机械部件，随机写应该和顺序写差不多快。事实并非如此，原因在闪存的物理结构：

随机写模式下，脏数据和有效数据混杂在同一个 block 里，GC 要频繁地把有效数据"腾挪"出去再擦除，写放大严重；顺序写模式下，一个 block 里的数据大概率是"同批失效"的（比如整体被覆盖或整体过期），GC 几乎不用腾挪，写放大趋近于 1。

实测数据佐证了这个差异：某厂商 SATA SSD 上，顺序写 63.6K IOPS / 59.24 μs 延迟，随机写只有 12.8K IOPS / 302 μs 延迟——约 5 倍的 IOPS 差距、约 5 倍的延迟差距；另一款盘上也观察到类似的 4~5 倍差异。(The SSD Review)在带宽维度上，业界经验值是随机 I/O 可能比顺序慢 50~100 倍（这个更大的数字通常出现在小随机 IO 且队列深度低的场景）。

结论：无论 HDD 还是 SSD，顺序写都显著优于随机写，只是物理原因不同（寻道 vs 擦除+GC）。这是数据库存储引擎设计的第一性原理——如果能把大量小的随机写，转换成少量大的顺序写，就能获得数量级的性能提升。B+Tree 和 LSM-Tree 正是在这条约束下给出的两种不同答案。

2. B+Tree：为教科书里"最优雅"的结构

2.1 为什么不是二叉树、也不是哈希表

一句话：B+Tree 是"用高扇出换低树高，用有序叶子链表换范围查询能力"的结构，它是为磁盘 I/O 为瓶颈的时代量身定制的。

2.2 聚簇索引 vs 二级索引（以 InnoDB 为例）

InnoDB 的主键索引是聚簇索引（clustered index）：叶子节点直接存放整行数据，而不是行的地址。也就是说，表数据本身就是按主键顺序组织的一棵 B+Tree。

二级索引（secondary index）是另一棵独立的 B+Tree，它的叶子节点存的不是整行数据，而是索引列 + 主键值。(MySQL 官方文档)

CREATE TABLE users (
    id     BIGINT PRIMARY KEY,      -- 聚簇索引：叶子节点 = 完整行数据
    email  VARCHAR(255),
    name   VARCHAR(100)
);
CREATE INDEX idx_users_email ON users(email);
-- 二级索引 idx_users_email 的叶子节点存的是 (email, id)，不是整行

这意味着通过二级索引查询时，拿到的只是主键值，还要再拿这个主键值去聚簇索引查一次完整的行——这个过程叫回表，第 6 节会详细讲它的代价。

这也解释了为什么 InnoDB 强烈建议用自增整数做主键：如果主键是 UUID 这种无序值，每次插入都可能落在树的任意位置，导致随机 I/O 和频繁的页分裂；用自增主键，插入永远发生在树的最右端，天然是顺序写。

2.3 页分裂：B+Tree 写放大的根源

B+Tree 的每个节点对应一个磁盘页（InnoDB 默认 16 KB）。当往一个已经写满的页里插入新记录时，这一页放不下了，就要分裂（page split）：申请一个新页，把原页大约一半的记录挪过去，同时更新父节点的指针。

InnoDB 为了减少这种情况，在顺序插入时，默认给每个页预留 1/16 的空间；如果插入是乱序的（比如 UUID 主键），页最终大概只能利用到 15/16 左右的空间，也更容易触发分裂。(MySQL 官方文档 14.6.2.2)

页分裂的代价：

  1. 分裂本身要写两个页（原页 + 新页），还要写父节点更新指针——一次逻辑插入变成了多次物理写。
  2. 分裂后页利用率下降，磁盘占用增加（这也是一种空间放大）。
  3. 分裂可能级联：如果父节点也满了，父节点也要分裂，最坏情况下一路分裂到根节点。
  4. 数据不再连续存放，之后的范围扫描可能要跳更多的页，读性能也会下降。

这就是 B+Tree 写放大的根源：为了维持"有序 + 高扇出"这个对读友好的结构，写入时要付出页分裂、随机 I/O 和空间浪费的代价。B+Tree 是一个为读优化、向写妥协的结构。

2.4 B+Tree 的写放大量级直觉

一次 UPDATE 一行 100 字节的数据，如果这行恰好在一个 16 KB 的页里，理论上只需要写这 100 字节，但由于磁盘/文件系统是按页读写的，实际至少要重写这一整页（16 KB）—— 单次写放大约 160 倍（这也是为什么 WAL/redo log 存在的意义之一：先顺序写日志，脏页可以延迟刷盘再合并写）。如果这次写触发了页分裂，还要再加上多写一整个新页、更新父节点页的开销。

3. LSM-Tree：把随机写变成顺序写的工程妥协

LSM-Tree（Log-Structured Merge-Tree）最早由 Patrick O'Neil 等人在 1996 年的论文中提出（发表于 Acta Informatica, 1996, 33(4): 351–385）。(Springer)其设计目标非常直接：为写多的场景，把随机写彻底改造成顺序写，代价是读和空间上的一些牺牲。RocksDB、LevelDB、Cassandra、HBase、TiKV 都基于这个思想。

3.1 核心思路：MemTable + SSTable + Compaction

  1. WAL（Write-Ahead Log）：写入先顺序追加到磁盘上的日志文件，保证崩溃后可恢复。这一步本身就是顺序写。
  2. MemTable：数据同时写入内存里的一个有序结构（通常是跳表）。写操作到这里就算完成——不管是随机 key 还是顺序 key，对用户来说都是纯内存操作 + 一次顺序日志追加，没有随机磁盘 I/O。
  3. Flush 成 SSTable：MemTable 长到一定大小后，作为一个不可变的、内部有序的文件整体刷到磁盘，这个文件叫 SSTable（Sorted String Table）。刷盘是整体顺序写一个新文件，不是原地更新。
  4. 多层 SSTable 与 Compaction：磁盘上会积累许多 SSTable（通常按 Level 0、Level 1……组织）。后台进程周期性地把多个 SSTable 合并（compaction）成更大的、去重后的新 SSTable，同时清理被删除/被覆盖的旧版本数据。这也是顺序读多个文件、顺序写一个新文件的过程。

一句话：LSM-Tree 用"先攒在内存里、满了就整体顺序落盘、后台再顺序合并"的方式，把用户侧看到的随机写，转化成系统侧的顺序 I/O。这正好对上了第 1 节讲的物理约束：无论 HDD 还是 SSD，顺序 I/O 都比随机 I/O 快一个数量级以上。

3.2 代价一：读放大

数据可能同时存在于 MemTable、Level 0 的多个 SSTable、Level 1……因为一个 key 可能被多次更新，新版本和旧版本分散在不同层里。查询一个 key，最坏情况要依次查 MemTable，再查 Level 0 里所有可能重叠的文件（Level 0 内文件之间 key 范围可能重叠），再逐层往下查，直到找到或者查完所有层。

3.3 代价二：空间放大

因为更新/删除不是原地修改，而是写一条新记录（删除则写一个"墓碑" tombstone），旧版本数据在被 compaction 真正清理之前，会一直占着磁盘空间。

3.4 Compaction 策略的取舍：Leveled vs Size-Tiered

Compaction 策略本质上是在写放大、读放大、空间放大这三者之间选一个偏向：

Size-Tiered Compaction（STCS，Cassandra 默认策略之一）：相似大小的 SSTable 攒够一批就合并成一个更大的文件。合并频率低，写放大小，但同一个 key 的多个历史版本会长期共存在不同大小的文件里，空间放大和读放大都比较高（最坏情况空间放大是层级数量级，即 O(T)，T 为大小比例）。(ScyllaDB 分析)

Leveled Compaction（LCS，RocksDB 默认策略）：数据按 Level 严格分层，每一层是全局有序、内部不重叠的，一个 key 在某一层最多出现一次。这样空间放大和读放大都更可控，但代价是写放大高——一条数据从 Level 0 一路合并到 Level 5、6，可能被重写 5~6 次，每层合并比例通常是 10 倍，写放大可以到 10~30 倍这个量级。(相关分析总结)

选型经验：

3.5 LSM-Tree 为什么删除也贵

LSM-Tree 的删除不是物理删除，而是插入一条"墓碑"标记。这条墓碑要一直保留到 compaction 把它和它标记的所有旧版本一起清理掉——如果 compaction 没有触发（比如冷数据、大 key 范围删除），墓碑可能长期占用空间，甚至在读路径上拖慢查询（要扫过一堆墓碑才能确认某个 key 真的不存在）。这是 Cassandra 场景下著名的 "tombstone 过多导致读超时" 问题的根源。

4. 对照表：B+Tree vs LSM-Tree

维度B+Tree（MySQL InnoDB, PostgreSQL）LSM-Tree（RocksDB, Cassandra, HBase）
写路径原地更新，随机 I/O，可能触发页分裂先写内存 + WAL，顺序刷盘，后台顺序合并
写吞吐受随机 I/O 上限约束，扩展性一般顺序 I/O，写吞吐通常显著更高，尤其在 SSD/HDD 上
写放大中等，页级重写 + 页分裂（页大小/记录大小的比例级别，如 16KB 页改 100B 记录约 160x）依赖 compaction 策略：leveled 常见 10~30x，STCS 更低但空间/读放大更高
读路径定位单一位置，树高通常 3~4 层可能要查 MemTable + 多层 SSTable，依赖 Bloom Filter 优化
读放大低，接近 1 次逻辑查找对应几次页 I/O未优化可到大几十甚至上百；调优后普遍个位数到十几
空间放大低，一份数据一个位置（页有 1/16 预留空间）有，旧版本/墓碑未被 compaction 前占用额外空间；生产可调至 ~1.1x
删除原地标记删除后由后续维护/VACUUM 回收，代价可控墓碑机制，真正回收依赖 compaction，可能造成"墓碑膨胀"
范围查询原生优势：叶子节点有序 + 链表，直接顺序扫需要归并多层有序文件，通常比 B+Tree 慢，但仍支持
并发写入扩展性受锁和页竞争限制MemTable+immutable SSTable 天然对追加写友好，易于水平扩展
典型代表MySQL InnoDB、PostgreSQL、SQLite、OracleRocksDB、LevelDB、Cassandra、HBase、TiKV 底层

5. 真实场景选型

5.1 写多读少的日志/事件流 → 倾向 LSM-Tree

日志系统（应用日志、审计日志、消息队列持久化层）的特点是：几乎只 append，很少更新，读通常是按时间顺序批量读最近的数据，很少做随机点查。这正是 LSM-Tree 的甜蜜区：写入走顺序 I/O，吞吐高；读的场景多是范围扫描最新数据（往往还在还没被 compact 的高层或者内存里），代价可控。选择 size-tiered 或按时间窗口的 compaction 策略（很多时序数据库用 TWCS，Time-Window Compaction Strategy），空间放大和读放大的劣势进一步被时间局部性抵消。

5.2 读多写少的用户表 → 倾向 B+Tree

典型的业务系统用户表：一次写入（注册），大量读（登录校验、资料展示、外键关联查询），偶尔更新几个字段。这种场景下 B+Tree 的优势明显：点查只需要 3~4 次 I/O，不需要 Bloom Filter 之类的辅助结构；不存在 compaction 带来的读放大和后台 I/O 抖动（LSM-Tree 的 compaction 会周期性占用磁盘带宽和 CPU，可能造成写入毛刺）；事务、外键约束、复杂 JOIN 这些 B+Tree 存储引擎（MySQL/PostgreSQL）生态更成熟。这也是为什么绝大多数传统 OLTP 业务库首选 MySQL/PostgreSQL，而不是直接上 RocksDB。

5.3 时序数据 → 看写入模式细分

时序数据（监控指标、IoT 传感器数据）表面上和日志类似，写多读相对少，天然适合 LSM-Tree 类存储（InfluxDB 的 TSM 引擎、TiKV/HBase 承载时序场景都是 LSM 系）。但要注意两点区别：

6. 索引使用的实战：最左前缀、覆盖索引、回表

这一节聚焦 B+Tree 索引（以 MySQL InnoDB 为主），因为这是绝大多数工程师日常打交道最多的存储引擎实现。

6.1 最左前缀原则

联合索引 (a, b, c) 在 B+Tree 里的排序方式是：先按 a 排，a 相同的再按 b 排，b 相同的再按 c 排。这意味着索引只能被"从左边连续使用"：

CREATE INDEX idx_abc ON t(a, b, c);

-- 能用上索引（走 a，或 a+b，或 a+b+c 的连续前缀）
WHERE a = 1
WHERE a = 1 AND b = 2
WHERE a = 1 AND b = 2 AND c = 3
WHERE a = 1 AND c = 3   -- 只能用上 a 这一段，c 这个条件不能利用索引有序性，只能在已筛出的 a=1 结果里做过滤

-- 用不上索引（跳过了最左列 a）
WHERE b = 2
WHERE c = 3

原因很直观：树里数据先按 a 排序，如果不给 a 的条件，整棵树里 b、c 的值是杂乱无章的，没法用二分/范围扫描去定位，只能全表扫。

6.2 覆盖索引：不回表的捷径

前面提到，二级索引的叶子节点存的是 (索引列, 主键值)，不是整行数据。如果查询需要的所有列，二级索引本身就能提供（不需要再去聚簇索引取其他列），这就叫覆盖索引（covering index）——查询只需要访问一棵 B+Tree，不需要回表。

CREATE INDEX idx_users_email ON users(email);

-- 需要回表：id 是主键会自动带出，但还要 name 这一列，索引里没有
SELECT id, email, name FROM users WHERE email = 'a@b.com';

-- 覆盖索引，不回表：查询只用到 email 和 id，索引叶子节点已经包含这两者
SELECT id FROM users WHERE email = 'a@b.com';

-- 常见实战技巧：把常用查询列加入联合索引，让它成为覆盖索引
CREATE INDEX idx_users_email_covering ON users(email, name);
SELECT name FROM users WHERE email = 'a@b.com';  -- 不回表

覆盖索引省下的是「二级索引查到主键后，再去聚簇索引做一次随机 I/O 查整行」这一步——在数据量大、二级索引选择性低（命中行数多）的场景下，这个优化的收益可以很可观，因为省掉的是一次次随机 I/O，而不是顺序扫描。

6.3 回表的代价

-- users 表 100 万行，email 有索引，name 没在索引里
SELECT id, email, name FROM users WHERE email LIKE 'a%';

执行过程：先在 idx_users_email 这棵 B+Tree 上定位到以 a 开头的 email 范围（顺序扫描一段），拿到一批主键 id；然后逐个拿这些 id 去聚簇索引里查整行——这一步是随机 I/O，因为二级索引里筛出的这批 id 在聚簇索引里的物理位置通常并不连续。如果符合条件的行数很多，这批随机 I/O 的总代价可能远超直接全表扫描（全表扫描虽然要扫全部数据，但至少是顺序 I/O）。

这就引出下一个反直觉的点。

6.4 为什么有时候索引反而更慢

优化器会估算：用索引走「索引扫描 + N 次回表随机 I/O」的代价，和「直接全表顺序扫描 + 内存里过滤」的代价，哪个更低。

实战建议：不要迷信"加了索引就一定快"，用 EXPLAIN 看 rows（预估扫描行数）和 Extra（是否 Using index、Using filesort、Using temporary），必要时用 EXPLAIN ANALYZE 看真实执行时间和预估的偏差，再决定要不要调整索引或强制 FORCE INDEX。

EXPLAIN ANALYZE
SELECT id, email, name FROM users WHERE email LIKE 'a%';
-- 关注：
-- 1. 是 Index Scan/Range Scan 还是 Seq Scan（Bitmap Heap Scan 是折中态）
-- 2. actual rows 和 estimated rows 差距大不大（统计信息过期的信号）
-- 3. 有没有额外的 Sort/Filter 节点吃掉了大部分时间

7. 总结

存储引擎的选择，本质上是在"磁盘/SSD 讨厌随机写"这条物理定律下，选择把复杂度放在写路径还是读路径：

参考来源