深入理解B+树与LSM树：数据库索引引擎的核心数据结构

在现代数据库系统中，索引数据结构的选择直接决定了系统的读写性能、存储效率和并发能力。B+ 树和 LSM 树是两种最核心的索引结构，分别代表了"读优化"和"写优化"的设计哲学。本文将从底层原理出发，深入剖析这两种数据结构的设计思想、性能特征及实际工程应用。

一、B+ 树：经典的多路平衡搜索树

B+ 树（B-plus tree）是自平衡的多路搜索树，是 B 树的变种。它是关系型数据库中最常见的索引结构，MySQL InnoDB、PostgreSQL 等都采用 B+ 树作为默认索引实现。

1.1 核心结构

B+ 树的关键特性是：所有数据记录都存储在叶子节点上，非叶子节点仅存储键（key）作为索引指引。叶子节点之间通过双向链表串联，形成有序序列。

// B+ 树节点基本结构（伪代码）
struct BPlusTreeNode {
    bool is_leaf;                    // 是否为叶子节点
    int key_count;                   // 当前键数量
    KeyType keys[M-1];               // 键数组（M 为阶数）
    union {
        NodePointer children[M];     // 内部节点：子节点指针
        RecordPointer records[M-1]; // 叶子节点：数据记录指针
        struct {
            NodePointer next;        // 叶子节点：后继指针
            NodePointer prev;        // 叶子节点：前驱指针
        };
    };
};

假设一棵阶数为 M 的 B+ 树，其约束条件如下：每个内部节点最多有 M 个子节点；除根节点外，每个内部节点至少有个 M/2 个子节点；所有叶子节点位于同一层。当 M=200 时，一棵 3 层 B+ 树即可索引约 800 万条记录（200×200×200），这解释了为什么数据库索引通常只需 3-4 次 I/O 就能定位到数据。

1.2 查找过程

B+ 树的查找从根节点开始，在每个节点内进行二分查找，确定下一步的子节点分支，直到抵达叶子节点。对于点查询（point query），时间复杂度为 O(logN)；对于范围查询，先定位到起始叶子节点，然后沿链表顺序扫描即可。

// B+ 点查询伪代码
function search(Node node, Key target):
    if node.is_leaf:
        // 在叶子节点中二分查找
        index = binary_search(node.keys, target)
        if index >= 0:
            return node.records[index]
        return null
    else:
        // 在内部节点中找到合适的子节点
        i = upper_bound(node.keys, target)
        return search(node.children[i], target)

1.3 插入与分裂

插入时先找到目标叶子节点，将键值对写入后将节点按键排序。若叶子节点已满（key_count 达到 M-1），则进行分裂：取中间键提升至父节点，左右两部分分别成为新的叶子节点。如果父节点也因此满裂，分裂可能向上传播到根节点，导致树高增加——这是 B+ 树唯一的高度增长方式。

1.4 删除与合并

删除操作类似，从叶子节点移除记录后，若节点键数低于阈值，则尝试从兄弟节点"借"一个键（rotation），若兄弟也不足则与兄弟节点合并（merge）。合并可能导致父节点键减少，进而向上传播。

1.5 B+ 树的读优化特性

B+ 树的优势在于点查询和范围查询都可以快速完成。由于所有数据在叶子节点上有序串联，范围查询只需要一次定位加顺序扫描。此外，B+ 树的扇出（fanout）很高，树矮层少，缓存友好。但代价在于写入时的页分裂：随机插入可能导致频繁的分裂操作，产生大量随机 I/O。

二、LSM 树：写优化的日志结构合并树

LSM 树（Log-Structured Merge-Tree）由 O'Neil 等人于 1996 年提出。它的核心思想是"将随机写转换为顺序写"，通过追加日志和后台合并来优化写吞吐量。Google LevelDB、RocksDB、Apache Cassandra、HBase 等都采用 LSM 树结构。

2.1 核心架构

LSM 树由多层（level）结构组成，从上到下容量逐级增大。写入首先进入内存中的 MemTable（通常为跳表或平衡二叉树），当 MemTable 达到阈值时转为不可变的 Immutable MemTable，然后刷盘（flush）成为 Level 0 的一个 SSTable 文件。

// LSM 树写入流程
1. 写入 WAL (Write-Ahead Log)
2. 写入 MemTable (内存有序结构，如跳表)
3. MemTable 满 - 转为 Immutable MemTable
4. Flush 到磁盘 - Level 0 SSTable (sorted file)
5. 后台 Compaction：Level 0 - Level 1 - Level 2 ...

SSTable（Sorted String Table）是按键排序的不可变文件。Level 0 的 SSTable 之间可能存在键范围重叠（因为每次 flush 是独立进行的），而从 Level 1 开始，每个 Level 内的 SSTable 按键范围严格互不重叠。

2.2 Compaction 策略

Compaction 是 LSM 树后台最核心的操作，主要有两种策略：

Size-Tiered Compaction（大小分层）：当某一层的 SSTable 数量达到阈值时，将该层多个 SSTable 与下一层重叠的 SSTable 合并排序，生成更大的新 SSTable 写入下一层。这种策略写放大较小，但读放大和空间放大较大。

Leveled Compaction（分层合并）：每一层的总大小约为上一层的 T 倍（通常 T=10）。每一层内的 SSTable 大小相同且键范围不重叠。Compaction 时将该层的一个 SSTable 与下一层中重叠的 SSTable（通常约 10 个）合并。这种策略读性能更优、空间放大更小，但写放大更大。RocksDB 默认采用此策略。

// Leveled Compaction 参数示例
Level 0: 4 个文件 (每个 64KB, 共 256KB)
Level 1: 10MB     (10 个 1MB SSTable)
Level 2: 100MB    (10 个 10MB SSTable)
Level 3: 1GB      (10 个 100MB SSTable)
Level 4: 10GB     (10 个 1GB SSTable)
Level 5: 100GB    (10 个 10GB SSTable)
Level 6: 1TB      (10 个 100GB SSTable)

2.3 读取路径

LSM 树的读取路径比 B+ 树复杂，因为数据可能分布在 MemTable、Immutable MemTable、Level 0 SSTables 和 Level 1+ SSTables 中的任意一层。读取按以下顺序逐层查找：

// LSM 树查找流程
1. MemTable（最新数据）
2. Immutable MemTable
3. Level 0 SSTables (按时间从新到旧，因为可能有重复键)
4. Level 1 ~ Level 6 SSTables (每层二分查找定位 SSTable)

由于 LSM 树可能存在多层查找，点查询的性能不如 B+ 树。为了加速读取，LSM 树通常使用布隆过滤器（Bloom Filter）来快速判断某个 key 是否存在于某个 SSTable 中，从而避免无用的磁盘 I/O。

2.4 删除与更新

LSM 树中，删除和更新都是通过插入新记录实现的。删除操作会写入一条特殊标记（tombstone/DELETE marker），表示该键已被删除。在后续的 compaction 过程中，过期的记录和 tombstone 会被清理掉。更新操作则直接写入新版本的记录，compaction 时只保留最新版本。

三、B+ 树 vs LSM 树深度对比

3.1 读写性能权衡

两种数据结构最核心的差异在于读写性能的权衡：

写入性能：LSM 树远优于 B+ 树。LSM 树的所有写入都是顺序追加到 WAL 和 MemTable，几乎没有随机 I/O。B+ 树的随机写入可能导致页分裂，产生大量随机写操作。在 SSD 上，LSM 树的写入吞吐量通常比 B+ 树高 5-10 倍。

点查询性能：B+ 树优于 LSM 树。B+ 树只需一次 O(logN) 的树搜索即可定位数据。LSM 树可能需要检查多层 SSTable（尽管布隆过滤器能排除大部分无效查找），最坏情况下可能涉及多次随机 I/O。

范围查询性能：B+ 树在范围查询上有天然优势（叶子节点链表）。LSM 树的范围查询需要在所有层级中查找并合并结果（通过 Merge Iterator 实现），但由于每个 SSTable 内部有序，实际表现也可以接受。

3.2 写放大与读放大

度量指标	B+ 树	LSM 树 (Leveled)	LSM 树 (Size-Tiered)
写放大	低（1-2x 页分裂时略增）	高（10-30x）	低（2-5x）
读放大	低（O(logN) 次 I/O）	高（需查多层 SSTable）	中（每层查 1 个文件）
空间放大	低（页利用率约 69%）	高（最坏 50-90% 旧数据）	中（约 10-30%）
点查延迟	低（1-3 次 I/O）	中（布隆过滤后 1-3 次）	较低
写入吞吐	中	高	很高

写放大（Write Amplification）是 LSM 树最大的"隐形成本"。在 Leveled Compaction 下，一条记录可能在多个 Level 中被重复写入多次。这对于 SSD 的磨损和磁盘带宽消耗都有显著影响。

四、工程实践中的混合架构

4.1 RocksDB 的优化技巧

RocksDB（Facebook 基于 LevelDB 的优化版本）提供了丰富的调优参数：

// RocksDB 关键配置示例
options.write_buffer_size = 64MB        // MemTable 大小
options.max_write_buffer_number = 3     // 最多 MemTable 数量
options.level0_file_num_compaction_trigger = 4   // L0 触发 compaction 的文件数
options.target_file_size_base = 64MB    // L1 的基础文件大小
options.target_file_size_multiplier = 1 // 每层文件大小的倍增因子
options.max_bytes_for_level_base = 256MB         // L1 总大小
options.max_bytes_for_level_multiplier = 10      // 每层大小倍增因子
options.compression = kLZ4Compression  // 每层压缩算法
options.bottommost_compression = kZSTD // 最底层使用更强压缩
options.bloom_filter_bits_per_key = 10 // 布隆过滤器精度

4.2 B+ 树的优化方向：WiredTiger 的启示

MongoDB 的 WiredTiger 引擎对传统 B+ 树进行了多项优化：Copy-on-Write（避免页分裂的开销）、Checkpoint 机制（替代传统 WAL）、前缀压缩（减少存储占用）、定期执行 compact 回收碎片空间。这些优化使 B+ 树在高并发写入场景下依然有不错的表现。

4.3 混合索引：Learned Index Structures

近年来，学习型索引（Learned Index）成为一个新兴方向。其核心思想是用神经网络模型来"学习"键的分布，预测记录的位置，用模型替代 B+ 树的节点搜索。Google 的 RMI（Recursive Model Index）在特定场景下实现了比 B+ 树快 3 倍、体积小 100 倍的效果。但目前学习型索引还不支持高效更新，工程应用有限。

五、如何选择：场景驱动的决策框架

选择索引结构时，需要综合考虑以下因素：

选择 B+ 树的场景：读多写少的 OLTP 工作负载（如 MySQL 订单系统）、需要强事务一致性（B+ 树天然支持 MVCC 和行锁）、要求低延迟的点查询、范围查询为主的应用。

选择 LSM 树的场景：写入密集型的时序数据（如 IoT 传感器、监控数据）、日志系统、消息系统、需要极高写入吞吐的应用、SSD 上的大数据库存储（利用顺序写性能）。

// 简洁的决策框架
写多读少 + 高吞吐     - LSM 树 (RocksDB/HBase)
读多写少 + 低延迟     - B+ 树 (InnoDB/PostgreSQL)
时序/日志/流式数据    - LSM 树
强事务 + 复杂查询     - B+ 树
混合负载             - 根据读写比选择或混合架构

六、总结与展望

B+ 树和 LSM 树分别代表了数据库索引两种截然不同的设计哲学。B+ 树以"读优先"为原则，通过高度平衡的多路搜索树实现 O(logN) 的点查和高效的范围扫描。LSM 树以"写优先"为宗旨，通过顺序写和后台合并将随机 I/O 降到最低，用读性能的退换来换取写吞吐的飞跃。

在实际工程中，没有银弹。现代数据库引擎往往在两种结构的基础上做了大量折中优化。例如：TiDB 的 TiKV 使用 RocksDB（LSM），而其 SQL 层保留了 B+ 树式的索引视图；NewSQL 数据库 CockroachDB 采用 Pebble（LSM 变种）作为底层存储引擎，上层实现分布式 SQL。

未来，随着存储硬件的发展（如 NVMe SSD、持久内存/PMEM、CXL 内存），索引结构也可能会持续演进。但理解 B+ 树和 LSM 树的核心原理，仍然是深入数据库系统设计不可或缺的基石。