B-Tree、B+Tree 与 LSM-Tree
第二十章：B-Tree、B+Tree 与 LSM-Tree
打开 MySQL 客户端，执行 EXPLAIN SELECT * FROM users WHERE id = 42，你会在 type 列看到 const——这意味着 InnoDB 通过一次 B+Tree 查找就定位到了数据行。这个"一次查找"的背后，是一棵高度通常只有 3-4 层的多路搜索树，每个节点恰好占据一个 16KB 的磁盘页。
为什么不是二叉搜索树？为什么不是哈希表？为什么不是红黑树？这些问题的答案都指向同一个核心矛盾：内存访问速度与磁盘 I/O 速度之间存在 10 万倍的鸿沟。一次内存随机访问约 100ns，一次 SSD 随机读取约 100μs，一次机械硬盘随机寻道约 10ms。当数据量超过内存容量时，任何数据结构的设计都必须以"最小化磁盘 I/O 次数"为首要目标。
Rudolf Bayer 和 Edward McCreight 在 1972 年发明 B-Tree 时，正是瞄准了这个问题。他们的论文标题直白而精准：《Organization and Maintenance of Large Ordered Indexes》。B-Tree 通过增大每个节点的"宽度"（存储多个 key 和子指针），将树的高度压缩到 log_m(n) 级别（m 是节点的分支数，通常在数百到数千之间），从而将查找一条记录的磁盘 I/O 次数控制在 3-4 次。
而 B+Tree 是 B-Tree 的变体，所有数据只存储在叶子节点，叶子之间通过双向链表连接——这使得范围查询变得极其高效。MySQL InnoDB、PostgreSQL、Oracle 的索引结构都是 B+Tree。
但 B+Tree 并非万能。当写入负载远大于读取时（如日志系统、时序数据库），B+Tree 的随机写放大问题会成为瓶颈。Patrick O'Neil 在 1996 年提出的 LSM-Tree（Log-Structured Merge-Tree）通过"先写内存→批量刷盘→后台合并"的策略，将随机写变为顺序写，实现了写吞吐量的数量级提升。LevelDB、RocksDB、Cassandra、HBase 都基于 LSM-Tree。
这一章，我们从 B-Tree 的基本定义出发，深入 B+Tree 在数据库中的实际应用，再到 LSM-Tree 的写优化设计，最后讨论 Redis 为什么选择跳表而非 B+Tree。你将看到，数据结构的选择从来不是"谁更好"的问题，而是"在给定的硬件约束和访问模式下，谁的代价更低"。
Level 1 · 你需要知道的
20.1 B-Tree：多路搜索树
20.1.1 从二叉到多路
我们在前面的章节学过二叉搜索树（BST）和平衡二叉搜索树（AVL、红黑树）。它们的核心性质是：每个节点最多两个子节点，查找的时间复杂度为 O(log₂n)。
对于 100 万条记录，二叉树的高度约为 log₂(1,000,000) ≈ 20。如果树完全在内存中，20 次比较微不足道。但如果每个节点都在磁盘上，就意味着 20 次磁盘 I/O——以 HDD 10ms/次计算，一次查找就要 200ms，这是不可接受的。
解决方案是增加每个节点的"分支因子"（branching factor）。如果每个节点能存储 1000 个 key 和 1001 个子指针，那么同样 100 万条记录，树的高度只有 log₁₀₀₁(1,000,000) ≈ 2。加上根节点通常缓存在内存中，实际只需要 1-2 次磁盘 I/O 就能找到任何记录。
这就是 B-Tree 的核心思想：用节点宽度换取树的高度。
20.1.2 B-Tree 的正式定义
一棵 m 阶 B-Tree（m 是节点的最大子节点数）满足以下性质：
- 每个节点最多有 m 个子节点
- 非根节点最少有 ⌈m/2⌉ 个子节点（保证节点至少半满）
- 根节点至少有 2 个子节点（除非根节点是叶子）
- 有 k 个子节点的节点包含 k-1 个 key
- 所有叶子在同一层（完全平衡）
- 节点内的 key 有序排列
以 m=5 的 B-Tree 为例（也叫 2-3-4 树的泛化）：
- 每个节点最多 4 个 key，5 个子指针
- 非根节点最少 2 个 key，3 个子指针
class BTreeNode:
"""B-Tree 节点"""
def __init__(self, leaf=False):
self.keys = [] # 存储的 key 列表（有序）
self.children = [] # 子节点指针列表
self.leaf = leaf # 是否叶子节点
class BTree:
"""B-Tree 实现（m 阶）"""
def __init__(self, m):
self.root = BTreeNode(leaf=True)
self.m = m # 最大子节点数
self.max_keys = m - 1 # 每个节点最大 key 数
self.min_keys = (m + 1) // 2 - 1 # 非根节点最小 key 数
def search(self, node, key):
"""在 B-Tree 中查找 key"""
i = 0
# 在当前节点中找到 key 应该在的位置
while i < len(node.keys) and key > node.keys[i]:
i += 1
# 找到了
if i < len(node.keys) and key == node.keys[i]:
return (node, i)
# 没找到且是叶子节点
if node.leaf:
return None
# 递归到子节点（这一步对应一次磁盘 I/O）
return self.search(node.children[i], key)
def insert(self, key):
"""插入 key"""
root = self.root
# 如果根节点满了，需要先分裂
if len(root.keys) == self.max_keys:
new_root = BTreeNode(leaf=False)
new_root.children.append(self.root)
self._split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _insert_non_full(self, node, key):
"""在未满的节点中插入"""
i = len(node.keys) - 1
if node.leaf:
# 叶子节点直接插入
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
# 找到应该插入的子节点
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
# 如果子节点满了，先分裂
if len(node.children[i].keys) == self.max_keys:
self._split_child(node, i)
if key > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], key)
def _split_child(self, parent, idx):
"""分裂 parent 的第 idx 个子节点"""
m = self.m
child = parent.children[idx]
mid = len(child.keys) // 2
# 创建新节点，存放右半部分
new_node = BTreeNode(leaf=child.leaf)
new_node.keys = child.keys[mid + 1:]
if not child.leaf:
new_node.children = child.children[mid + 1:]
child.children = child.children[:mid + 1]
# 中间的 key 提升到父节点
promote_key = child.keys[mid]
child.keys = child.keys[:mid]
# 在父节点中插入提升的 key 和新子节点
parent.keys.insert(idx, promote_key)
parent.children.insert(idx + 1, new_node)
20.1.3 B-Tree 查找过程可视化
假设一棵 5 阶 B-Tree 存储了 key [1, 2, ..., 20]，结构可能如下：
[8]
/ \
[3, 5] [12, 15, 18]
/ | \ / | | \
[1,2] [4] [6,7] [9,10,11] [13,14] [16,17] [19,20]
查找 key=14 的过程：
- 根节点 [8]：14 > 8，走右子节点（1 次磁盘 I/O）
- 内部节点 [12, 15, 18]：12 < 14 < 15，走第二个子指针（1 次磁盘 I/O）
- 叶子节点 [13, 14]：找到 14（1 次磁盘 I/O）
总共 3 次磁盘 I/O。
20.1.4 为什么不用红黑树或哈希表？
这是面试中的经典问题。让我们从根本上分析：
| 数据结构 | 查找 I/O | 范围查询 | 有序性 | 磁盘友好 |
|---|---|---|---|---|
| 红黑树 | O(log₂n) ≈ 20 | 需要中序遍历 | 有序 | 差（节点分散） |
| 哈希表 | O(1) 平均 | 不支持 | 无序 | 差（扩容代价大） |
| B+Tree | O(log_m n) ≈ 3 | 叶子链表顺序扫描 | 有序 | 极好（节点=页） |
红黑树的问题：
- 高度太高：100 万条记录需要 ~20 层，意味着 ~20 次磁盘 I/O
- 节点太小：每个节点只存一个 key，无法有效利用磁盘页的 4KB/16KB 空间
- 节点分散：相邻 key 的节点可能在磁盘上完全不连续，无法利用预读
哈希表的问题：
- 不支持范围查询：
WHERE age BETWEEN 20 AND 30需要全表扫描 - 不支持排序：
ORDER BY需要额外排序步骤 - 扩容代价大：rehash 需要重新分布所有数据
- 哈希冲突不可控：最坏情况退化为 O(n)
B+Tree 为什么赢了：
- 树高极低：即使 10 亿条记录，4 层足够（假设每页能放 1000 个 key）
- 节点大小=磁盘页大小：一次 I/O 读取一个完整节点
- 顺序访问优秀：叶子链表使范围查询只需顺序读取
- 预读友好：操作系统的 readahead 机制可以预加载相邻页
20.2 B+Tree：数据库索引的基石
20.2.1 B+Tree 与 B-Tree 的关键区别
B+Tree 是 B-Tree 的变体，有两个关键改进：
- 所有数据只存在叶子节点：内部节点只存 key（作为路标/索引），不存数据
- 叶子节点通过指针连成双向链表：支持高效的范围扫描
这两个改进带来了巨大的实际优势：
B-Tree（数据分布在所有节点）：
[10|data, 20|data]
/ | \
[5|data] [15|data] [25|data, 30|data]
B+Tree（数据只在叶子）：
[10, 20] ← 内部节点：只有 key，无数据
/ | \
[5|d]→[10|d, 15|d]→[20|d, 25|d, 30|d] ← 叶子：有数据 + 链表
为什么"数据只存叶子"更好？
内部节点不存数据意味着：
- 内部节点能容纳更多 key → 分支因子更大 → 树更矮
- 假设一个 16KB 页面，key 占 8 字节，指针占 6 字节：
- B-Tree 内部节点：如果每条数据 100 字节，一页只能放 ~145 个 key
- B+Tree 内部节点：没有数据开销，一页能放 ~1170 个 key
- B+Tree 的分支因子是 B-Tree 的 8 倍，这意味着树高降低至少一层
为什么"叶子链表"很重要？
# 范围查询：SELECT * FROM users WHERE age BETWEEN 20 AND 30
# B+Tree：先定位到 age=20 的叶子，然后沿链表顺序扫描到 age>30 为止
# B-Tree：需要中序遍历，可能在不同层级间反复跳转
def range_query_bplus(root, low, high):
"""B+Tree 范围查询"""
# 第一步：定位到起始叶子（O(log n) 次 I/O）
leaf = find_leaf(root, low)
results = []
# 第二步：沿叶子链表顺序扫描（顺序 I/O，极快）
while leaf is not None:
for key, data in leaf.entries:
if key > high:
return results
if key >= low:
results.append(data)
leaf = leaf.next_leaf # 链表指针，下一个叶子页
return results
20.2.2 B+Tree 查找的完整过程
让我们用一个具体例子模拟 InnoDB 的 B+Tree 查找。假设：
- 页大小 16KB
- 主键为 bigint（8 字节），每行数据 200 字节
- 内部节点：每个 key 8 字节 + 指针 6 字节 = 14 字节，一页约 1170 个指针
- 叶子节点：每行 200 字节，一页约 80 行
则：
- 2 层 B+Tree：1170 × 80 = 93,600 行
- 3 层 B+Tree：1170 × 1170 × 80 = 1.09 亿行
- 4 层 B+Tree：1170³ × 80 = 1281 亿行
也就是说，对于绝大多数业务表（< 1 亿行），3 次磁盘 I/O 就能定位到任何一行数据。加上根节点和第二层通常缓存在 Buffer Pool 中，实际可能只需要 1 次磁盘 I/O。
class BPlusTreeNode:
"""B+Tree 节点"""
def __init__(self, leaf=False):
self.keys = []
self.leaf = leaf
if leaf:
self.data = [] # 叶子节点存数据
self.next_leaf = None # 指向下一个叶子
self.prev_leaf = None # 指向上一个叶子
else:
self.children = [] # 内部节点存子指针
class BPlusTree:
"""简化的 B+Tree 实现"""
def __init__(self, order):
self.root = BPlusTreeNode(leaf=True)
self.order = order # 每个节点最大 key 数
def search(self, key):
"""精确查找"""
node = self.root
while not node.leaf:
# 在内部节点中二分查找定位子节点
i = self._find_position(node.keys, key)
node = node.children[i]
# 在叶子节点中查找
i = self._find_position(node.keys, key)
if i < len(node.keys) and node.keys[i] == key:
return node.data[i]
return None
def range_search(self, low, high):
"""范围查找"""
# 定位到起始叶子
node = self.root
while not node.leaf:
i = self._find_position(node.keys, low)
node = node.children[i]
# 沿叶子链表扫描
results = []
while node is not None:
for i, key in enumerate(node.keys):
if key > high:
return results
if key >= low:
results.append((key, node.data[i]))
node = node.next_leaf
return results
def insert(self, key, data):
"""插入 key-data 对"""
# 找到应该插入的叶子
node = self.root
path = [] # 记录路径，用于分裂时向上传播
while not node.leaf:
i = self._find_position(node.keys, key)
path.append((node, i))
node = node.children[i]
# 在叶子中插入
i = self._find_position(node.keys, key)
node.keys.insert(i, key)
node.data.insert(i, data)
# 如果叶子溢出，分裂
if len(node.keys) > self.order:
self._split_leaf(node, path)
def _split_leaf(self, leaf, path):
"""分裂叶子节点"""
mid = len(leaf.keys) // 2
new_leaf = BPlusTreeNode(leaf=True)
# 右半部分移到新叶子
new_leaf.keys = leaf.keys[mid:]
new_leaf.data = leaf.data[mid:]
leaf.keys = leaf.keys[:mid]
leaf.data = leaf.data[:mid]
# 维护叶子链表
new_leaf.next_leaf = leaf.next_leaf
if leaf.next_leaf:
leaf.next_leaf.prev_leaf = new_leaf
leaf.next_leaf = new_leaf
new_leaf.prev_leaf = leaf
# 将新叶子的第一个 key 提升到父节点
promote_key = new_leaf.keys[0]
self._insert_into_parent(leaf, promote_key, new_leaf, path)
def _insert_into_parent(self, left, key, right, path):
"""将 key 插入父节点"""
if not path:
# 需要创建新根
new_root = BPlusTreeNode(leaf=False)
new_root.keys = [key]
new_root.children = [left, right]
self.root = new_root
return
parent, idx = path.pop()
parent.keys.insert(idx, key)
parent.children.insert(idx + 1, right)
if len(parent.keys) > self.order:
self._split_internal(parent, path)
def _split_internal(self, node, path):
"""分裂内部节点"""
mid = len(node.keys) // 2
promote_key = node.keys[mid]
new_node = BPlusTreeNode(leaf=False)
new_node.keys = node.keys[mid + 1:]
new_node.children = node.children[mid + 1:]
node.keys = node.keys[:mid]
node.children = node.children[:mid + 1]
self._insert_into_parent(node, promote_key, new_node, path)
def _find_position(self, keys, target):
"""二分查找定位"""
lo, hi = 0, len(keys)
while lo < hi:
mid = (lo + hi) // 2
if keys[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
20.2.3 插入和分裂
B+Tree 的插入操作遵循"自底向上分裂"的策略：
- 定位叶子：沿根到叶的路径找到 key 应该插入的叶子节点
- 插入叶子：将 key-data 对插入叶子节点的正确位置
- 检查溢出：如果叶子节点的 key 数超过 order，执行分裂
- 分裂传播：分裂可能向上传播到父节点，最坏情况一直传播到根
分裂的关键规则：
- 叶子分裂：中间 key 复制一份提升到父节点（因为数据还要留在叶子）
- 内部节点分裂：中间 key 移动到父节点（内部节点不存数据）
这个区别很重要，确保所有数据都能在叶子节点中找到。
20.2.4 删除和合并
删除操作是插入的逆过程：
- 定位并删除：在叶子中删除目标 key
- 检查下溢：如果节点的 key 数低于 ⌈order/2⌉，需要处理
- 尝试借位：从兄弟节点借一个 key（旋转）
- 合并节点：如果兄弟也很少，两个节点合并为一个
def delete(self, key):
"""从 B+Tree 中删除 key（简化版）"""
# 找到叶子节点
leaf = self._find_leaf(key)
if key not in leaf.keys:
return False
idx = leaf.keys.index(key)
leaf.keys.pop(idx)
leaf.data.pop(idx)
# 检查是否下溢（key 数 < 最小要求）
min_keys = self.order // 2
if len(leaf.keys) < min_keys and leaf != self.root:
self._handle_underflow(leaf)
return True
20.3 B+Tree 与磁盘 I/O 的深度关系
20.3.1 磁盘访问的代价模型
理解 B+Tree 为什么高效，必须理解磁盘 I/O 的代价：
存储层次结构（2024 年典型数值）：
┌─────────────────────────┬──────────┬───────────┐
│ 存储介质 │ 延迟 │ 带宽 │
├─────────────────────────┼──────────┼───────────┤
│ L1 Cache │ 1ns │ 1TB/s │
│ L2 Cache │ 4ns │ 500GB/s │
│ L3 Cache │ 12ns │ 200GB/s │
│ DRAM │ 100ns │ 50GB/s │
│ NVMe SSD（随机 4KB） │ 100μs │ 7GB/s │
│ SATA SSD（随机 4KB） │ 200μs │ 500MB/s │
│ HDD（随机 4KB） │ 10ms │ 200MB/s │
└─────────────────────────┴──────────┴───────────┘
关键洞察：
- DRAM → SSD 的延迟跳跃是 1000 倍
- DRAM → HDD 的延迟跳跃是 100,000 倍
- 但顺序读取时，SSD 和 HDD 的带宽差距只有 10-35 倍
这就解释了两个设计原则：
- 减少随机 I/O 次数（B+Tree 的矮树高）
- 把随机 I/O 转为顺序 I/O（叶子链表、LSM-Tree）
20.3.2 节点大小为什么等于页大小
操作系统以"页"（page）为单位进行磁盘读写，Linux 默认 4KB，数据库通常使用 16KB（InnoDB）或 8KB（PostgreSQL）。
B+Tree 的节点大小设定为等于磁盘页大小，原因是：
- 读一个节点 = 一次 I/O：不管节点中有多少 key，开销都是一次磁盘读取
- 充分利用每次 I/O：一次读取 16KB，如果节点只有几十字节就浪费了
- 对齐文件系统：避免一个节点跨两个页导致两次 I/O
# InnoDB 页大小计算
PAGE_SIZE = 16 * 1024 # 16KB
# 内部节点（非叶子）的扇出计算
key_size = 8 # bigint 主键
pointer_size = 6 # InnoDB 使用 6 字节页号
header_overhead = 120 # 页头、页尾等固定开销
usable_space = PAGE_SIZE - header_overhead
keys_per_page = usable_space // (key_size + pointer_size)
# 约 1170 个 key，即扇出（fan-out）约 1170
# 叶子节点的记录数计算
row_size = 200 # 假设平均行大小 200 字节
rows_per_leaf = usable_space // row_size
# 约 80 行
# 树高与容量的关系
def capacity(height, fan_out, rows_per_leaf):
"""计算给定高度的 B+Tree 能存储的最大行数"""
return (fan_out ** (height - 1)) * rows_per_leaf
print(f"2 层: {capacity(2, 1170, 80):,} 行") # 93,600
print(f"3 层: {capacity(3, 1170, 80):,} 行") # 109,512,000
print(f"4 层: {capacity(4, 1170, 80):,} 行") # 128,129,040,000
20.4 常见误区
误区 1："B-Tree 的 B 代表 Binary"
错误。B-Tree 的 B 最常被解释为"Balanced"或"Boeing"（Bayer 和 McCreight 当时在波音公司工作），或者是 Bayer 的首字母。Bayer 本人从未给出官方解释。
误区 2："红黑树比 B-Tree 差"
这个说法脱离了语境。红黑树在纯内存场景下比 B-Tree 更优——因为每次比较只涉及一个 key，cache line 利用率更高。Linux 内核的进程调度、Java 的 TreeMap 都用红黑树。B-Tree/B+Tree 的优势是在磁盘/大数据量场景。
误区 3："哈希索引完全没用"
MySQL 的 MEMORY 引擎和 InnoDB 的自适应哈希索引（Adaptive Hash Index）都使用哈希。对于等值查询（WHERE id = 42），哈希索引 O(1) 确实比 B+Tree O(log n) 快。但哈希不支持范围查询和排序，所以不能作为通用索引结构。
Level 2 · 它是怎么运行的
20.5 B+Tree 在 MySQL InnoDB 中的应用
20.5.1 聚簇索引 vs 二级索引
InnoDB 使用 B+Tree 组织数据，但有两种不同的索引类型：
聚簇索引（Clustered Index）：
- 每张 InnoDB 表有且只有一个聚簇索引
- 叶子节点存储完整的行数据
- 默认使用主键；如果没有显式主键，InnoDB 会选择一个唯一非空索引或生成隐藏的 ROW_ID
- 数据的物理存储顺序就是主键的逻辑顺序
二级索引（Secondary Index）：
- 一张表可以有多个二级索引
- 叶子节点存储的是索引列的值 + 主键值（不存完整行数据）
- 通过二级索引查找时，需要"回表"（用主键值再去聚簇索引查一次）
聚簇索引结构（主键 id）：
Root: [50, 100]
↓ (id < 50)
Leaf: [id=1, name="Alice", age=25] → [id=2, name="Bob", age=30] → ...
二级索引结构（索引列 name）：
Root: ["John", "Mike"]
↓ (name < "John")
Leaf: [name="Alice", id=1] → [name="Bob", id=2] → ...
↑ 只存主键，需要回表
回表的代价：
# 假设执行：SELECT * FROM users WHERE name = 'Alice'
# 如果 name 上有二级索引：
# 步骤 1：在二级索引 B+Tree 中查找 name='Alice'
# → 得到主键 id=1（约 2-3 次 I/O）
# 步骤 2：用 id=1 去聚簇索引 B+Tree 中查找完整行
# → 得到完整数据（约 1-2 次 I/O，因为聚簇索引根节点通常在内存中）
# 总共：3-5 次 I/O
# 如果是覆盖索引（索引包含了所有需要的列）：
# SELECT id, name FROM users WHERE name = 'Alice'
# 二级索引的叶子节点已经有 (name, id)，不需要回表
# 总共：2-3 次 I/O
20.5.2 索引覆盖与联合索引
覆盖索引（Covering Index）是指查询所需的所有列都在索引中，不需要回表：
-- 创建联合索引
CREATE INDEX idx_name_age ON users(name, age);
-- 以下查询可以走覆盖索引（Extra: Using index）
SELECT name, age FROM users WHERE name = 'Alice';
-- 以下查询需要回表（需要 email 列，不在索引中）
SELECT name, age, email FROM users WHERE name = 'Alice';
联合索引的 B+Tree 结构遵循最左前缀原则：
联合索引 (name, age) 的 B+Tree：
叶子节点按 (name, age) 排序：
[("Alice", 25, id=1)] → [("Alice", 30, id=5)] → [("Bob", 20, id=3)] → ...
可以使用索引的查询：
✓ WHERE name = 'Alice' （最左前缀）
✓ WHERE name = 'Alice' AND age = 25 （完整前缀）
✓ WHERE name = 'Alice' AND age > 20 （前缀 + 范围）
✓ ORDER BY name, age （索引顺序）
不能使用索引的查询：
✗ WHERE age = 25 （跳过了 name）
✗ ORDER BY age, name （顺序不对）
20.5.3 InnoDB 页的物理结构
一个 InnoDB 页（16KB）的内部结构：
┌──────────────────────────────────────────────┐
│ File Header (38 bytes) │ ← 页号、校验和、前后页指针
├──────────────────────────────────────────────┤
│ Page Header (56 bytes) │ ← 记录数、空闲空间指针
├──────────────────────────────────────────────┤
│ Infimum & Supremum Records (26 bytes) │ ← 虚拟最小/最大记录
├──────────────────────────────────────────────┤
│ User Records │ ← 实际数据行（单链表）
│ ┌─────────────────────────────────────────┐ │
│ │ Record 1 → Record 2 → Record 3 → ... │ │
│ └─────────────────────────────────────────┘ │
├──────────────────────────────────────────────┤
│ Free Space │ ← 未使用空间
├──────────────────────────────────────────────┤
│ Page Directory (variable) │ ← 稀疏目录，加速页内查找
├──────────────────────────────────────────────┤
│ File Trailer (8 bytes) │ ← 校验和（与 Header 一致性检查）
└──────────────────────────────────────────────┘
页内查找使用 Page Directory（稀疏索引），将记录分组，每组 4-8 条记录。查找时先在 Page Directory 中二分查找定位到组，再在组内顺序扫描。这是"索引之上还有索引"的分层设计思想。
20.6 LSM-Tree：写优化的数据结构
20.6.1 B+Tree 的写放大问题
B+Tree 对读优化做到了极致，但写入有一个致命问题——写放大（Write Amplification）：
- 修改一行数据，需要：
- 从磁盘读取包含该行的 16KB 页
- 修改其中的几十字节
- 把整个 16KB 页写回磁盘
- 如果涉及节点分裂，还需要写多个页
- 加上 WAL（Write-Ahead Log），一次修改的实际写入量可能是原始数据的 10-30 倍
当写入负载占主导时（如日志收集、IoT 传感器数据、时序数据库），B+Tree 的写放大会严重限制吞吐量。
20.6.2 LSM-Tree 的核心思想
Patrick O'Neil 在 1996 年的论文《The Log-Structured Merge-Tree (LSM-Tree)》中提出了一个关键洞察：
如果磁盘的顺序写比随机写快 100 倍，那么把所有写入都变成顺序写就好了。
LSM-Tree 的写入路径：
写入请求 → MemTable（内存有序结构）→ 满了 → 刷盘为 SSTable（磁盘有序文件）
↓
后台 Compaction（合并多个 SSTable）
具体步骤：
- 写入 MemTable：新数据先写入内存中的有序数据结构（通常是红黑树或跳表），同时写 WAL 保证持久性
- MemTable 转 Immutable：当 MemTable 达到阈值（如 64MB），冻结为 Immutable MemTable
- Flush 为 SSTable：Immutable MemTable 顺序写入磁盘，生成一个 SSTable（Sorted String Table）文件
- Compaction：后台线程定期合并多个 SSTable，消除重复 key，释放空间
import bisect
import time
import os
class MemTable:
"""内存中的有序表（简化为 sorted list 实现）"""
def __init__(self, max_size=1000):
self.entries = [] # [(key, value, timestamp)]
self.max_size = max_size
self.size = 0
def put(self, key, value):
"""写入/更新"""
entry = (key, value, time.time())
# 二分查找插入位置
idx = bisect.bisect_left(self.entries, (key,))
if idx < len(self.entries) and self.entries[idx][0] == key:
self.entries[idx] = entry # 更新
else:
self.entries.insert(idx, entry)
self.size += 1
def get(self, key):
"""查找"""
idx = bisect.bisect_left(self.entries, (key,))
if idx < len(self.entries) and self.entries[idx][0] == key:
return self.entries[idx][1]
return None
def is_full(self):
return self.size >= self.max_size
def flush_to_sstable(self, filename):
"""顺序写入磁盘，生成 SSTable"""
with open(filename, 'w') as f:
for key, value, ts in self.entries:
f.write(f"{key}\t{value}\t{ts}\n")
return SSTable(filename)
class SSTable:
"""磁盘上的有序文件（简化版）"""
def __init__(self, filename):
self.filename = filename
self.index = self._build_sparse_index()
def _build_sparse_index(self):
"""构建稀疏索引（每隔 N 条记录记一个位置）"""
index = {}
with open(self.filename, 'r') as f:
offset = 0
for line in f:
key = line.split('\t')[0]
if len(index) == 0 or hash(key) % 16 == 0:
index[key] = offset
offset += len(line)
return index
def get(self, key):
"""在 SSTable 中查找（需要 I/O）"""
with open(self.filename, 'r') as f:
for line in f:
parts = line.strip().split('\t')
if parts[0] == key:
return parts[1]
if parts[0] > key:
break
return None
class LSMTree:
"""简化的 LSM-Tree 实现"""
def __init__(self, data_dir="lsm_data"):
self.memtable = MemTable()
self.immutable_memtables = [] # 等待 flush 的 MemTable
self.sstables = [] # 磁盘上的 SSTable 列表（新→旧）
self.data_dir = data_dir
self.sstable_counter = 0
def put(self, key, value):
"""写入"""
self.memtable.put(key, value)
if self.memtable.is_full():
self._flush()
def get(self, key):
"""读取：先查内存，再查磁盘"""
# 1. 先查当前 MemTable
result = self.memtable.get(key)
if result is not None:
return result
# 2. 再查 Immutable MemTables（从新到旧）
for imm in reversed(self.immutable_memtables):
result = imm.get(key)
if result is not None:
return result
# 3. 最后查 SSTables（从新到旧）
for sst in self.sstables:
result = sst.get(key)
if result is not None:
return result
return None # key 不存在
def _flush(self):
"""将 MemTable 刷盘为 SSTable"""
self.immutable_memtables.append(self.memtable)
self.memtable = MemTable()
# 模拟后台 flush
imm = self.immutable_memtables.pop(0)
filename = f"{self.data_dir}/sst_{self.sstable_counter:06d}.dat"
self.sstable_counter += 1
sst = imm.flush_to_sstable(filename)
self.sstables.insert(0, sst) # 新的在前面
def compact(self):
"""合并 SSTable（简化版 Level Compaction）"""
if len(self.sstables) < 4:
return
# 合并最旧的两个 SSTable
sst1 = self.sstables.pop()
sst2 = self.sstables.pop()
# 归并排序两个有序文件
merged = self._merge_sstables(sst1, sst2)
self.sstables.append(merged)
def _merge_sstables(self, sst1, sst2):
"""归并两个 SSTable"""
filename = f"{self.data_dir}/sst_{self.sstable_counter:06d}.dat"
self.sstable_counter += 1
entries = {}
# 读取两个文件，后写入的（sst1 更新）覆盖先写入的
for sst in [sst2, sst1]:
with open(sst.filename, 'r') as f:
for line in f:
parts = line.strip().split('\t')
entries[parts[0]] = (parts[1], parts[2])
# 按 key 排序写入新文件
with open(filename, 'w') as f:
for key in sorted(entries.keys()):
value, ts = entries[key]
f.write(f"{key}\t{value}\t{ts}\n")
# 删除旧文件
os.remove(sst1.filename)
os.remove(sst2.filename)
return SSTable(filename)
20.6.3 LevelDB / RocksDB 的分层 Compaction
Google 的 LevelDB（Jeff Dean 和 Sanjay Ghemawat 设计）将 SSTable 组织为多个层级：
Level 0: SSTable_a, SSTable_b, SSTable_c ← 直接从 MemTable flush
(key 范围可能重叠)
Level 1: SSTable_1, SSTable_2, SSTable_3 ← 每层内 key 范围不重叠
[0-100] [101-200] [201-300]
Level 2: SSTable_A, SSTable_B, ..., SSTable_F
[0-50] [51-100] ... [251-300]
Level 3: ...（每层容量是上一层的 10 倍）
Level Compaction 规则：
- Level 0 的文件 key 范围可以重叠（因为直接 flush）
- Level 1+ 的文件 key 范围互不重叠
- 当某层的文件总大小超过阈值，选取一个文件与下一层重叠的文件合并
- Level 0 → Level 1 → Level 2 → ...，每层容量增大 10 倍
为什么分层？
假设总数据量 10GB：
- 不分层：每次 compaction 可能需要合并所有 10GB，代价巨大
- 分层：Level 1 限 10MB，Level 2 限 100MB，Level 3 限 1GB...
- 每次 compaction 只涉及相邻两层的少量文件
- 单次 compaction 的 I/O 量可控
读放大 vs 写放大的权衡：
LSM-Tree 的代价模型：
┌────────────┬──────────────────────────────────────────┐
│ 操作 │ 代价 │
├────────────┼──────────────────────────────────────────┤
│ 写入 │ O(1) 内存写 + O(1) WAL 顺序写 │
│ │ 写放大 ≈ 10-30 倍（Compaction 的代价） │
├────────────┼──────────────────────────────────────────┤
│ 点查询 │ 最坏需要查每一层：O(层数) │
│ │ 优化：Bloom Filter 跳过不包含目标 key 的文件 │
├────────────┼──────────────────────────────────────────┤
│ 范围查询 │ 需要归并多层的结果：O(层数 × log(文件数)) │
└────────────┴──────────────────────────────────────────┘
B+Tree 的代价模型：
┌────────────┬──────────────────────────────────────────┐
│ 操作 │ 代价 │
├────────────┼──────────────────────────────────────────┤
│ 写入 │ O(log n) 次随机 I/O + WAL │
│ │ 写放大 ≈ 10-30 倍（页粒度写） │
├────────────┼──────────────────────────────────────────┤
│ 点查询 │ O(log n) ≈ 2-4 次 I/O │
├────────────┼──────────────────────────────────────────┤
│ 范围查询 │ 定位 + 顺序扫描叶子链表 │
└────────────┴──────────────────────────────────────────┘
20.6.4 Bloom Filter 优化读取
LSM-Tree 的读取劣势是需要逐层查找。Bloom Filter 可以快速判断"某个 key 一定不在这个 SSTable 中"，从而跳过大量无用的磁盘读取。
import mmh3 # MurmurHash3
class BloomFilter:
"""布隆过滤器"""
def __init__(self, expected_items, false_positive_rate=0.01):
# 计算最优参数
import math
self.size = int(-expected_items * math.log(false_positive_rate)
/ (math.log(2) ** 2))
self.num_hashes = int((self.size / expected_items) * math.log(2))
self.bit_array = [0] * self.size
def add(self, key):
"""添加 key"""
for i in range(self.num_hashes):
idx = mmh3.hash(key, i) % self.size
self.bit_array[idx] = 1
def might_contain(self, key):
"""查询（可能有假阳性，但绝无假阴性）"""
for i in range(self.num_hashes):
idx = mmh3.hash(key, i) % self.size
if self.bit_array[idx] == 0:
return False # 一定不存在
return True # 可能存在
# 在 LSM-Tree 中使用 Bloom Filter
class SSTableWithBloom(SSTable):
def __init__(self, filename, bloom_filter):
super().__init__(filename)
self.bloom = bloom_filter
def get(self, key):
# 先问 Bloom Filter
if not self.bloom.might_contain(key):
return None # 跳过磁盘 I/O
# Bloom Filter 说"可能存在"，再去磁盘确认
return super().get(key)
RocksDB 的每个 SSTable 都带有 Bloom Filter，默认 10 bits/key，假阳性率约 1%。这意味着 99% 的不命中查询可以零磁盘 I/O完成。
20.7 Redis 跳表：为什么不用 B+Tree
Redis 的有序集合（Sorted Set / ZSET）使用跳表（Skip List）而非 B+Tree。Antirez（Redis 作者 Salvatore Sanfilippo）本人给出的解释是：
- 纯内存操作：Redis 所有数据在内存中，不需要考虑磁盘 I/O，B+Tree 的优势消失
- 实现简单：跳表的代码量约为 B+Tree 的 1/3，更容易维护和调试
- 范围查询高效：跳表的前向指针天然支持范围扫描
- 并发友好：跳表可以通过局部锁实现高并发，B+Tree 的节点分裂需要锁整条路径
- 内存连续性：跳表的节点可以分散分配，不需要预分配大块连续内存
import random
class SkipListNode:
"""跳表节点"""
def __init__(self, key, value, level):
self.key = key
self.value = value
# forward[i] 是第 i 层的下一个节点
self.forward = [None] * (level + 1)
# span[i] 是第 i 层跨越的节点数（用于 ZRANK）
self.span = [0] * (level + 1)
class SkipList:
"""跳表实现（模仿 Redis ZSET）"""
MAX_LEVEL = 32
P = 0.25 # Redis 使用 1/4 的晋升概率
def __init__(self):
self.header = SkipListNode(None, None, self.MAX_LEVEL)
self.level = 0
self.length = 0
def _random_level(self):
"""随机决定新节点的层数"""
level = 0
while random.random() < self.P and level < self.MAX_LEVEL:
level += 1
return level
def insert(self, key, value):
"""插入元素"""
update = [None] * (self.MAX_LEVEL + 1)
current = self.header
# 从最高层向下查找插入位置
for i in range(self.level, -1, -1):
while (current.forward[i] is not None and
current.forward[i].key < key):
current = current.forward[i]
update[i] = current
# 随机层数
new_level = self._random_level()
if new_level > self.level:
for i in range(self.level + 1, new_level + 1):
update[i] = self.header
self.level = new_level
# 创建新节点并插入各层
new_node = SkipListNode(key, value, new_level)
for i in range(new_level + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
self.length += 1
def search(self, key):
"""查找"""
current = self.header
for i in range(self.level, -1, -1):
while (current.forward[i] is not None and
current.forward[i].key < key):
current = current.forward[i]
current = current.forward[0]
if current is not None and current.key == key:
return current.value
return None
def range_by_score(self, min_score, max_score):
"""范围查询（模拟 ZRANGEBYSCORE）"""
current = self.header
# 先定位到 >= min_score 的第一个节点
for i in range(self.level, -1, -1):
while (current.forward[i] is not None and
current.forward[i].key < min_score):
current = current.forward[i]
current = current.forward[0]
# 沿底层链表顺序扫描
results = []
while current is not None and current.key <= max_score:
results.append((current.key, current.value))
current = current.forward[0]
return results
跳表 vs B+Tree 对比总结：
| 特性 | 跳表 | B+Tree |
|---|---|---|
| 最佳场景 | 纯内存 | 磁盘存储 |
| 实现复杂度 | 低 | 高 |
| 查找时间 | O(log n) 期望 | O(log_m n) 确定 |
| 范围查询 | 底层链表 | 叶子链表 |
| 空间开销 | 每个节点平均 1.33 个指针（P=0.25） | 节点半满保证 |
| 并发性 | 无锁/局部锁 | 需要 latch coupling |
| 磁盘 I/O | 差（节点分散） | 极好（节点=页） |
Level 3 · 规范怎么定义的
20.8 B-Tree 的历史与设计决策
20.8.1 Bayer & McCreight 1972
Rudolf Bayer 和 Edward McCreight 在 1972 年发表了《Organization and Maintenance of Large Ordered Indexes》（发表于 Acta Informatica 期刊），首次提出 B-Tree。他们当时在波音科学研究实验室（Boeing Scientific Research Labs）工作。
论文的核心贡献：
- 定义了 B-Tree 的结构和性质
- 证明了所有操作（查找、插入、删除）的时间复杂度为 O(log n)
- 分析了磁盘 I/O 次数的上界
- 提出了节点分裂和合并的算法
为什么叫"B"-Tree？Bayer 从未给出明确解释。常见说法包括 Boeing、Balanced、Bayer、Broad 等。Douglas Comer 在 1979 年的综述论文《The Ubiquitous B-Tree》中写道："The origin of 'B-tree' has never been explained by the authors."
历史背景： 1972 年的存储技术是磁鼓（drum）和磁盘（disk），访问时间在毫秒级。当时的主存（core memory）容量以 KB 计。Bayer 和 McCreight 设计 B-Tree 时的核心约束是：如何在极慢的外存上维护大型有序索引？这个问题在 50 年后依然相关——虽然 SSD 比 HDD 快 100 倍，但与 DRAM 相比仍然慢 1000 倍。
20.8.2 B+Tree 的演化
B+Tree 并没有单一的"发明者"论文。它是 B-Tree 在数据库系统中的实践演化：
- 1973 年：Knuth 在《The Art of Computer Programming》Vol. 3 中讨论了 B-Tree 变体
- 1977 年：IBM 的 System R 项目（SQL 的起源）使用了类似 B+Tree 的结构
- 1979 年：Douglas Comer 的综述论文系统总结了各种 B-Tree 变体，包括 B+Tree
B+Tree 相对于 B-Tree 的两个关键设计决策都有深刻的理由：
决策 1：数据只存叶子
- 理由：内部节点不存数据→更小→同一页能放更多 key→扇出更大→树更矮→I/O 更少
- 代价：等值查找一定要走到叶子（B-Tree 可能在内部节点就找到）
- 权衡：对于数据库场景，减少一层的好处远大于偶尔少一次 I/O
决策 2：叶子串联链表
- 理由：范围查询只需"定位+顺序扫描"，不需要回溯到父节点
- 代价：额外的指针空间（通常可忽略）
- 实现：现代实现通常使用双向链表，支持正序和逆序扫描
20.8.3 O'Neil 1996 LSM-Tree 论文
Patrick O'Neil、Edward Cheng、Dieter Gawlick、Elizabeth O'Neil 在 1996 年发表了《The Log-Structured Merge-Tree (LSM-Tree)》（发表于 Acta Informatica）。
论文的核心论点：
- 对于写密集型工作负载，B-Tree 的随机写入效率极低
- 通过将所有写入转为顺序写（先写内存，再批量刷盘），可以大幅提升写吞吐
- 用读取的些许退化（需要查多个组件）换取写入的数量级提升
O'Neil 提出的原始 LSM-Tree 只有两个组件（C₀ 在内存，C₁ 在磁盘）。后来 Google 的 BigTable 论文（2006）将 LSM-Tree 推广为多层结构，LevelDB 和 RocksDB 进一步完善了分层 Compaction 策略。
LSM-Tree 的理论分析：
假设：
- B = 磁盘块大小
- M = 内存中 C₀ 的大小
- 磁盘顺序写带宽为 W_seq
- 磁盘随机写延迟为 T_rand
B+Tree 的写吞吐：W_btree = 1 / T_rand（每次写入一次随机 I/O）
LSM-Tree 的写吞吐：W_lsm ≈ W_seq / (write_amplification)
当 W_seq >> 1/T_rand 时（这在 HDD 上总是成立），LSM-Tree 的写吞吐远高于 B+Tree。在 SSD 上，顺序写/随机写的差距缩小了，但 LSM-Tree 的写放大会消耗 SSD 的擦写寿命（P/E cycles），这是一个新的权衡维度。
20.8.4 磁盘 I/O 与 B-Tree 的数学关系
设：
- n = 记录总数
- m = B-Tree 的阶（最大子节点数）
- h = 树的高度
则高度的精确界为：
h ≤ log_{⌈m/2⌉}((n+1)/2) + 1 （最大高度，节点半满）
h ≥ log_m(n+1) （最小高度，节点全满）
对于 InnoDB 的典型参数（m ≈ 1170，n = 1 亿）：
- 最小高度：log₁₁₇₀(100,000,001) ≈ 2.6 → 3 层
- 最大高度：log₅₈₅(50,000,001) ≈ 2.78 → 3 层
所以无论填充率如何，3 层都够了。这就是为什么 DBA 常说"InnoDB 的 B+Tree 几乎总是 3 层高"。
Buffer Pool 的影响：
InnoDB 的 Buffer Pool（默认 128MB，生产环境通常设为物理内存的 50-80%）缓存热点页：
- 根节点：几乎永远在 Buffer Pool 中（100% 命中率）
- 第二层内部节点：1170 个页 × 16KB = 18.3MB，也几乎全在内存中
- 第三层叶子节点：1170² ≈ 137 万页 × 16KB ≈ 21.4GB，按访问频率缓存
结论：对于热数据，实际的磁盘 I/O 可能只有 0-1 次（只有冷数据的叶子页需要从磁盘读取）。
Level 4 · 边界与陷阱
20.9 与本站其他书的联系
本章的内容与以下章节紧密相关：
- MySQL 高性能实战 · 索引章节 — 详细讨论了 InnoDB B+Tree 索引的实战技巧：如何选择合适的索引列、如何分析 EXPLAIN 输出、索引失效的常见场景
- MySQL 高性能实战 · 架构章节 — InnoDB 存储引擎的整体架构，包括 Buffer Pool、Change Buffer、Redo Log 等与 B+Tree 协作的组件
- Redis 深度解析 — 跳表在 Redis ZSET 中的具体实现，以及 Redis 的其他数据结构选择
20.10 面试中如何回答"MySQL 为什么用 B+Tree"
这是后端面试中出现频率最高的问题之一。以下是一个结构化的回答框架：
第一层：磁盘 I/O 约束 "数据库的数据存储在磁盘上，磁盘随机 I/O 很慢（SSD ~100μs，HDD ~10ms）。我们需要一种树高极低的数据结构，使每次查找只需要少量磁盘 I/O。"
第二层：为什么不是红黑树/AVL "红黑树是二叉的，1 亿条记录需要 ~27 层。每层一次 I/O 意味着一次查找要 27 次磁盘访问，不可接受。B+Tree 的每个节点可以有上千个分支，1 亿记录只需 3 层。"
第三层：为什么不是哈希表 "哈希表不支持范围查询（BETWEEN）、排序（ORDER BY）、最左前缀匹配。数据库需要这些操作，所以不能只用哈希。不过 InnoDB 有自适应哈希索引作为补充。"
第四层：为什么是 B+Tree 而非 B-Tree "B+Tree 的内部节点不存数据，所以每页能放更多 key，树更矮。而且叶子节点组成链表，范围查询只需定位起点后顺序扫描，不需要回溯。"
加分项：提到 Buffer Pool "实际运行中，因为 Buffer Pool 的存在，B+Tree 根节点和前几层内部节点几乎总是在内存中，真正的磁盘 I/O 通常只有 0-1 次。"
20.11 B+Tree vs LSM-Tree 的选型指南
| 维度 | B+Tree | LSM-Tree |
|---|---|---|
| 读写比 | 读多写少 | 写多读少 |
| 延迟特征 | 稳定（每次 2-4 I/O） | 写低延迟，读可能偶尔毛刺 |
| 空间放大 | 低（页内碎片） | 中（多版本数据暂存） |
| 写放大 | 中（页粒度写） | 高（Compaction 反复重写） |
| 读放大 | 低（直接定位） | 高（多层查找） |
| 典型系统 | MySQL, PostgreSQL, Oracle | RocksDB, Cassandra, HBase |
| 适用场景 | OLTP, 事务处理 | 日志, 时序, 写密集 |
实际选型建议：
- 如果你是传统 OLTP 业务（电商、社交、支付），99% 的情况选 MySQL/PostgreSQL（B+Tree）
- 如果你是日志分析、监控指标、IoT 数据，考虑 ClickHouse/TDengine（列存+LSM 变体）
- 如果你需要高写吞吐的 KV 存储，考虑 RocksDB（LSM-Tree）
- TiDB 的存储层 TiKV 使用 RocksDB（LSM-Tree），但上层提供了 MySQL 兼容的 SQL 接口——这是"LSM-Tree 实现 B+Tree 语义"的工程方案
20.12 常见面试题与陷阱
问：B+Tree 的叶子节点是单链表还是双向链表？ 答：InnoDB 使用双向链表。File Header 中有 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 两个字段。这样既支持正序扫描（ASC）也支持逆序扫描（DESC）。
问：InnoDB 一棵 B+Tree 能存多少数据？ 答：假设主键 bigint（8B），行大小 1KB：
- 内部节点扇出 ≈ 16KB / (8+6)B ≈ 1170
- 叶子每页 ≈ 16KB / 1KB ≈ 16 行
- 3 层：1170 × 16 = 18,720 行
- 4 层：1170² × 16 ≈ 2190 万行
- 但如果行只有 100B，叶子每页 160 行，3 层就能存 1170 × 160 ≈ 1.87 亿行
问：为什么 MongoDB 之前用 B-Tree 而不是 B+Tree？ 答：MongoDB 的 WiredTiger 引擎实际上使用的是 B+Tree 的变体。早期 MMAPV1 引擎使用的类 B-Tree 结构是因为它直接 mmap 文件，设计理念不同。MongoDB 4.0 之后默认 WiredTiger，本质也是 B+Tree。
问：LSM-Tree 的 Compaction 会导致什么问题？ 答：
- 写放大：数据被反复读取和重写，消耗 SSD 寿命
- 空间放大：Compaction 期间需要同时存新旧两份数据
- 延迟毛刺：大规模 Compaction 会占用 I/O 带宽，影响前台读写
问：RocksDB 用什么解决 LSM-Tree 的读性能问题？ 答：
- Bloom Filter：每个 SSTable 带 Bloom Filter，跳过不包含目标 key 的文件
- Block Cache：缓存热点数据块
- 前缀 Bloom Filter：对 key 前缀建立 Bloom Filter，加速前缀查询
- 压缩：减少实际 I/O 数据量（LZ4/Snappy/ZSTD）
本章小结
本章围绕"如何在外存上高效组织有序数据"这个核心问题，介绍了三种关键数据结构：
- B-Tree：通过增大节点宽度降低树高，将磁盘 I/O 从 O(log₂n) 降到 O(log_m n)
- B+Tree：在 B-Tree 基础上让数据只存叶子、叶子串联链表，成为数据库索引的标准
- LSM-Tree：将随机写转为顺序写，牺牲读性能换取写吞吐，成为写密集场景的首选
它们不是"谁取代谁"的关系，而是针对不同工作负载的最优解。理解它们的设计权衡，是从"会用数据库"到"懂数据库"的分水岭。