B树与LSM树：现代数据库存储引擎的核心数据结构

引言：磁盘I/O是一切设计的原点

现代数据库存储引擎的设计，本质上是围绕一个核心矛盾展开的：内存的随机访问速度是纳秒级，而磁盘的随机访问速度是毫秒级，两者相差五个数量级。如何最小化磁盘I/O次数、最大化顺序I/O比例，决定了存储引擎的性能天花板。

在漫长的工程实践中，两种数据结构最终胜出，成为事实标准：B+树（读优化的代表）与LSM树（写优化的代表）。MySQL InnoDB用B+树构建聚簇索引，RocksDB/LevelDB用LSM树支撑高吞吐写入。理解这两种结构，就理解了现代数据库的运转逻辑。

一、B+树：磁盘友好的多路平衡搜索树

1.1 为什么选B+树而不是二叉树

假设一个10亿条记录的索引，二叉搜索树（BST）的高度最坏情况下可达O(N)，平衡二叉树（如AVL、红黑树）的树高为log₂(10⁹)≈30。这意味着一次点查需要30次磁盘I/O，每次I/O约10ms，单次查询需要300ms——完全不可接受。

B+树的核心思想是增加扇出（fan-out）来降低树高。假设一个B+树节点对应一个4KB的磁盘页，每个键值对16字节（8字节key + 8字节指针），单个节点可存放约250个键。此时：

• 1层B+树：250条记录
• 2层B+树：250² = 62,500条
• 3层B+树：250³ ≈ 1560万条
• 4层B+树：250⁴ ≈ 39亿条

结论：4层B+树即可索引近40亿条记录，仅需4次磁盘I/O，通常在1-3次之内即可完成。

1.2 B+树的核心结构特征

B+树与B树的关键区别在于：

• 数据仅存于叶子节点：内部节点只存键（key）和子节点指针，不存数据。这意味着内部节点可以容纳更多扇出，进一步降低树高。
• 叶子节点通过链表串联：所有叶子节点按顺序用双向链表连接，使得范围查询（range scan）可以高效地顺序遍历，而无需反复从根节点向下查找。
• 节点填充因子可控：B+树通常保持节点至少半满（填充因子50%-100%），在空间利用率和分裂频率之间取得平衡。

1.3 B+树的工程实现要点

在实际数据库中（以InnoDB为例）：

• 聚簇索引：InnoDB的主键索引直接将数据行存储在B+树的叶子节点中，主键查找一次B+树遍历即可拿到完整行数据。
• 辅助索引：非主键索引的叶子节点存储主键值，查询时需要回表（bookmark lookup）到主键索引获取完整数据。
• Buffer Pool：InnoDB通过内存缓冲池缓存热点B+树节点，根节点和高层节点通常常驻内存，大幅降低实际磁盘I/O次数。
• Change Buffer：对非唯一辅助索引的写操作，延迟合并到磁盘页，将多次随机I/O合并为一次。

1.4 B+树的写入代价

B+树在写入时面临的根本问题是随机写。插入一条记录可能导致以下情况：

• 叶节点未满：直接写入，一次磁盘I/O。
• 叶节点已满：节点分裂为两个半满节点，需要写入两个叶节点并递归更新父节点至根，涉及3-5次磁盘I/O。
• 页分裂导致碎片化：频繁插入导致页面不再连续，顺序扫描性能退化。

在写密集场景下（如日志系统、时序数据库），B+树随机写入的代价过高。这正是LSM树出现的原因。

二、LSM树：用写放大换取写吞吐

2.1 核心架构组件

LSM树（Log-Structured Merge Tree）将随机写转换为顺序写，核心组件包括：

• WAL（Write-Ahead Log）：所有写入首先追加到磁盘上的WAL日志（顺序写），然后写入内存中的MemTable。WAL保证即使进程崩溃，已提交的数据也可从日志恢复。
• MemTable：内存中的有序数据结构，通常用跳表（Skip List）或B+树实现。写入MemTable即完成客户端返回的"写入成功"。
• Immutable MemTable：MemTable写满后转为不可变状态，等待刷盘。此时新写入进入一个新的MemTable。
• SSTable（Sorted String Table）：MemTable刷盘后生成的磁盘文件，按键排序，不可变（immutable）。每个SSTable包含数据块（Data Block）和索引块（Index Block）。

2.2 多级Compaction机制

随着写入进行，SSTable文件越来越多。Compaction负责合并、去重、清理过期数据。经典策略有两种：

Size-Tiered Compaction（大小分层）：

• 大小的相近的SSTable合并为更大的文件。
• 优点：写放大小（相同数据被合并的次数少）。
• 缺点：读放大和空间放大严重（多个小文件中可能有重复key，需要逐个检查）。
• 代表系统：Cassandra（STCS模式）、HBase。

Leveled Compaction（分层合并）：

• L0允许文件重叠，但L1及以下每层内文件互不重叠，按key范围分区。
• 当Li层大小超过阈值，选取一个文件与Li+1层重叠的文件合并。
• 优点：读性能优秀（每层文件少，通常只需检查1-2个文件），空间放大可控。
• 缺点：写放大较大（重写数据更多）。
• 代表系统：LevelDB、RocksDB（默认LCS）、ScyllaDB。

2.3 读路径与优化

LSM树的读取路径比B+树更复杂，需要从最新的MemTable逐级查到最老的SSTable：

1. MemTable（内存中，最快）
2. Immutable MemTable（内存中）
3. L0 SSTables（允许key重叠，需逐个检查）
4. L1 SSTables（文件不重叠，每层最多查一个文件）
5. L2...Ln（逐层向下）

为了加速"key不存在"的查询，引入布隆过滤器（Bloom Filter）：每个SSTable附带一个Bloom Filter，如果Bloom Filter判断key不存在，则直接跳过该文件。对于点查场景，Bloom Filter将平均读I/O次数降至接近1次。

2.4 三种放大的理解

LSM树的设计围绕三种放大之间的权衡：

• 读放大（Read Amplification）：一次查询需要检查多少个SSTable。Leveling vs Tiering的关键差异。
• 写放大（Write Amplification）：写入一条数据，最终产生多少字节的磁盘写入（包含WAL、Compaction重写）。典型值在10-30倍之间。
• 空间放大（Space Amplification）：实际数据与磁盘占用之比。未合并的过期/删除数据占据额外空间，通常限制在1.1-1.5倍。

三者不可兼得，需在具体场景中取舍。Leveling优化读，Tiering优化写。RocksDB通过调节Compaction策略和层数参数来适配不同负载。

三、选型实践：何时用B+树，何时用LSM

典型案例：

• MySQL InnoDB：B+树聚簇索引，适合读多写少、需要强一致事务的OLTP场景。
• RocksDB：LSM树，作为Spanner、TiKV、Flink State Backend等系统的底层存储引擎，适用于写密集、大状态场景。
• Amazon DynamoDB：基于LSM树（存储引擎），支撑日均万亿级写入。
• Google Bigtable：经典LSM树实现，合并了合并和分割操作。

四、发展趋势与前沿研究

• Hybrid方案：如WiscKey（将value分离出SSTable，减少写放大）、TreeLine（将B+树索引与LSM存储分离）。
• FPGA/GPU加速Compaction：Compaction的计算密集型特性适合硬件加速。
• ZNS SSD友好型LSM：Zoned Namespace SSD要求分区顺序写，与LSM树天然契合，减少GC开销。
• Trie+B+树融合：如SlimDB用前缀压缩进一步减少B+树节点大小。