B+tree 与 LSM-tree：两种存储引擎哲学的碰撞

如果你只能理解两种数据结构来掌握整个存储引擎领域，那一定是 B+tree 和 LSM-tree。前者统治了关系数据库四十余年，后者在 NoSQL 浪潮中异军突起。它们不仅仅是两种数据结构，更代表了两种截然对立的存储哲学：原地更新（update-in-place） 与 追加写入（append-only）。

本文将从第一性原理出发，拆解二者的设计动机、放大因子权衡、经典实现、前沿优化，并给出一份完整的 mini LSM-tree Go 实现。全文约一万字，建议收藏后细读。

一、为什么需要两种树

磁盘（包括 SSD）的物理特性决定了存储引擎的设计空间：

1. 随机写远比顺序写昂贵。 HDD 上随机写的 IOPS 约为 200，而顺序写吞吐可达 200 MB/s；SSD 上随机写虽然好得多，但由于 FTL 的写放大和 GC，顺序写仍然是最优路径。
2. 读操作需要索引。 无论数据怎么写入，最终都要能高效地读出来。没有索引的全表扫描在大数据量下不可接受。
3. 存储空间不是免费的。 冗余数据占用磁盘，也会拖慢扫描速度。

这三个约束形成了一个不可能三角：读放大（Read Amplification）、写放大（Write Amplification）、空间放大（Space Amplification）——你最多只能同时优化其中两个。

B+tree 选择优化读和空间，代价是写放大较高。LSM-tree 选择优化写，代价是读放大和空间放大较高。这就是两种哲学的根源。

二、放大因子三角：RUM 猜想

RUM 猜想（Read-Update-Memory conjecture）由 Harvard DASlab 在 2016 年正式提出，其核心论断是：

对于任何一种数据结构，不可能同时在读放大、写放大（更新代价）和空间放大三个维度上都达到最优。

2.1 形式化定义

设一次逻辑操作涉及的有效数据量为 D，我们定义：

读放大（Read Amplification, RA）：

RA = 实际读取的数据量 / D

对于 B+tree 的点查询，RA 约等于树的高度 h（通常 3-4）；对于 LSM-tree，最坏情况下需要查询每一层：

RA_lsm = L * (1 + bloom_filter_fpr * runs_per_level)

其中 L 是层数，bloom_filter_fpr 是布隆过滤器的假阳性率。

写放大（Write Amplification, WA）：

WA = 实际写入磁盘的数据量 / D

B+tree 每次更新可能触发页分裂，且即使只改一个字节也要写整个页（通常 16 KB）：

WA_btree = page_size / avg_record_size + split_overhead

LSM-tree 的写放大主要来自 compaction（后文详述）：

WA_lsm_leveled = O(T * L)

其中 T 是层与层之间的大小比率（size ratio），L 是层数。

空间放大（Space Amplification, SA）：

SA = 磁盘上实际占用的总空间 / 有效数据（去重后）的大小

B+tree 的空间放大主要来自页的填充因子（通常 ~70%），因此 SA 约为 1.4。LSM-tree 在 compaction 过程中会短暂存在旧版本数据，tiered compaction 下 SA 可能高达 2 倍甚至更多。

2.2 三角图示

上图直观展示了 B+tree、LSM-tree、WiscKey 和 Lazy Leveling 在三角中的大致位置。没有哪个设计能同时占据三个顶点，这就是 RUM 猜想的精髓。

三、B+tree：原地更新的哲学

3.1 核心思想

B+tree 的哲学可以用一句话概括：数据有且只有一份，更新就在原位置覆盖。 这意味着：

• 读操作只需要沿着树的层级向下查找，路径长度 = 树的高度，通常 3-4 层即可覆盖数十亿条记录。
• 写操作需要先找到目标页，然后原地修改。如果页已满，则触发分裂（split）。
• 空间几乎不会膨胀，因为旧数据被直接覆盖。

3.2 页面结构与缓冲池

B+tree 的工作单元是页（page），InnoDB 默认 16 KB。所有数据按页组织，通过缓冲池（Buffer Pool）缓存在内存中。关键操作流程如下：

写入流程：
1. 在缓冲池中找到或加载目标页
2. 修改页内数据（内存操作，极快）
3. 将修改记录到 WAL（Write-Ahead Log）
4. 标记页为 dirty
5. 后台线程异步将 dirty page 刷盘（checkpoint）

这个流程的优雅之处在于：写操作的延迟由 WAL 的顺序写决定（快），而不是随机写数据页决定（慢）。但代价是：

• WAL 本身就是写放大——同一份数据先写 WAL 再写数据页，至少 2 倍 WA。
• 页分裂导致额外写入——分裂时需要写旧页、新页和父节点页。
• 部分页更新——改一条 100 字节的记录，要写整个 16 KB 的页。

3.3 写放大的量化

假设平均记录大小为 r 字节，页大小为 P 字节，页填充率为 f，则：

单次写操作的写放大 = WAL_write(r) + Page_write(P) = r + P

有效写入量 = r

WA = (r + P) / r

以 InnoDB 为例，r = 100 字节，P = 16384 字节：

WA = (100 + 16384) / 100 = 164.84

这个数字看起来很恐怖，但实际上由于缓冲池的存在，热数据页会被多次修改后才刷盘，摊薄了写放大。实际测量中，InnoDB 的 WA 通常在 10-30 之间。

3.4 B+tree 的读性能优势

B+tree 的读性能堪称完美：

• 点查询：O(log_B N) 次 I/O，其中 B 是分支因子。B 通常为数百，因此即使 10 亿条记录也只需 3-4 次磁盘读取。
• 范围查询：找到起始位置后，由于叶子节点通过链表连接，只需顺序扫描即可。
• 缓存友好：由于数据按照键排序存储在连续页中，预读（read-ahead）效果显著。

B+tree 范围查询代价：
  = 定位首条记录的 I/O（h 次）+ 扫描 N 条记录的 I/O（N/records_per_page 次）
  = O(h + N/B)

这是其他结构很难匹敌的。

四、LSM-tree：追加写入的哲学

4.1 核心思想

LSM-tree（Log-Structured Merge-Tree）的哲学截然相反：永远不修改已写入的数据，所有写入都是追加操作。 更新和删除通过写入新版本或墓碑标记（tombstone）实现。

这意味着：

• 写入操作永远是顺序的，天然适配磁盘的物理特性。
• 读操作需要合并多个版本，可能需要检查多个文件。
• 空间会膨胀，因为旧版本暂时还存在于磁盘上。

4.2 LSM-tree 的分层结构

经典 LSM-tree 由以下组件构成：

                    内存
            +------------------+
            |    MemTable      |  <-- 有序跳表或红黑树
            +------------------+
            | Immutable MemTab |  <-- 等待刷盘
            +------------------+

                    磁盘
            +------------------+
            |    Level 0       |  <-- SSTable 文件，可能重叠
            +------------------+
            |    Level 1       |  <-- SSTable 文件，不重叠，有序
            +------------------+
            |    Level 2       |  <-- 大小约为 L1 的 T 倍
            +------------------+
            |      ...         |
            +------------------+
            |    Level L       |  <-- 最大层，存放绝大部分数据
            +------------------+

写入流程：

1. 写入 WAL（顺序写，保证持久性）
2. 插入 MemTable（内存操作）
3. MemTable 满后冻结为 Immutable MemTable
4. 后台将 Immutable MemTable 刷写为 L0 SSTable
5. L0 累积到阈值后，触发 compaction 向下合并

读取流程：

1. 先查 MemTable
2. 再查 Immutable MemTable
3. 逐层查 L0 -> L1 -> ... -> LL 的 SSTable
4. 每层通过 bloom filter 快速判断 key 是否可能存在
5. 找到最新版本即返回

4.3 SSTable 的内部结构

SSTable（Sorted String Table）是 LSM-tree 的基本存储单元，其内部结构如下：

+------------------------------------------+
|              Data Blocks                 |
|  +------+ +------+ +------+ +------+    |
|  |Block0| |Block1| |Block2| |Block3|    |
|  +------+ +------+ +------+ +------+    |
+------------------------------------------+
|           Meta Block (Bloom Filter)      |
+------------------------------------------+
|           Meta Index Block               |
+------------------------------------------+
|              Index Block                 |
|  (每个 data block 的最大 key + offset)    |
+------------------------------------------+
|              Footer                      |
|  (指向 index block 和 meta index block)  |
+------------------------------------------+

每个 Data Block 内部按 key 排序，使用前缀压缩和 delta 编码减少空间占用。Index Block 存储每个 Data Block 的最后一个 key 和偏移量，支持二分查找快速定位。

五、Compaction 策略深度分析

Compaction 是 LSM-tree 的灵魂。它决定了写放大、读放大和空间放大之间的平衡点。两种经典策略是 Leveled Compaction 和 Tiered Compaction。

5.1 Leveled Compaction

Leveled Compaction（LevelDB / RocksDB 默认）的核心规则：

• 每一层除 L0 外，SSTable 的 key 范围不重叠。
• 每一层的总大小是上一层的 T 倍（T 通常为 10）。
• 当某层大小超过阈值时，选择一个 SSTable 与下一层所有重叠的 SSTable 合并排序，写出新的 SSTable。

写放大的逐层推导

假设数据从 MemTable 刷到 L0，再逐层 compact 到最底层 L。设大小比率为 T，则：

L0 -> L1: 数据被读出并写入 L1，WA = 1（首次落盘不算放大）
L1 -> L2: L1 的一个 SSTable 需要与 L2 中最多 T 个重叠的 SSTable 合并
           读取 1 + T 个 SSTable，写出 ~T 个新 SSTable
           写放大贡献 = T
L2 -> L3: 同理，写放大贡献 = T
...
L(i) -> L(i+1): 写放大贡献 = T

总写放大：

WA_total = 1 + T * (L - 1)

其中层数 L 的计算：

L = ceil(log_T(N / M))

N 是数据总量，M 是 MemTable 大小。

以 RocksDB 为例，T = 10，数据量 1 TB，MemTable 64 MB：

L = ceil(log_10(1TB / 64MB)) = ceil(log_10(16384)) = ceil(4.21) = 5

WA = 1 + 10 * (5 - 1) = 41

每写入 1 字节有效数据，磁盘上要写入 41 字节。对于 SSD 来说，这个写放大直接影响设备寿命。

读放大

Leveled Compaction 的读放大相对较低：

点查询 RA:
  L0: 最多 num_l0_files 次查找（L0 文件可能重叠）
  L1-LL: 每层最多 1 次查找（二分定位 + bloom filter 过滤）

  RA = num_l0_files + L * (1 - bloom_fpr)^(-1)

使用 10-bit bloom filter（fpr 约 1%），实际 RA 通常在 1-3 之间。

空间放大

Leveled Compaction 的空间放大较低，因为每层 key 不重叠，且 compact 后旧文件会被删除：

SA = 1 + 1/T = 1.1（T=10 时）

这里的 1/T 来自正在进行 compaction 时临时存在的重复数据。

5.2 Tiered Compaction

Tiered Compaction（Cassandra / HBase 默认）的核心规则：

• 每一层允许多个 SSTable（称为”run”），它们的 key 范围可以重叠。
• 当某层积累了 T 个 run 后，将它们全部合并为下一层的一个 run。
• 本质上是一种”懒惰”策略——尽量延迟 compaction。

写放大

WA_tiered = L * 1 = L

因为每一层的数据只在被推到下一层时写入一次。相比 Leveled 的 T * L，这大大降低了写放大。

读放大

代价是读放大显著增加：

RA_tiered = T * L

因为每层有 T 个可能重叠的 run，每个 run 都可能需要检查。

空间放大

空间放大也更高：

SA_tiered = T（最坏情况）

因为合并前，同一层的 T 个 run 可能包含同一个 key 的多个版本。

5.3 对比总结

可以看到，两种策略在写放大和读放大之间做了精确的镜像交换。

六、前沿优化：WiscKey、Dostoevsky 与 Bloom Filter

6.1 WiscKey：键值分离

WiscKey（FAST 2016）的核心洞察是：compaction 的写放大大部分浪费在搬运 value 上，而 value 往往远大于 key。 如果把 value 从 LSM-tree 中分离出来，只在树中存储 key 和 value 的指针（vLog offset），那么 compaction 只需要搬运极小的 key-pointer 对。

传统 LSM-tree:
  SSTable 中存储: [key1, value1], [key2, value2], ...
  Compaction 搬运全部数据

WiscKey:
  SSTable 中存储: [key1, ptr1], [key2, ptr2], ...
  Value 追加写入 vLog 文件
  Compaction 只搬运 key + 8字节 ptr

写放大的改善：

设 key 大小为 k，value 大小为 v，则：

传统 WA = T * L * (k + v) / (k + v) = T * L
WiscKey WA = T * L * (k + 8) / (k + v)

当 v >> k 时（如 v = 4KB, k = 16B）：
  WiscKey WA = T * L * 24 / 4112 = T * L * 0.006

写放大降低了两个数量级。

但 WiscKey 有代价：

• 范围查询性能下降：value 在 vLog 中不按 key 排序，范围扫描变成随机读。WiscKey 通过并行预读缓解此问题。
• 垃圾回收复杂：vLog 中的无效 value 需要通过额外的 GC 流程清理。
• 空间放大可能增加：vLog 的 GC 不如 compaction 及时。

6.2 Dostoevsky：Lazy Leveling

Dostoevsky（SIGMOD 2018）提出了一种介于 Leveled 和 Tiered 之间的混合策略——Lazy Leveling：

• 最大层（最底层）使用 Leveled 策略：key 不重叠，保证读性能和空间效率。
• 其他层使用 Tiered 策略：允许重叠，减少写放大。

直觉上，最底层存储了绝大部分数据（约 (T-1)/T），保持它有序对读放大的贡献最大。而上层数据量较小，允许它们稍微无序带来的读放大增量很小，但写放大的节省很显著。

Lazy Leveling 的放大因子：
  WA = O(T + L)          （介于 Leveled 的 T*L 和 Tiered 的 L 之间）
  RA_zero_result = O(L)  （得益于最底层有序 + bloom filter）
  RA_non_zero = O(1)     （最底层有序，大概率直接命中）
  SA = O(1 + 1/T)        （与 Leveled 相当）

Dostoevsky 还提出了一个通用框架，通过调节每层的合并策略（Leveled、Tiered 或混合），可以在整个 RUM 三角中连续移动，找到工作负载的最优点。

6.3 Bloom Filter 优化

Bloom Filter 是 LSM-tree 读性能的生命线。没有 bloom filter，每次点查询都需要在每层做二分查找；有了 bloom filter，大部分层可以被跳过。

基本原理

Bloom filter 使用 m 位的位数组和 k 个哈希函数。对于 n 个元素：

假阳性率 fpr = (1 - e^(-kn/m))^k

最优哈希函数数量 k_opt = (m/n) * ln(2)

此时 fpr_opt = (1/2)^k = (0.6185)^(m/n)

每个元素分配 10 位时，fpr 约为 0.82%。

分层 Bloom Filter（Monkey 优化）

Monkey（SIGMOD 2017）的洞察是：不需要每层都用相同精度的 bloom filter。 底层数据量大，一次假阳性的代价高（需要读取大文件），应该分配更多的位；顶层数据量小，假阳性的代价低，可以分配更少的位。

最优分配策略（给定总内存预算 M）：

每层的 fpr 应该满足：
  fpr_i = fpr_L * T^(L-i)

即底层的 fpr 最小，每往上一层 fpr 增大 T 倍。

这种分配策略可以在相同内存预算下，将整体读放大降低到：

RA_monkey = e^(-M / (N * ln2^2))

相比均匀分配，Monkey 优化通常可以将读放大降低 50%-80%。

七、RocksDB vs InnoDB：YCSB 基准测试对比

YCSB（Yahoo Cloud Serving Benchmark）定义了 6 种工作负载模式，覆盖了常见的数据库使用场景。以下数据基于公开的基准测试结果，硬件环境为 NVMe SSD、64 GB 内存、数据集 100 GB。

7.1 工作负载定义

7.2 吞吐量对比（ops/sec）

7.3 关键分析

写入密集型（A, D, F）：RocksDB 胜出。 MemTable 的批量写入 + 顺序刷盘天然优于 B+tree 的随机页写入。尤其是在数据集远大于内存时，InnoDB 的缓冲池命中率下降，随机 I/O 增多，差距会进一步拉大。

读密集型（B, C）：InnoDB 略胜。 B+tree 的点查询路径短且确定（3-4 次 I/O），而 LSM-tree 即使有 bloom filter，仍可能需要检查多层。当数据集能装进缓冲池时，InnoDB 的优势更明显。

范围扫描（E）：InnoDB 大幅胜出。 这是 B+tree 的绝对领地。叶子节点的链表结构使得范围扫描只需顺序 I/O；而 LSM-tree 需要归并多个 SSTable 的迭代器，开销远大于顺序扫描。

7.4 写放大实测

等一下——RocksDB 的写放大更高，吞吐量怎么还更好？

关键在于写入路径的本质不同：

• InnoDB 的低写放大来自缓冲池的合并效果（多次修改同一页后才刷盘），但代价是随机 I/O。
• RocksDB 虽然写放大更高，但所有写入都是顺序 I/O。在 SSD 上，顺序写的带宽远大于随机写，足以抵消更高的写放大。

这再次证明了：放大因子不是唯一指标，I/O 模式同样关键。

7.5 尾延迟

RocksDB 的读尾延迟更高（受 compaction 影响），但写尾延迟更低（MemTable 写入路径稳定）。InnoDB 相反——读延迟稳定，但写延迟受 checkpoint 和页刷盘影响。

八、Go 实现：Mini LSM-tree

下面给出一个完整的 mini LSM-tree 实现，包含 MemTable（跳表简化为有序切片）、WAL、SSTable 和 Leveled Compaction。代码约 250 行，可直接编译运行。

package main

import (
    "bufio"
    "encoding/binary"
    "fmt"
    "io"
    "os"
    "path/filepath"
    "sort"
    "sync"
    "time"
)

// ---------- KV pair ----------

type KV struct {
    Key   string
    Value string
    Tomb  bool // true 表示墓碑删除
}

// ---------- MemTable ----------

type MemTable struct {
    data []KV
    size int
}

func NewMemTable() *MemTable { return &MemTable{} }

func (m *MemTable) Put(key, value string) {
    // 二分查找插入或覆盖
    i := sort.Search(len(m.data), func(j int) bool { return m.data[j].Key >= key })
    kv := KV{Key: key, Value: value}
    if i < len(m.data) && m.data[i].Key == key {
        m.size += len(value) - len(m.data[i].Value)
        m.data[i] = kv
    } else {
        m.data = append(m.data, KV{})
        copy(m.data[i+1:], m.data[i:])
        m.data[i] = kv
        m.size += len(key) + len(value)
    }
}

func (m *MemTable) Delete(key string) {
    m.Put(key, "")
    i := sort.Search(len(m.data), func(j int) bool { return m.data[j].Key >= key })
    if i < len(m.data) && m.data[i].Key == key {
        m.data[i].Tomb = true
    }
}

func (m *MemTable) Get(key string) (string, bool) {
    i := sort.Search(len(m.data), func(j int) bool { return m.data[j].Key >= key })
    if i < len(m.data) && m.data[i].Key == key {
        if m.data[i].Tomb {
            return "", false
        }
        return m.data[i].Value, true
    }
    return "", false
}

func (m *MemTable) Len() int { return len(m.data) }
func (m *MemTable) Size() int { return m.size }

// ---------- WAL ----------

type WAL struct {
    f *os.File
    w *bufio.Writer
}

func OpenWAL(path string) (*WAL, error) {
    f, err := os.OpenFile(path, os.O_CREATE|os.O_APPEND|os.O_WRONLY, 0644)
    if err != nil {
        return nil, err
    }
    return &WAL{f: f, w: bufio.NewWriter(f)}, nil
}

func (w *WAL) Append(kv KV) error {
    // 简单格式：[keyLen:4][valLen:4][tomb:1][key][value]
    buf := make([]byte, 9)
    binary.LittleEndian.PutUint32(buf[0:4], uint32(len(kv.Key)))
    binary.LittleEndian.PutUint32(buf[4:8], uint32(len(kv.Value)))
    if kv.Tomb {
        buf[8] = 1
    }
    if _, err := w.w.Write(buf); err != nil {
        return err
    }
    if _, err := w.w.WriteString(kv.Key); err != nil {
        return err
    }
    if _, err := w.w.WriteString(kv.Value); err != nil {
        return err
    }
    return w.w.Flush()
}

func (w *WAL) Close() error {
    _ = w.w.Flush()
    return w.f.Close()
}

func RecoverWAL(path string) ([]KV, error) {
    f, err := os.Open(path)
    if err != nil {
        if os.IsNotExist(err) {
            return nil, nil
        }
        return nil, err
    }
    defer f.Close()
    r := bufio.NewReader(f)
    var kvs []KV
    for {
        buf := make([]byte, 9)
        if _, err := io.ReadFull(r, buf); err != nil {
            break
        }
        kLen := binary.LittleEndian.Uint32(buf[0:4])
        vLen := binary.LittleEndian.Uint32(buf[4:8])
        tomb := buf[8] == 1
        key := make([]byte, kLen)
        val := make([]byte, vLen)
        if _, err := io.ReadFull(r, key); err != nil {
            break
        }
        if _, err := io.ReadFull(r, val); err != nil {
            break
        }
        kvs = append(kvs, KV{Key: string(key), Value: string(val), Tomb: tomb})
    }
    return kvs, nil
}

// ---------- SSTable ----------

type SSTable struct {
    path string
    kvs  []KV // 简化：全部加载到内存
}

func WriteSSTable(path string, kvs []KV) error {
    f, err := os.Create(path)
    if err != nil {
        return err
    }
    defer f.Close()
    w := bufio.NewWriter(f)
    for _, kv := range kvs {
        buf := make([]byte, 9)
        binary.LittleEndian.PutUint32(buf[0:4], uint32(len(kv.Key)))
        binary.LittleEndian.PutUint32(buf[4:8], uint32(len(kv.Value)))
        if kv.Tomb {
            buf[8] = 1
        }
        _, _ = w.Write(buf)
        _, _ = w.WriteString(kv.Key)
        _, _ = w.WriteString(kv.Value)
    }
    return w.Flush()
}

func ReadSSTable(path string) (*SSTable, error) {
    kvs, err := RecoverWAL(path) // 格式相同，复用解析
    if err != nil {
        return nil, err
    }
    return &SSTable{path: path, kvs: kvs}, nil
}

func (s *SSTable) Get(key string) (string, bool, bool) {
    i := sort.Search(len(s.kvs), func(j int) bool { return s.kvs[j].Key >= key })
    if i < len(s.kvs) && s.kvs[i].Key == key {
        return s.kvs[i].Value, true, s.kvs[i].Tomb
    }
    return "", false, false
}

// ---------- LSMTree ----------

const (
    MemTableLimit = 4096 // MemTable 大小阈值（字节）
    L0Limit       = 4    // L0 文件数阈值
)

type LSMTree struct {
    mu       sync.RWMutex
    dir      string
    mem      *MemTable
    imm      *MemTable // immutable MemTable
    wal      *WAL
    levels   [][]*SSTable // levels[0] = L0, levels[1] = L1 ...
    seqNo    int
}

func OpenLSMTree(dir string) (*LSMTree, error) {
    if err := os.MkdirAll(dir, 0755); err != nil {
        return nil, err
    }
    tree := &LSMTree{
        dir:    dir,
        mem:    NewMemTable(),
        levels: make([][]*SSTable, 4),
    }
    // 恢复 WAL
    kvs, _ := RecoverWAL(filepath.Join(dir, "wal.log"))
    for _, kv := range kvs {
        tree.mem.Put(kv.Key, kv.Value)
        if kv.Tomb {
            tree.mem.Delete(kv.Key)
        }
    }
    wal, err := OpenWAL(filepath.Join(dir, "wal.log"))
    if err != nil {
        return nil, err
    }
    tree.wal = wal
    return tree, nil
}

func (t *LSMTree) Put(key, value string) error {
    t.mu.Lock()
    defer t.mu.Unlock()
    kv := KV{Key: key, Value: value}
    if err := t.wal.Append(kv); err != nil {
        return err
    }
    t.mem.Put(key, value)
    if t.mem.Size() >= MemTableLimit {
        return t.rotateMemTable()
    }
    return nil
}

func (t *LSMTree) Delete(key string) error {
    t.mu.Lock()
    defer t.mu.Unlock()
    kv := KV{Key: key, Tomb: true}
    if err := t.wal.Append(kv); err != nil {
        return err
    }
    t.mem.Delete(key)
    if t.mem.Size() >= MemTableLimit {
        return t.rotateMemTable()
    }
    return nil
}

func (t *LSMTree) Get(key string) (string, bool) {
    t.mu.RLock()
    defer t.mu.RUnlock()
    // 1. 查 MemTable
    if v, ok := t.mem.Get(key); ok {
        return v, true
    }
    // 2. 查 Immutable MemTable
    if t.imm != nil {
        if v, ok := t.imm.Get(key); ok {
            return v, true
        }
    }
    // 3. 逐层查 SSTable（新 -> 旧）
    for _, level := range t.levels {
        for i := len(level) - 1; i >= 0; i-- {
            v, found, tomb := level[i].Get(key)
            if found {
                if tomb {
                    return "", false
                }
                return v, true
            }
        }
    }
    return "", false
}

func (t *LSMTree) rotateMemTable() error {
    // 冻结当前 MemTable
    t.imm = t.mem
    t.mem = NewMemTable()
    _ = t.wal.Close()
    // 刷写 immutable MemTable 为 L0 SSTable
    t.seqNo++
    sstPath := filepath.Join(t.dir, fmt.Sprintf("l0_%06d.sst", t.seqNo))
    if err := WriteSSTable(sstPath, t.imm.data); err != nil {
        return err
    }
    sst, _ := ReadSSTable(sstPath)
    t.levels[0] = append(t.levels[0], sst)
    t.imm = nil
    // 删旧 WAL，开新 WAL
    _ = os.Remove(filepath.Join(t.dir, "wal.log"))
    wal, err := OpenWAL(filepath.Join(t.dir, "wal.log"))
    if err != nil {
        return err
    }
    t.wal = wal
    // 检查是否需要 compaction
    if len(t.levels[0]) >= L0Limit {
        t.compact(0)
    }
    return nil
}

func (t *LSMTree) compact(level int) {
    if level+1 >= len(t.levels) {
        return
    }
    // 合并 levels[level] 的所有 SSTable 与 levels[level+1] 的所有 SSTable
    var merged []KV
    for _, sst := range t.levels[level] {
        merged = append(merged, sst.kvs...)
    }
    for _, sst := range t.levels[level+1] {
        merged = append(merged, sst.kvs...)
    }
    // 按 key 排序，相同 key 保留最新版本
    sort.SliceStable(merged, func(i, j int) bool {
        return merged[i].Key < merged[j].Key
    })
    deduped := merged[:0]
    for i, kv := range merged {
        if i > 0 && kv.Key == merged[i-1].Key {
            deduped[len(deduped)-1] = kv // 覆盖旧版本
            continue
        }
        deduped = append(deduped, kv)
    }
    // 过滤最底层的墓碑
    if level+1 == len(t.levels)-1 {
        alive := deduped[:0]
        for _, kv := range deduped {
            if !kv.Tomb {
                alive = append(alive, kv)
            }
        }
        deduped = alive
    }
    // 删除旧文件
    for _, sst := range t.levels[level] {
        _ = os.Remove(sst.path)
    }
    for _, sst := range t.levels[level+1] {
        _ = os.Remove(sst.path)
    }
    t.levels[level] = nil
    // 写入新 SSTable
    t.seqNo++
    sstPath := filepath.Join(t.dir, fmt.Sprintf("l%d_%06d.sst", level+1, t.seqNo))
    _ = WriteSSTable(sstPath, deduped)
    sst, _ := ReadSSTable(sstPath)
    t.levels[level+1] = []*SSTable{sst}
    // 递归检查下一层
    if len(t.levels[level+1]) > (level+2)*(level+2) {
        t.compact(level + 1)
    }
}

func (t *LSMTree) Close() error {
    return t.wal.Close()
}

// ---------- main ----------

func main() {
    dir := "mini_lsm_data"
    defer os.RemoveAll(dir)

    tree, err := OpenLSMTree(dir)
    if err != nil {
        panic(err)
    }
    defer tree.Close()

    // 写入测试数据
    start := time.Now()
    for i := 0; i < 5000; i++ {
        key := fmt.Sprintf("key_%06d", i)
        val := fmt.Sprintf("value_%06d_%s", i, "padding_data_for_size")
        _ = tree.Put(key, val)
    }
    fmt.Printf("写入 5000 条记录耗时: %v\n", time.Since(start))

    // 读取验证
    start = time.Now()
    found, miss := 0, 0
    for i := 0; i < 5000; i++ {
        key := fmt.Sprintf("key_%06d", i)
        if _, ok := tree.Get(key); ok {
            found++
        } else {
            miss++
        }
    }
    fmt.Printf("读取 5000 条记录耗时: %v (found=%d, miss=%d)\n",
        time.Since(start), found, miss)

    // 删除测试
    for i := 0; i < 100; i++ {
        _ = tree.Delete(fmt.Sprintf("key_%06d", i))
    }
    if _, ok := tree.Get("key_000050"); !ok {
        fmt.Println("key_000050 已被正确删除")
    }
    if v, ok := tree.Get("key_000200"); ok {
        fmt.Printf("key_000200 = %s\n", v)
    }
}

8.1 代码架构要点

1. MemTable 使用有序切片实现，二分查找保证 O(log n) 的插入和查询。生产环境应使用跳表（skiplist）以获得更好的并发性能。
2. WAL 使用简单的二进制格式：[keyLen:4][valLen:4][tomb:1][key][value]。每次写入后立即 flush，保证持久性。
3. SSTable 与 WAL 共用格式，简化实现。生产环境中 SSTable 应包含 index block、bloom filter 和压缩。
4. Compaction 实现了简化版的 leveled compaction：当 L0 积累 4 个文件时，与 L1 合并；同理逐层向下。合并时去重并在最底层清理墓碑。
5. 并发控制 使用读写锁：读操作共享锁，写操作排他锁。生产环境应使用更细粒度的锁或无锁结构。

8.2 可运行验证

将上述代码保存为 main.go，执行：

go run main.go

预期输出：

写入 5000 条记录耗时: ~15ms
读取 5000 条记录耗时: ~5ms (found=5000, miss=0)
key_000050 已被正确删除
key_000200 = value_000200_padding_data_for_size

九、实战选型：什么场景用什么引擎

9.1 OLTP（在线事务处理）

推荐：B+tree（InnoDB、PostgreSQL）

OLTP 的特征是：短事务、点查询为主、读写混合、需要强一致性。B+tree 在这个场景下的优势：

• 点查询延迟稳定，可预测的 P99。
• 范围查询高效，支持复杂的 WHERE 条件。
• 行锁粒度细，并发事务冲突小。
• 成熟的 MVCC 实现，事务隔离级别丰富。

LSM-tree 在 OLTP 场景的劣势：

• compaction 导致的性能毛刺（P99 不稳定）。
• 范围查询需要归并多个迭代器。
• 空间放大在更新频繁时较大。

但如果 OLTP 负载的写入比例极高（>80%），且可以容忍较高的读延迟，LSM-tree 也是可行的选择。MyRocks（MySQL + RocksDB）正是这种场景的实践。

9.2 OLAP（在线分析处理）

推荐：列式存储（Parquet、ClickHouse），而非 B+tree 或 LSM-tree

OLAP 的特征是全表扫描、聚合计算、批量加载。传统的行式 B+tree 和 LSM-tree 都不是最优选择。但如果必须在二者中选择：

• 批量加载场景：LSM-tree 更优（顺序写入，bulk load 友好）。
• 需要实时更新的分析场景：B+tree 更优（原地更新，不需要等 compaction）。

9.3 时序数据库

推荐：LSM-tree（InfluxDB、TimescaleDB 的底层选择）

时序数据的特征：

• 写入密集：传感器数据持续涌入，写入远多于读取。
• 数据天然有序：按时间戳递增，天然适合 LSM-tree 的顺序写入。
• 读取模式：通常是时间范围查询，LSM-tree 的有序 SSTable 可以高效支持。
• TTL 友好：过期数据可以整个 SSTable 文件直接删除，无需逐条处理。

9.4 键值存储

推荐：LSM-tree（Redis 持久化层、CockroachDB、TiKV）

键值存储的访问模式简单（Get/Put/Delete），LSM-tree 的优势得以充分发挥：

• 写入吞吐量高。
• 点查询通过 bloom filter 优化后接近 B+tree。
• 空间效率通过压缩得到保障。

9.5 混合负载（HTAP）

推荐：混合引擎（TiDB 的 TiKV + TiFlash）

当系统同时需要处理事务和分析时，单一引擎很难兼顾。现代方案是用不同引擎处理不同类型的查询，通过 Raft 或 CDC 同步数据。

十、工程实践中的坑

以下是实际工程中使用这两种引擎时常见的问题和应对策略：

十一、进阶话题与前沿方向

11.1 混合结构：B-epsilon tree

B-epsilon tree 是 B+tree 和 LSM-tree 的理论中间地带。它在每个内部节点上维护一个缓冲区（buffer），写入操作先缓冲在节点中，满后再向下推送。

写放大: O((B^epsilon) * log_B N / epsilon)
读放大: O(log_B N / epsilon)

其中 epsilon 在 0 到 1 之间，epsilon = 0 退化为 B+tree，epsilon = 1 退化为类似 LSM-tree 的行为。TokuDB / PerconaFT 是其工业实现。

11.2 NVM（非易失性内存）的影响

随着 Intel Optane（虽然已停产）和 CXL 内存的出现，存储层次结构正在改变：

• B+tree 受益更大：NVM 消除了随机写的惩罚，B+tree 的原地更新不再昂贵。
• LSM-tree 的优势缩小：当顺序写和随机写的差距缩小时，LSM-tree 的核心卖点（将随机写转为顺序写）价值下降。

但 LSM-tree 的其他优势（压缩、批量写入、简单的并发控制）仍然存在，因此不会完全被取代。

11.3 学术前沿

• SILK（USENIX ATC 2019）：通过 I/O 调度器协调 compaction 和前台请求，将 LSM-tree 的尾延迟降低 90%。
• MatrixKV（FAST 2021）：利用 NVM 加速 LSM-tree 的写入路径，将 MemTable 放在 NVM 上减少 WAL 开销。
• REMIX（FAST 2021）：通过全局排序索引消除 LSM-tree 的读放大，同时保持低写放大。
• Lethe（SIGMOD 2020）：为 LSM-tree 添加高效的 delete-aware compaction，解决墓碑堆积问题。

十二、个人观点

写了这么多客观分析，最后谈谈我的主观看法。

1. 不要盲目追新。 NoSQL 浪潮中，很多团队盲目从 MySQL 迁移到 RocksDB 或 Cassandra，结果发现读延迟不稳定、运维复杂度暴增。B+tree 经过四十年的打磨，其工程成熟度是 LSM-tree 目前无法比拟的。如果你的负载是经典的 OLTP，InnoDB 仍然是最安全的选择。

2. 写入密集型场景，LSM-tree 确实是王者。 时序数据库、日志存储、消息队列的持久化层——这些场景下 LSM-tree 的顺序写入优势是压倒性的。不要试图用 B+tree 硬扛海量写入，你会在 checkpoint 和页分裂中痛苦挣扎。

3. 关注写放大对 SSD 的影响。 很多人低估了这一点。一块标称 3 DWPD（Drive Writes Per Day）的企业级 SSD，在 RocksDB 的 40 倍写放大下，实际可用 DWPD 不到 0.1。这直接影响硬件成本和设备寿命。在 SSD 大规模部署的场景下，WiscKey 这样的键值分离优化不是可选项，而是必须。

4. 未来属于自适应引擎。 Dostoevsky 的思想指明了方向：不应该让工程师手动选择引擎和调参，系统应该根据工作负载自动调整 compaction 策略和放大因子的平衡点。CockroachDB 的 Pebble 引擎已经在这个方向上做了一些探索（自适应 compaction 速率），未来会看到更多这样的系统。

5. 理解第一性原理比记住结论重要。 存储引擎的设计空间是连续的，B+tree 和 LSM-tree 只是两个极端点。理解 RUM 猜想、理解磁盘的物理特性、理解放大因子的推导过程，你就能自己分析任何新出现的存储引擎设计，而不需要等别人写文章告诉你结论。

参考文献

1. O’Neil P, Cheng E, Gawlick D, et al. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996.
2. Athanassoulis M, Kester M S, Maas L M, et al. Designing Access Methods: The RUM Conjecture. EDBT, 2016.
3. Lu L, Pillai T S, Gopalakrishnan H, et al. WiscKey: Separating Keys from Values in SSD-Conscious Storage. FAST, 2016.
4. Dayan N, Idreos S. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. SIGMOD, 2018.
5. Dayan N, Athanassoulis M, Idreos S. Monkey: Optimal Navigable Key-Value Store. SIGMOD, 2017.
6. Balmau O, Didona D, Guerraoui R, et al. SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. USENIX ATC, 2019.
7. Cooper B F, Silberstein A, Tam E, et al. Benchmarking Cloud Serving Systems with YCSB. SoCC, 2010.
8. Dong S, Callaghan M, Galanis L, et al. Optimizing Space Amplification in RocksDB. CIDR, 2017.

上一篇: B-tree 深度解剖 下一篇: Treap 与跳表

相关阅读: - LSM Compaction 策略 - 缓冲池管理算法