现代数据库存储引擎主要分为两大流派：以 InnoDB、PostgreSQL 为代表的 B+ 树（原地更新，In-place Update），以及以 LevelDB、RocksDB、Cassandra、TiKV 为代表的 LSM-Tree（日志结构合并树，Out-of-place Update）。根据 RUM 猜想（Read, Update, Memory overhead），没有任何一种存储结构能同时在读放大、写放大和空间放大三个指标上同时达到最优。
一、B+ 树的优势与随机写瓶颈
B+ 树按固定大小的数据页（通常为 8KB 或 16KB）组织磁盘数据。高度为 3～4 层的 B+ 树即可容纳数亿条记录，且由于非叶子节点常驻内存 Buffer Pool，一次点查询或范围扫描通常只需 1 次磁盘 I/O。
然而，当面对高吞吐随机主键或二级索引写入时，B+ 树存在显著的 写放大（Write Amplification）：
- 即使只修改一行中 10 字节的字段，刷盘时也必须将整个 16KB 数据页（以及 InnoDB Doublewrite Buffer 的额外 16KB）写入磁盘；
- 随机插入导致叶子节点空间不足时，会触发代价高昂的 页分裂（Page Split），并造成约 30%～50% 的页内空间碎片。
二、LSM-Tree 如何将随机写转化为顺序写
LSM-Tree 的核心思想是完全放弃原地更新，所有写入（包括增、改、删）一律以追加（Append-only）方式进行：
- 写入 WAL 与 MemTable：写请求先顺序追加到磁盘预写日志（WAL），随后插入内存中的跳表（SkipList）或红黑树结构
MemTable，即刻向客户端返回成功。 - Flush 生成 L0 SSTable：当
MemTable达到大小阈值（如 64MB）后冻结为Immutable MemTable，由后台线程顺序刷盘生成不可变的有序文件 SSTable（Sorted String Table）。 - 多层 Compaction（合并压缩）：后台线程不断将高层级（如 L0、L1）的 SSTable 进行多路归并排序，剔除被覆盖的旧版本与墓碑标记（Tombstone），下沉到更大容量的下一层（L2、L3...）。
| 评估维度 | B+ 树存储引擎 (InnoDB/PG) | LSM-Tree 存储引擎 (RocksDB) |
|---|---|---|
| 点查询延迟 | 极低且稳定（最多 1 次页读取） | 需依次查询 MemTable、L0 及各层 SSTable，依赖 Bloom Filter |
| 范围扫描性能 | 优秀（叶子节点双向链表顺序遍历） | 需构造多路归并迭代器（Merge Iterator）合并多层结果 |
| 随机写入吞吐 | 受限于随机落盘与页分裂 | 极高（全部转化为 WAL 与 SSTable 顺序写） |
| 写放大来源 | 全页刷盘 + Doublewrite + 页分裂 | 后台多层 Leveled Compaction 重复读写同一批 KV |
| 空间利用率 | 页内碎片较多（填充率约 67%） | 块压缩率高，但 Compaction 期间存在临时历史版本冗余 |
三、RocksDB 点查询优化：Bloom Filter 与 Prefix Seek
在 Leveled Compaction 架构下，如果不加优化，一次查询一个不存在的 Key 可能需要逐层二分查找数十个 SSTable 文件。为此，RocksDB 在每个 SSTable 的 Filter Block 中嵌入了 布隆过滤器（Bloom Filter）：
cpp
// RocksDB 表级配置：启用 10 bits/key 的布隆过滤器与块缓存
rocksdb::BlockBasedTableOptions table_options;
table_options.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10, false));
table_options.block_cache = rocksdb::NewLRUCache(2ULL * 1024 * 1024 * 1024); // 2GB Block Cache
table_options.cache_index_and_filter_blocks = true;
table_options.pin_l0_filter_and_index_blocks_in_cache = true;当分配 10 bits/key 时，布隆过滤器的假阳性率（False Positive Rate）可降至约 1%，即 99% 不存在于该 SSTable 中的点查询可以在内存中直接短路返回，从而将 LSM-Tree 的点查延迟逼近 B+ 树。