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

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

## 目录

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

---

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

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

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

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

- 寻道时间：约 4~10 ms
- 旋转延迟：7200 转/分的盘，平均延迟约 4.17 ms
- 实际数据传输：通常 < 0.1 ms

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

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

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

- 闪存以 **page**（通常 4~16 KB）为单位读写，以 **block/erase block**（由数百个 page 组成，通常几十到几百 MB）为单位擦除。
- **闪存不能"原地覆盖写"**：一个 page 一旦写过，必须先擦除整个 block 才能重新写入。
- 所以 SSD 内部的固件——**FTL（Flash Translation Layer）**——采用"异地更新"策略：新数据写到一个空闲 page，旧 page 标记为无效，逻辑地址到物理地址的映射更新。([Coding for SSDs, Code Capsule](https://codecapsule.com/2014/02/12/coding-for-ssds-part-3-pages-blocks-and-the-flash-translation-layer/))
- 当空闲 page 不够用时，FTL 触发 **垃圾回收（GC）**：把一个 block 里还有效的 page 搬到新 block，再擦除整个旧 block 腾出空间。这个"为了写 1 份数据，实际在闪存介质上多写了几份"的现象，就是 **写放大（Write Amplification, WA）**。([Write amplification, Wikipedia](https://en.wikipedia.org/wiki/Write_amplification))

随机写模式下，脏数据和有效数据混杂在同一个 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](https://www.thessdreview.com/featured/ssd-throughput-latency-iopsexplained/))在带宽维度上，业界经验值是随机 I/O 可能比顺序慢 50~100 倍（这个更大的数字通常出现在小随机 IO 且队列深度低的场景）。

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

---

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

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

- **二叉树/红黑树**：每个节点只有 2 个子节点，树高是 `O(log₂ N)`。对于一张千万行的表，树高大约是 24 层。**每一层通常对应一次磁盘 I/O**（除非全部缓存在内存），24 次随机 I/O 才能定位一行数据，代价太高。
- **B+Tree**：把"分支因子"从 2 提升到几百甚至上千（等于一个磁盘页能塞下多少个 key+指针）。InnoDB 默认页大小 16 KB，一个整数主键+子节点指针大约 十几字节，一页能放 1000+ 个索引项。([MySQL 官方文档](https://dev.mysql.com/doc/refman/8.4/en/innodb-physical-structure.html))这样三层 B+Tree 就能索引 1000 × 1000 × 1000 = 10 亿行数据——**树高从二叉树的 ~30 层压到 3~4 层**，对应的随机 I/O 次数也从 30 次降到 3~4 次。这是数量级的差距。
- **哈希索引**：等值查询是 `O(1)`，但完全不支持范围查询（`WHERE age > 18`、`ORDER BY`），因为哈希打散了数据的有序性。B+Tree 的叶子节点天然按 key 有序，还用链表串联，范围扫描只需定位到起点后向右遍历，天然支持 `>`、`<`、`BETWEEN`、`ORDER BY`。

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

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

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

**二级索引（secondary index）**是另一棵独立的 B+Tree，它的叶子节点存的不是整行数据，而是**索引列 + 主键值**。([MySQL 官方文档](https://dev.mysql.com/doc/refman/8.4/en/innodb-physical-structure.html))

```sql
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](https://docs.oracle.com/cd/E17952_01/mysql-5.7-en/innodb-physical-structure.html))

页分裂的代价：
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](https://link.springer.com/article/10.1007/s002360050048))其设计目标非常直接：**为写多的场景，把随机写彻底改造成顺序写**，代价是读和空间上的一些牺牲。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 范围可能重叠），再逐层往下查**，直到找到或者查完所有层。

- 定义：读放大 = 回答一次查询实际需要的磁盘读次数。([RocksDB Wiki](https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide))
- LevelDB（RocksDB 前身）在未调优情况下，读放大理论上可以到 **200** 这个量级；写放大最坏情况下可以到 **50**。([相关综述引用](https://gifted-dl.medium.com/deep-dive-on-read-write-and-space-amplification-in-ssds-and-lsm-storage-engines-and-what-makes-4a1e15fc6f0e))
- 生产环境的 RocksDB 通过 **Bloom Filter**（快速判断一个 key 一定不在某个 SSTable 里，避免无谓的磁盘读）和层级归并策略，把实际读放大压到个位数到十几的量级，但仍然天然高于 B+Tree（B+Tree 一次点查通常只需要 3~4 次页 I/O，因为数据只有一份、只在一个位置）。

### 3.3 代价二：空间放大

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

- 定义：空间放大 = 磁盘上实际占用空间 / 数据的逻辑大小。比如写入 10 MB 逻辑数据，实际占了 100 MB 磁盘，空间放大就是 10。([RocksDB CIDR 2017 论文](https://www.cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf))
- Facebook 对 RocksDB 的生产优化实践中，通过调整层级大小比例（size multiplier，常用值是 10）和 compaction 策略，把空间放大控制在 **1.1 倍左右**（即多占约 10% 空间）这个量级。([同上](https://www.cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf))
- 换句话说，空间放大不是 LSM-Tree 不可避免的宿命，而是"写放大 / 读放大 / 空间放大"三者之间可以调节的权衡——压得越狠（空间越省），通常读写代价越高。

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

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

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

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

选型经验：
- **写多、可以容忍多占磁盘、对读延迟不敏感**（日志、事件流、时序写入缓冲）→ 偏向 size-tiered，用磁盘空间换写吞吐。
- **读多、磁盘紧张、要求读延迟稳定**（用户画像、KV 存储的对外服务层）→ 偏向 leveled，用写开销换空间和读的可预测性。

### 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、Oracle | RocksDB、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 系）。但要注意两点区别：
- 如果时序数据**乱序写入**（比如边缘设备网络延迟导致数据晚到），LSM-Tree 处理乱序写依然是顺序 I/O（写到内存里排序即可），而如果用 B+Tree 类结构处理乱序写入的时间戳主键，会导致大量随机插入和页分裂——**这也是时序数据库几乎清一色选 LSM 系存储的关键原因之一**。
- 时序数据通常有明确的 TTL（保留 N 天后过期删除），LSM-Tree 的 compaction 天然适合按时间窗口批量整体丢弃过期 SSTable（不需要真正执行删除操作扫描每一行），这比 B+Tree 里做批量 `DELETE WHERE ts < xxx` 高效得多——后者要逐行删除、可能产生大量随机 I/O 和碎片。

---

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

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

### 6.1 最左前缀原则

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

```sql
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，不需要回表。

```sql
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 回表的代价

```sql
-- 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」的代价，和「直接全表顺序扫描 + 内存里过滤」的代价，哪个更低。

- 当索引的**选择性差**（比如 `status` 字段只有 3 种取值，命中 30% 的数据）时，用索引意味着要为 30% 的行分别做一次回表随机 I/O，这通常比一次性顺序扫描全表还慢——这也是为什么 MySQL 优化器有时会"忽略"你建的索引，直接走全表扫描，这不是 bug，是基于代价的正确选择。
- 当表很小、能整体放进 Buffer Pool（内存）时，"随机 I/O"其实是内存里的随机访问，代价和顺序访问差距很小，索引选择性差带来的劣势被抹平，优化器更可能选索引。
- 当排序/分组需要用到索引的有序性（`ORDER BY` 命中索引列），即使选择性一般，优化器也可能倾向于用索引来避免额外的排序开销（filesort）。

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

```sql
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 讨厌随机写"这条物理定律下，选择把复杂度放在写路径还是读路径：

- **B+Tree** 选择在写入时就维护好全局有序结构（付出页分裂和随机 I/O 的代价），换来读时只需要 3~4 次 I/O 就能精确定位——**为读优化，是 MySQL/PostgreSQL 这类 OLTP 系统的默认选择**。
- **LSM-Tree** 选择把写全部变成顺序追加，把"整理有序"这件事推迟到后台 compaction 慢慢做——**为写优化，代价是读放大和空间放大，是 RocksDB/Cassandra/时序数据库的常见选择**。
- 索引实战的很多"反直觉"现象（最左前缀失效、索引变慢），根源都能回到 B+Tree 的物理结构：有序性只在维护索引的那几列上成立，回表是一次额外的随机 I/O，优化器的每一个选择都是在做代价估算，而不是有索引就必然用索引。

---

## 参考来源

- O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. (1996). *The log-structured merge-tree (LSM-tree)*. Acta Informatica, 33(4), 351–385. https://link.springer.com/article/10.1007/s002360050048
- MySQL 官方文档：[The Physical Structure of an InnoDB Index](https://dev.mysql.com/doc/refman/8.4/en/innodb-physical-structure.html)
- RocksDB Wiki：[RocksDB Tuning Guide](https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide)
- Dong, S. et al. *Optimizing Space Amplification in RocksDB*. CIDR 2017. https://www.cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf
- ScyllaDB Blog：[Size-Tiered Compaction](https://www.scylladb.com/2018/01/17/compaction-series-space-amplification/)、[Leveled Compaction](https://www.scylladb.com/2018/01/31/compaction-series-leveled-compaction/)
- Code Capsule：[Coding for SSDs – Pages, Blocks, and the Flash Translation Layer](https://codecapsule.com/2014/02/12/coding-for-ssds-part-3-pages-blocks-and-the-flash-translation-layer/)
- Wikipedia：[Write amplification](https://en.wikipedia.org/wiki/Write_amplification)
- The SSD Review：[SSD Throughput, Latency and IOPS Explained](https://www.thessdreview.com/featured/ssd-throughput-latency-iopsexplained/)
- PlanetScale Blog：[B-trees and database indexes](https://planetscale.com/blog/btrees-and-database-indexes)