存储引擎核心数据结构：B-Tree家族与LSM-Tree的设计权衡

数据结构存储引擎B-TreeLSM-Tree

引言：存储引擎的核心矛盾

存储引擎的设计本质上是一道关于读写权衡的系统工程题。

任何持久化存储系统都必须回答两个基本问题：数据如何写入磁盘？数据如何从磁盘读出？这两个问题看似简单，但在工程层面存在深刻的矛盾——优化写性能的数据结构往往牺牲读性能，反之亦然。

传统关系型数据库（MySQL InnoDB、PostgreSQL）选择了 B-Tree 家族作为索引结构，将数据组织为有序的树形结构，天然支持高效的点查和范围查询。代价是：每次写入都需要找到数据在树中的精确位置，执行就地更新（in-place update），这意味着随机磁盘 I/O。

而以 Google BigTable 为代表的分布式存储系统则走向了另一个极端：LSM-Tree（Log-Structured Merge-Tree）将所有写入先缓存在内存中，攒满后批量顺序刷盘。写入性能极高，但读取时可能需要合并多个层级的数据，读放大成为必须面对的问题。

理解这两类数据结构的原理与权衡，是理解现代存储引擎设计的基石。

B-Tree 家族：面向读优化的索引结构

B-Tree（多路平衡搜索树）

B-Tree 最初由 Rudolf Bayer 和 Edward McCreight 于 1972 年在 Boeing Research Labs 提出，目标是解决磁盘存储环境下的高效检索问题。

核心定义： 一棵 m 阶 B-Tree 满足以下性质：

  • 每个节点最多包含 m 个子节点（m-1 个关键字）
  • 除根节点外，每个节点至少包含 ⌈m/2⌉ 个子节点
  • 根节点至少有 2 个子节点（除非它同时是叶子节点）
  • 所有叶子节点位于同一层
  • 每个节点内的关键字按升序排列

搜索过程等价于多路折半查找： 从根节点开始，在节点内部通过二分查找定位关键字或确定子树方向，逐层下降直至找到目标或到达叶子节点。由于每个节点可以容纳多个关键字，树的高度被大幅压缩。对于包含 N 个关键字的 m 阶 B-Tree，树高为 O(log_m N)，每一层对应一次磁盘 I/O，因此查找的 I/O 次数与树高成正比。

节点分裂与合并： 当插入导致节点溢出（关键字数超过 m-1）时，节点从中间位置分裂为两个节点，中间关键字上提至父节点。删除时如果节点关键字数低于下限，则需要从兄弟节点借用关键字或与兄弟节点合并。这两种操作保证了树的平衡性。

                    [30 | 70]
                   /    |    \
          [10|20]    [40|50|60]    [80|90]

B-Tree 与二叉搜索树的本质区别： 二叉搜索树（BST）每个节点只存一个关键字，树高为 O(log_2 N)。当 N = 100 万时，BST 树高约 20，而 1000 阶 B-Tree 树高仅为 2。在磁盘 I/O 代价远高于内存计算的存储场景下，这个差距决定了 B-Tree 的绝对优势。

B+Tree：面向磁盘 I/O 优化的索引结构

B+Tree 是 B-Tree 最重要的变体，也是现代关系型数据库索引的事实标准。它在 B-Tree 基础上做了两个关键改进：

改进一：数据只存储在叶子节点。 B-Tree 中，关键字及其关联的数据记录分布在整棵树的所有节点中。B+Tree 则将所有数据下沉至叶子节点，非叶子节点仅存储关键字的副本，作为索引的"路标"。

这意味着：

  • 非叶子节点更小，同样大小的磁盘页可以容纳更多关键字，扇出（fan-out）更大，树更矮
  • 查询路径固定：无论查找什么数据，都必须走到叶子节点，查询性能更稳定
  • 非叶子节点形成稀疏索引（sparse index），叶子节点形成稠密索引（dense index）

改进二：叶子节点之间通过双向链表连接。 这使得范围查询可以在叶子层顺序遍历，而不需要回溯到父节点。

         内部节点（仅存索引）
              [30 | 70]
             /    |    \
     叶子层（存数据，链表相连）
    [10,20] ↔ [30,40,50,60] ↔ [70,80,90]

为什么 B+Tree 更适合数据库索引？

特性 B-Tree B+Tree
数据存储位置 所有节点 仅叶子节点
非叶子节点大小 较大（含数据指针） 较小（仅含关键字）
扇出（fan-out） 较低 较高
同等数据量的树高 较高 较低
范围查询 需要中序遍历整棵树 叶子链表顺序扫描
查询性能稳定性 不稳定（数据可能在任意层） 稳定（总是到达叶子层）

工程实现细节——以 InnoDB 为例：

MySQL InnoDB 的 B+Tree 实现有几个值得关注的工程决策：

  1. 页大小固定为 16KB。 每个 B+Tree 节点对应一个页。假设主键为 8 字节的 bigint，指针为 6 字节，则每个内部节点可容纳约 16KB / 14B ≈ 1170 个关键字。两层内部节点可索引 1170 × 1170 ≈ 137 万条记录，三层内部节点可索引约 16 亿条记录。这意味着绝大多数表的主键查找只需 2-3 次磁盘 I/O。

  2. 聚簇索引（Clustered Index）。 InnoDB 的主键索引是聚簇索引，叶子节点直接存储完整的行数据。二级索引的叶子节点存储的是主键值，通过主键值回表到聚簇索引获取完整数据。

  3. 页分裂与页合并。 当页满时，InnoDB 不是简单地从中间分裂，而是考虑插入模式。对于自增主键的顺序插入，InnoDB 会将新记录插入到新页中，避免不必要的数据搬移。

PostgreSQL 的 B+Tree 实现也有其独特之处。PostgreSQL 不使用聚簇索引，所有索引都是二级索引，叶子节点存储的是指向堆表（heap table）中行的物理指针（ctid）。这使得 PostgreSQL 的索引扫描天然需要一次额外的堆表访问，但避免了二级索引回表的间接寻址开销。

B*Tree：空间利用率的进一步优化

B*Tree 是 B+Tree 的进一步变体，核心改进在于提高节点空间利用率：

关键设计差异：

  • 非根非叶节点增加兄弟指针。 兄弟节点之间可以直接通信，无需通过父节点中转。
  • 最低空间利用率从 1/2 提高到 2/3。 B+Tree 要求每个节点至少半满，B*Tree 将这个下限提高到三分之二。
  • 分裂策略优化。 当一个节点满时，B*Tree 不是立即分裂，而是先尝试将部分关键字转移到未满的兄弟节点。只有当两个相邻的兄弟节点都满时，才将两个节点分裂为三个节点（2→3 分裂），而非 B+Tree 的 1→2 分裂。
B+Tree 分裂：1 个满节点 → 2 个半满节点（利用率 50%）
B*Tree 分裂：2 个满节点 → 3 个 2/3 满节点（利用率 67%）

BTree 的优势在于减少分裂次数、提高空间利用率，从而降低树高和磁盘 I/O 次数。但其实现复杂度更高，兄弟指针的维护在并发场景下需要额外的锁协议。因此，工程实践中 B+Tree 仍是主流选择，BTree 更多见于学术讨论和少数文件系统实现中。

LSM-Tree：面向写优化的存储结构

设计动机：写密集场景的性能瓶颈

B-Tree 家族的索引结构在写入时存在一个根本性的性能瓶颈：就地更新（in-place update）导致随机 I/O。

分析一次 B+Tree 的写入操作所需的 I/O：

  1. 读取目标页： 从根节点逐层查找，定位到数据所在的叶子页，将该页从磁盘加载到内存（至少 1 次随机读 I/O）
  2. 修改并回写： 在内存中修改页内容，将修改后的页刷回磁盘（至少 1 次随机写 I/O）
  3. WAL 写入： 为保证持久性，还需要先写预写日志（Write-Ahead Log），这是 1 次顺序写 I/O

对于写密集型场景（日志采集、时序数据、消息队列），每秒可能有数万甚至数十万次写入。每次写入都要执行随机磁盘 I/O，即使使用 SSD，随机写的吞吐量也远低于顺序写（SSD 随机写约 10K-50K IOPS，顺序写可达 500MB/s 以上）。

LSM-Tree（Log-Structured Merge-Tree）正是为解决这一问题而提出的。Patrick O'Neil 等人在 1996 年的论文中首次系统描述了这一数据结构，其核心思想可以概括为一句话：将随机写转化为顺序写。

核心架构：MemTable、Immutable MemTable 与 SSTable

LSM-Tree 的写入路径遵循一个分层的架构设计：

第一层：MemTable（内存写缓冲）

所有写入操作首先进入内存中的 MemTable。MemTable 通常实现为跳表（Skip List）或红黑树，保持数据的有序性。写入 MemTable 是纯内存操作，没有磁盘 I/O 开销。

为保证持久性，写入 MemTable 的同时会将操作追加写入 WAL（Write-Ahead Log）。WAL 是顺序写入的日志文件，写入代价极低。即使进程崩溃，也可以通过重放 WAL 恢复 MemTable 中未持久化的数据。

第二层：Immutable MemTable（不可变内存缓冲）

当 MemTable 的大小达到阈值（通常为 64MB），它被转化为 Immutable MemTable——冻结为只读状态，不再接受新的写入。同时创建一个新的 MemTable 继续接收写入请求。

Immutable MemTable 等待后台线程将其刷写（flush）到磁盘，生成 SSTable 文件。这个设计将前台写入与后台刷盘解耦，避免刷盘阻塞写入。

第三层：SSTable（Sorted String Table）

SSTable 是 LSM-Tree 在磁盘上的持久化格式。每个 SSTable 文件内部的数据按 key 排序，且一旦写入就不可修改（immutable）。SSTable 通常包含以下结构：

┌─────────────────────────────┐
│         Data Blocks         │  ← 按 key 排序的 KV 对，分块存储
├─────────────────────────────┤
│        Index Block          │  ← 每个 Data Block 的起始 key 及偏移量
├─────────────────────────────┤
│     Bloom Filter Block      │  ← 快速判断某个 key 是否可能存在
├─────────────────────────────┤
│         Meta Block          │  ← 统计信息、压缩类型等元数据
├─────────────────────────────┤
│          Footer             │  ← 指向 Index Block 和 Meta Block 的指针
└─────────────────────────────┘

SSTable 的不可变性是 LSM-Tree 架构的关键设计决策。它带来了几个重要优势：写入只需要顺序追加、不需要就地更新锁、天然支持并发读取、易于压缩和缓存。

完整写入路径：

客户端写入 → WAL（顺序追加） → MemTable（内存有序结构）
                                      ↓ 达到阈值
                               Immutable MemTable
                                      ↓ 后台刷盘
                                Level 0 SSTable
                                      ↓ Compaction
                                Level 1 SSTable
                                      ↓ Compaction
                                Level 2 SSTable
                                      ...

Compaction 策略：Size-Tiered 与 Leveled

随着 SSTable 文件不断生成，磁盘上会积累大量文件。多个 SSTable 中可能存在同一个 key 的不同版本（新写入、更新、删除标记）。Compaction 的职责是合并这些文件，清理过期数据，控制文件数量和层级结构。

Size-Tiered Compaction（STCS）

STCS 的策略是：当同一层级积累了一定数量的大小相近的 SSTable 后，将它们合并为一个更大的 SSTable，推入下一层。

Level 0:  [SST-1][SST-2][SST-3][SST-4]  ← 4个文件触发合并
                    ↓
Level 1:       [   SST-merged   ]         ← 合并为1个更大文件
  • 优势： 写放大较低（每次 Compaction 只合并同层文件），写吞吐量高
  • 劣势： 空间放大严重（合并期间新旧文件同时存在，最坏情况下需要两倍磁盘空间），读放大较高（同一层的多个 SSTable 的 key 范围可能重叠，读取时需要检查多个文件）
  • 典型应用： Apache Cassandra（默认策略）、HBase

Leveled Compaction（LCS）

LCS 的核心约束是：除 Level 0 外，每一层内的 SSTable 之间 key 范围不重叠。 这意味着对于任意一个 key，在每一层最多只存在于一个 SSTable 中。

Compaction 过程：从 Level N 选取一个 SSTable，找到 Level N+1 中与其 key 范围重叠的所有 SSTable，将它们合并排序后重新写入 Level N+1。

Level 0:  [a-z][a-m][d-r]        ← key 范围可重叠
Level 1:  [a-f][g-m][n-s][t-z]   ← key 范围不重叠
Level 2:  [a-c][d-f][g-i]...[x-z] ← key 范围不重叠，文件更多

每一层的总大小是上一层的固定倍数（通常为 10 倍）。Level 1 为 10MB，Level 2 为 100MB，Level 3 为 1GB，以此类推。

  • 优势： 空间放大可控（旧数据及时清理），读放大低（每层最多查一个文件）
  • 劣势： 写放大较高（一个 Level N 的文件可能与 Level N+1 的多个文件重叠，合并代价大）
  • 典型应用： LevelDB、RocksDB（默认策略）

读放大、写放大与空间放大

LSM-Tree 的三种放大效应是评估其工程表现的核心指标：

写放大（Write Amplification）： 数据的实际磁盘写入量与用户写入量的比值。一条数据从 MemTable 刷到 Level 0，再经过多次 Compaction 逐层下沉，每次 Compaction 都会被重新写入磁盘。Leveled Compaction 的写放大在最坏情况下可达 10-30 倍（每层大小比为 10 时，单层写放大约为 10 倍）。

读放大（Read Amplification）： 一次逻辑读操作需要读取的磁盘次数。在最坏情况下，一个 key 可能不存在于任何 SSTable 中，查询需要逐层检查。Bloom Filter 可以大幅缓解这个问题——当 Bloom Filter 判定 key 不存在时，可以直接跳过该 SSTable，将无效 I/O 降至接近零。

空间放大（Space Amplification）： 磁盘上实际占用空间与有效数据量的比值。由于同一 key 可能在多层存在旧版本，以及 Compaction 期间的临时空间占用，LSM-Tree 的空间放大通常大于 1。STCS 的空间放大可达 2 倍以上，LCS 通常控制在 1.1-1.2 倍。

三种放大之间存在此消彼长的关系，这被称为 RUM 猜想（Read, Update, Memory）：不可能同时优化读、写和空间三个维度，任何设计都是在三者之间做取舍。

B-Tree 与 LSM-Tree 的设计权衡

读性能对比

B+Tree 的读性能更优且更稳定。 一次点查的 I/O 次数等于树高（通常 2-4 次），且与数据量呈对数关系。内部节点通常常驻缓存（Buffer Pool），实际 I/O 往往只有 1 次。范围查询沿叶子链表顺序扫描，充分利用磁盘顺序读的性能优势。

LSM-Tree 的读性能取决于层数和 Compaction 状态。 最坏情况下，一次读取需要检查 MemTable + 每一层的 SSTable。Bloom Filter 和 Block Cache 是必不可少的优化手段。在实践中，热数据通常集中在 Level 0 和 Level 1（较新的数据层），命中率较高；冷数据的读取延迟则显著增加。

场景 B+Tree LSM-Tree
点查（热数据） 1-2 次 I/O 1-2 次 I/O（MemTable/L0 命中）
点查（冷数据） 2-4 次 I/O 可能 5-10+ 次 I/O
范围查询 叶子链表顺序扫描，极优 需要归并多层数据，开销较大
点查延迟稳定性 极稳定（P99 与 P50 接近） 波动较大（Compaction 期间更明显）

写性能对比

LSM-Tree 的写入吞吐量显著优于 B+Tree。 写入操作只涉及内存操作和 WAL 顺序追加，没有随机 I/O。在 SSD 上，LSM-Tree 的写入吞吐量可以比 B+Tree 高 5-10 倍。

B+Tree 的写入是随机 I/O 密集型操作。 每次写入需要定位目标页、可能触发页分裂，以及刷脏页。Buffer Pool 可以在一定程度上缓解这个问题——脏页在内存中合并后批量刷盘，但当 Buffer Pool 容量不足以覆盖工作集时，随机 I/O 问题依然突出。

需要注意的一点是 LSM-Tree 的写放大问题。虽然前台写入极快，但后台 Compaction 会产生大量的磁盘写入。在 SSD 上，写放大不仅影响性能，还直接影响 SSD 的使用寿命（SSD 有写入次数限制）。这是工程实践中必须权衡的因素。

空间效率

B+Tree 的空间利用率受页填充率影响，通常在 60%-70% 左右（考虑页分裂后的半满页和预留空间）。InnoDB 的默认页填充因子为 15/16（约 93%），但随着随机插入和删除，实际利用率会下降。

LSM-Tree 在 Leveled Compaction 下空间效率较高（约 1.1 倍），因为 Compaction 过程会持续清理过期版本。但 Size-Tiered Compaction 的瞬时空间占用可能高达 2 倍。此外，LSM-Tree 支持更高效的压缩——SSTable 是不可变的、按 key 排序的，这使得块压缩（如 Snappy、LZ4、Zstd）的压缩比通常优于 B+Tree 的页压缩。

选型决策框架

决策维度 倾向 B+Tree 倾向 LSM-Tree
读写比例 读多写少（OLTP 典型场景） 写多读少（日志、时序、消息）
查询模式 点查 + 范围查询为主 以写入和最新数据查询为主
延迟要求 需要稳定的低延迟（P99 敏感） 可接受偶尔的延迟毛刺
存储介质 HDD（随机读性能差，但 B+Tree 读 I/O 少） SSD（顺序写优势明显）
数据规模 中等规模（单机 TB 级） 超大规模（分布式 PB 级）
事务需求 强事务、行级锁 最终一致性或简单事务

工程实践中的混合方案

RocksDB 的 Leveled Compaction 优化

RocksDB 是 Facebook 基于 LevelDB 开发的高性能嵌入式存储引擎，采用 LSM-Tree 架构，在 Leveled Compaction 的基础上做了大量工程优化：

Sub-Compaction（子任务并行）： 将一次大的 Compaction 任务拆分为多个子任务并行执行，充分利用多核 CPU 和 SSD 的并发 I/O 能力。

Dynamic Level Size Adjustment： 根据实际数据量动态调整每层的大小目标，而非使用固定的 10 倍比例。这在数据量远小于最大层容量时，可以显著减少层数和写放大。

Column Family： 支持在同一个数据库实例中创建多个独立的 LSM-Tree（Column Family），每个 Column Family 可以配置不同的 Compaction 策略和参数。例如，元数据使用较小的 MemTable 和激进的 Compaction，用户数据使用较大的 MemTable 和保守的 Compaction。

Rate Limiter： 限制 Compaction 和 Flush 的磁盘 I/O 带宽，避免后台任务抢占前台读写的 I/O 资源。这在生产环境中至关重要——不加限制的 Compaction 可能导致前台请求延迟飙升。

TiKV 的 LSM-Tree 实践

TiKV 是 TiDB 的分布式 KV 存储层，底层使用 RocksDB 作为单机存储引擎。TiKV 在 LSM-Tree 之上增加了分布式层面的优化：

Raft + LSM-Tree 的写入路径： 写请求先通过 Raft 协议在多个副本之间达成共识，然后各副本将数据写入本地的 RocksDB 实例。Raft Log 本身也存储在一个独立的 RocksDB 实例中，实现了"用 LSM-Tree 存储 WAL"的设计。

Region 分裂与 Compaction 的协调： TiKV 将数据按 key 范围划分为 Region（默认 96MB）。当 Region 分裂时，需要确保分裂边界与 SSTable 的 key 范围对齐，否则会导致不必要的 Compaction。TiKV 通过 compaction filter 在 Compaction 过程中同时清理已被 GC 的 MVCC 版本，将垃圾回收与 Compaction 合并，减少额外的 I/O 开销。

Titan：大 Value 分离存储。 当 Value 较大（默认阈值 1KB）时，TiKV 的 Titan 插件会将 Value 单独存储在 Blob 文件中，LSM-Tree 中只保留 Key 和指向 Blob 文件的指针。这大幅减少了 Compaction 期间的数据搬移量，降低写放大。这一设计借鉴了 WiscKey 论文的核心思想：在 SSD 上，随机读的代价已经大幅降低，因此可以用"随机读 Blob 文件"的代价换取"减少 Compaction 写放大"的收益。

WiredTiger 的 B-Tree + LSM 混合引擎

MongoDB 3.2 起采用的 WiredTiger 存储引擎是少有的同时支持 B-Tree 和 LSM-Tree 的混合引擎：

B-Tree 模式（默认）： 使用改良的 B+Tree 结构，支持前缀压缩和页内压缩（Snappy/Zlib/Zstd）。采用 MVCC 和 Hazard Pointer 实现无锁并发读取，通过 Skip List 作为内存缓冲管理脏页。

LSM 模式： 适用于写入密集的工作负载。WiredTiger 的 LSM 实现支持 Bloom Filter 和自动 Compaction，但相比 RocksDB 的 LSM 实现，在 Compaction 策略的丰富度和调优参数上有所不足。

混合策略的实践意义： WiredTiger 的设计表明，B-Tree 和 LSM-Tree 并非不可调和的对立。在同一个系统中，可以根据不同集合（Collection）的访问模式选择不同的存储结构。例如，频繁查询的用户画像数据使用 B-Tree，高频写入的行为日志数据使用 LSM-Tree。

总结

B-Tree 家族与 LSM-Tree 代表了存储引擎设计中两种根本不同的哲学：

  • B-Tree 哲学：读优先。 通过维护全局有序的树结构，在写入时付出额外代价（随机 I/O、页分裂），换取读取时的高效和稳定。这是"写时整理"的策略。
  • LSM-Tree 哲学：写优先。 通过延迟排序和批量合并，将写入代价降到最低（顺序 I/O），在读取时付出额外代价（多层查找、Compaction 开销）。这是"读时整理"的策略。

没有绝对的优劣，只有场景的适配。理解这两类数据结构的原理与权衡，才能在面对具体的存储引擎选型时做出合理的技术决策。从 MySQL 到 Cassandra，从 TiDB 到 CockroachDB，每一个成功的存储系统背后，都是对读写权衡的深思熟虑。

加载导航中...

评论