第2章：B树与LSM树（B-Trees and LSM Trees）

一、导读

1.1 本章学习目标

第2章深入讲解数据库存储引擎中最核心的两种数据结构：B+ 树和 LSM 树。这两种结构代表了存储引擎设计的两个基本方向——B+ 树通过原地更新实现读优化，LSM 树通过追加写入实现写优化。理解它们的内部工作原理，是选择和使用数据库的基础。

本章的核心学习目标包括：

掌握 B+ 树的完整结构：内部节点、叶子节点、指针链接、分裂与合并
理解 B+ 树的 I/O 模型：为什么 B+ 树适合磁盘存储？树的高度如何影响查询性能？
掌握 LSM 树的基本结构：MemTable、SSTable、Compaction 的协同工作
理解 LSM 树的读写放大：写放大、读放大、空间放大的权衡关系
对比 B+ 树和 LSM 树的适用场景：什么场景选 B+ 树？什么场景选 LSM 树？
了解压缩策略对存储引擎的影响：Snappy、Zstd、LZ4 等压缩算法的选择

1.2 为什么本章如此重要

B+ 树和 LSM 树是数据库存储引擎的两大基石。几乎所有主流数据库的底层存储都基于这两种结构之一：

B+ 树阵营：MySQL InnoDB、PostgreSQL、Oracle、SQLite
LSM 树阵营：RocksDB、LevelDB、Cassandra、HBase、TiKV

选择 B+ 树还是 LSM 树，本质上是在读写性能之间做权衡。B+ 树的读性能优秀（O(log n) 的树遍历），但写入可能触发页分裂和随机 I/O；LSM 树的写入性能优秀（顺序追加），但读取可能需要查找多个 SSTable。

理解这两种结构的内部机制，不仅能帮助你选择合适的数据库，还能指导你进行性能调优——比如知道为什么 InnoDB 的主键选择很重要，为什么 Cassandra 的 Compaction 策略会影响查询延迟。

1.3 核心问题引导

在阅读本章时，请带着以下问题思考：

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

一棵包含 10 亿条记录的 B+ 树有多高？需要几次磁盘 I/O？

B+ 树的页分裂是如何发生的？它对写入性能有什么影响？

LSM 树的 MemTable 为什么要用跳表或红黑树实现？

Leveled Compaction 和 Tiered Compaction 各有什么优缺点？

为什么 LSM 树需要 Bloom Filter？它如何减少读的放大？

二、核心概念详解

2.1 B+ 树的结构与原理

2.1.1 B+ 树 vs B 树

B+ 树是 B 树的变体，关键区别在于：

B 树：所有节点（包括内部节点）都存储数据
B+ 树：只有叶子节点存储数据，内部节点只存储键值和子节点指针

B 树 (order=3):
         [10|20]
        /   |   \
    [5|7] [13|17] [25|30]

B+ 树 (order=3):
         [10|20]           ← 内部节点只有键
        /   |   \
  [5|7|→] [13|17|→] [25|30|→]  ← 叶子节点有数据 + 兄弟指针
       └──→ ──┘ └──→ ──┘

B+ 树的优势：

内部节点更小：不存储数据，每个内部节点可以容纳更多键值，树更矮

顺序访问高效：叶子节点通过指针链接，范围查询只需遍历叶子层

查询性能稳定：所有查询都要走到叶子节点，性能一致

2.1.2 B+ 树的参数计算

以 InnoDB 为例（页大小 16KB，主键为 BIGINT 8 字节，行大小约 100 字节）：

内部节点:
- 每个键: 8 字节 (BIGINT) + 6 字节 (子指针) = 14 字节
- 每页可容纳: 16384 / 14 ≈ 1170 个键
- 分支因子: ~1170

叶子节点:
- 每条记录: 100 字节 (数据) + 26 字节 (行头+事务ID+滚指针) = 126 字节
- 每页可容纳: 16384 / 126 ≈ 130 条记录
- 填充因子: ~70% → 实际 ~91 条

树的高度:
- 高度 1: 91 条记录
- 高度 2: 1170 × 91 = 106,470 条
- 高度 3: 1170 × 1170 × 91 = 124,518,300 条 (1.2亿)
- 高度 4: 1170^3 × 91 ≈ 1456 亿条

结论: 10亿条记录的表，B+ 树高度为 3-4 层
每次点查需要 3-4 次 I/O（缓冲池可缓存根节点和部分内部节点）

2.1.3 页分裂与合并

当向一个已满的叶子页插入新记录时，触发页分裂（Page Split）：

分裂前:
Page A (已满): [k1, k2, k3, ..., k_n]

分裂后:
Page A (前半): [k1, k2, ..., k_m]
Page B (后半): [k_m+1, ..., k_n]
父节点新增: [k_m+1] → 指向 Page B

如果父节点也满了 → 递归分裂 → 可能增加树的高度

页分裂的代价：

额外的 I/O：需要写入两个新页 + 更新父节点
空间浪费：分裂后两个页的填充度约 50%-70%
树高度增长：最坏情况下树会增加一层

优化策略：

预分配空间：InnoDB 在页中预留一定的空闲空间（填充因子）
批量插入优化：按主键顺序插入时，使用"页的右端追加"优化，避免频繁分裂
合并（Merge）：当两个相邻页都很空时，合并为一个页，减少空间浪费

2.2 LSM 树的结构与原理

2.2.1 LSM 树的基本思想

LSM（Log-Structured Merge）树的核心思想是：将随机写转换为顺序写。

传统的 B+ 树在写入时需要找到目标页并原地修改，这可能产生随机 I/O。LSM 树的做法完全不同：

新数据首先写入内存中的有序结构（MemTable）

MemTable 满后，整体刷写为磁盘上的有序文件（SSTable）

后台定期合并多个 SSTable（Compaction），消除过期数据

写入路径:
Client → Write → WAL → MemTable (内存) → [满了] → SSTable (磁盘)

读取路径:
Client → Read → 先查 MemTable → 再查 Immutable MemTable → 
       → 依次查 Level 0, Level 1, ..., Level N 的 SSTable

2.2.2 MemTable

MemTable 是 LSM 树的内存组件，它是一个有序的键值映射：

常用实现：跳表（SkipList，如 LevelDB/RocksDB）、红黑树（如早期 Bigtable）
特点：支持高效的插入（O(log n)）和查找（O(log n)），支持有序遍历
大小：通常配置为 64MB-256MB

MemTable 结构 (SkipList):
Level 3:  [1] ──────────────────────→ [50]
Level 2:  [1] ──→ [10] ────────────→ [50] ──→ [80]
Level 1:  [1] → [5] → [10] → [20] → [50] → [65] → [80]
Level 0:  [1] → [3] → [5] → [8] → [10] → [15] → [20] → ...

插入: 从最高层开始查找，逐层下降 → O(log n)
查找: 从最高层开始，逐层缩小范围 → O(log n)

当 MemTable 达到大小阈值时，它被冻结为 Immutable MemTable，后台线程将其刷写为磁盘上的 SSTable。在此期间，新的写入进入新的 MemTable。

2.2.3 SSTable

SSTable（Sorted String Table）是 LSM 树的磁盘组件，它是一个不可变的有序文件：

SSTable 文件结构:
┌──────────────────────────────┐
│         Data Block 0         │  ← 有序的键值对
├──────────────────────────────┤
│         Data Block 1         │
├──────────────────────────────┤
│           ...                │
├──────────────────────────────┤
│         Data Block N         │
├──────────────────────────────┤
│        Index Block           │  ← 每个 Data Block 的最后一个键 + 偏移
├──────────────────────────────┤
│       Bloom Filter           │  ← 用于快速判断键是否存在
├──────────────────────────────┤
│       Meta Block             │  ← 元数据（统计信息等）
├──────────────────────────────┤
│    Footer (Magic Number)     │  ← 文件头信息
└──────────────────────────────┘

Data Block 的内部结构：

Data Block (压缩前):
┌────────────────────────────────┐
│ key_len | val_len | key | val  │  ← 键值对 1
├────────────────────────────────┤
│ key_len | val_len | key | val  │  ← 键值对 2
├────────────────────────────────┤
│           ...                  │
├────────────────────────────────┤
│        Restart Points          │  ← 用于二分查找的锚点
├────────────────────────────────┤
│   num_restarts | checksum     │
└────────────────────────────────┘

前缀压缩:
原始: [abc123, abc456, abc789]
压缩: [abc123, 3|456, 3|789]  ← 共享前缀 "abc"

2.2.4 Compaction 策略

Compaction 是 LSM 树最核心的机制——它负责合并多个 SSTable，消除过期数据和删除标记，控制读放大。

Leveled Compaction（LevelDB/RocksDB 默认）：

Level 0:  [SST0] [SST1] [SST2]     ← 从 MemTable 刷写，键范围可重叠
Level 1:  [SST3] [SST4] [SST5] ... ← 键范围不重叠，每层最多 10× 上层大小
Level 2:  [SST...] ...              ← 更大的层
Level N:  ...

Compaction 过程:
1. 选择 Level L 的一个 SSTable
2. 找到 Level L+1 中键范围重叠的所有 SSTable
3. 多路归并这些 SSTable → 生成新的 Level L+1 SSTable
4. 删除旧的 SSTable

特点:
- 读放大小: 每个键最多存在于每层一个 SSTable 中
- 写放大大: 同一条数据可能经历多次 Compaction
- 空间放大小: 数据只存在于一个层级

Tiered Compaction（Cassandra 默认）：

Tier 0:  [SST0] [SST1] [SST2]     ← 键范围可重叠
Tier 1:  [SST3] [SST4] [SST5]     ← 键范围可重叠
Tier 2:  [SST6] [SST7] [SST8] ...

Compaction 过程:
1. 选择一个 Tier 中所有 SSTable
2. 多路归并 → 生成新的 Tier+1 SSTable
3. 删除旧 SSTable

特点:
- 读放大大: 同一个键可能存在于多个 SSTable 中
- 写放大小: 数据移动次数少
- 空间放大大: 可能存在多份过期数据

2.3 Bloom Filter——减少读放大

2.3.1 工作原理

Bloom Filter 是一种空间效率极高的概率数据结构，用于判断一个元素是否属于集合：

可能存在于集合中（有一定误判率）
一定不存在于集合中（无误判）

Bloom Filter 结构:
位数组: [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]  (16 bits)
哈希函数: h1, h2, h3

插入 "hello":
h1("hello") = 3  → [0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
h2("hello") = 7  → [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
h3("hello") = 12 → [0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0]

查询 "hello": h1=3(1), h2=7(1), h3=12(1) → 可能存在 ✓
查询 "world": h1=3(1), h2=5(0) → 一定不存在 ✗

2.3.2 在 LSM 树中的应用

每个 SSTable 都附带一个 Bloom Filter。读取时：

先查询 SSTable 的 Bloom Filter

如果 Bloom Filter 说"不存在"→ 跳过该 SSTable（节省一次磁盘 I/O）

如果 Bloom Filter 说"可能存在"→ 实际查找 SSTable

没有 Bloom Filter 的读取:
查找 key="user:1001"
→ 查 Level 0 SSTable 0: 不在 (1次 I/O)
→ 查 Level 0 SSTable 1: 不在 (1次 I/O)
→ 查 Level 1 SSTable 3: 不在 (1次 I/O)
→ 查 Level 1 SSTable 4: 找到了! (1次 I/O)
总计: 4 次 I/O

有 Bloom Filter 的读取:
查找 key="user:1001"
→ Level 0 SSTable 0 Bloom Filter: 不存在 → 跳过
→ Level 0 SSTable 1 Bloom Filter: 不存在 → 跳过
→ Level 1 SSTable 3 Bloom Filter: 可能存在 → 查找 (1次 I/O)
→ Level 1 SSTable 4 Bloom Filter: 可能存在 → 查找 (1次 I/O)
总计: 2 次 I/O (节省 50%)

Bloom Filter 的误判率通常为 1%-2%，占用空间约 10-12 bits/key

2.4 B+ 树 vs LSM 树：全面对比

维度	B+ 树	LSM 树
写入模式	原地更新	追加写入
写放大	低（1x-3x）	高（10x-30x）
读放大	低（O(log n)）	高（可能查多个 SSTable）
空间放大	低（10%-30%）	中（取决于 Compaction）
写入吞吐	中等	高（接近顺序写带宽）
读取延迟	稳定	不稳定（取决于 Compaction）
适用场景	读多写少	写多读少
代表系统	InnoDB, PostgreSQL	RocksDB, Cassandra

选择指南:
- 读多写少（10:1 以上）→ B+ 树
- 写多读少（10:1 以上）→ LSM 树
- 读写均衡 → 取决于延迟敏感度
  - 延迟敏感 → B+ 树（延迟更稳定）
  - 吞吐优先 → LSM 树（写入吞吐更高）

三、实战案例

3.1 案例一：B+ 树的可视化与性能分析

python

class BPlusTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []
        self.next = None  # 叶子节点的兄弟指针
        self.values = []  # 叶子节点的值

class BPlusTree:
    def __init__(self, order=4):
        self.root = BPlusTreeNode()
        self.order = order

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node.leaf:
            if key in node.keys:
                idx = node.keys.index(key)
                return node.values[idx]
            return None
        else:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            return self._search(node.children[i], key)

    def insert(self, key, value):
        self._insert(self.root, key, value)
        if len(self.root.keys) > self.order - 1:
            new_root = BPlusTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split(new_root, 0)
            self.root = new_root

    def _insert(self, node, key, value):
        if node.leaf:
            i = 0
            while i < len(node.keys) and node.keys[i] < key:
                i += 1
            node.keys.insert(i, key)
            node.values.insert(i, value)
            if len(node.keys) >= self.order:
                self._split_leaf(node)
        else:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            self._insert(node.children[i], key, value)

    def range_query(self, start_key, end_key):
        node = self._find_leaf(self.root, start_key)
        result = []
        while node:
            for k, v in zip(node.keys, node.values):
                if start_key <= k <= end_key:
                    result.append((k, v))
                if k > end_key:
                    return result
            node = node.next
        return result

# 使用示例
tree = BPlusTree(order=4)
for i in range(1, 21):
    tree.insert(i, f"value_{i}")

print("Search key=10:", tree.search(10))
print("Range [5,15]:", tree.range_query(5, 15))

3.2 案例二：LSM 树模拟器

python

import os
import json
from sortedcontainers import SortedDict

class SimpleLSMTree:
    def __init__(self, memtable_size=100, data_dir="/tmp/lsm"):
        self.memtable = SortedDict()
        self.memtable_size = memtable_size
        self.sstables = []  # 磁盘上的 SSTable 列表
        self.data_dir = data_dir
        os.makedirs(data_dir, exist_ok=True)

    def put(self, key, value):
        self.memtable[key] = value
        if len(self.memtable) >= self.memtable_size:
            self._flush_memtable()

    def get(self, key):
        # 1. 先查 MemTable
        if key in self.memtable:
            val = self.memtable[key]
            return None if val == "__DELETED__" else val

        # 2. 再查 SSTable（从新到旧）
        for sst in reversed(self.sstables):
            if key in sst:
                val = sst[key]
                return None if val == "__DELETED__" else val
        return None

    def delete(self, key):
        self.put(key, "__DELETED__")

    def _flush_memtable(self):
        if not self.memtable:
            return
        sst_path = os.path.join(self.data_dir, f"sst_{len(self.sstables)}.json")
        with open(sst_path, 'w') as f:
            json.dump(dict(self.memtable), f)
        self.sstables.append(dict(self.memtable))
        self.memtable = SortedDict()

    def compact(self):
        if len(self.sstables) < 2:
            return
        merged = SortedDict()
        for sst in self.sstables:
            merged.update(sst)
        # 删除标记为删除的键
        merged = {k: v for k, v in merged.items() if v != "__DELETED__"}
        self.sstables = [dict(merged)]

# 使用示例
lsm = SimpleLSMTree(memtable_size=5)
lsm.put("alice", 25)
lsm.put("bob", 30)
lsm.put("charlie", 35)
print("Get alice:", lsm.get("alice"))  # 25
lsm.delete("bob")
print("Get bob:", lsm.get("bob"))      # None

四、本章小结

本章深入讲解了数据库存储引擎的两大核心数据结构：

B+ 树通过原地更新和页分裂管理数据，读性能稳定（O(log n)），适合读多写少的 OLTP 场景。树的高度通常为 3-4 层，每次查询需要 3-4 次 I/O。

LSM 树通过将随机写转换为顺序写（MemTable → SSTable → Compaction），实现了极高的写入吞吐，但读放大较大，需要 Bloom Filter 和 Compaction 策略来优化。

B+ 树 vs LSM 树的核心权衡是读放大 vs 写放大。B+ 树读放大低但写放大也低；LSM 树写放大高但写入吞吐也高。

Compaction 策略（Leveled vs Tiered）直接影响 LSM 树的读写放大和空间放大，需要根据工作负载选择。

Bloom Filter 是 LSM 树减少读放大的关键工具，以少量内存开销换取大量不必要的磁盘 I/O。

五、思考与练习

思考题

如果 InnoDB 的 B+ 树页大小从 16KB 改为 4KB，树的高度会增加多少？对查询性能有什么影响？

为什么 LSM 树的 MemTable 通常用跳表而不是数组实现？如果用数组实现会有什么问题？

Leveled Compaction 的写放大为什么比 Tiered Compaction 高？在什么场景下应该选择 Tiered Compaction？

Bloom Filter 的误判率与位数组大小、哈希函数数量之间有什么关系？如何计算最优参数？

编程练习

实现一个完整的 B+ 树，支持插入、删除、范围查询，并统计树的高度和每层的节点数。

实现一个 LSM 树模拟器，包含 MemTable、SSTable 刷写、Leveled Compaction 功能。

实现一个 Bloom Filter，测试不同参数下的误判率，并与理论值对比。