B+Tree 索引结构与并发控制

B+ 树是关系数据库索引的事实标准：MySQL InnoDB、PostgreSQL、SQLite 的主索引全是它。本文用一个 200 行的 Python 实现完整复现 B+ 树的插入、节点分裂、叶子链表范围查询，并用一次真实运行展示锁耦合（lock crabbing）并发协议如何把全路径锁优化成『最多持有两个节点闩锁』。

一、为什么是 B+ 树而不是 B 树或跳表

B+ 树相对 B 树的关键改动是：内部节点只存键不存数据，所有记录都挂在叶子层，且叶子间用链表串联。这带来两个工程优势：内部节点同样大小的页能容纳更多键（扇出更大、树更矮，磁盘 I/O 次数更少）；范围查询只需定位起点后沿叶子链表顺序扫，完美匹配磁盘的顺序读特性。跳表（Redis 有序集合所用）实现简单且并发友好，但页局部性差——每个节点一次随机 I/O，在磁盘时代输在了起跑线上。LSM-Tree（本专栏另有专文）则以顺序写换取写吞吐，是另一个极端。

二、核心机制：插入、分裂与叶子链表

查找：从根开始二分定位子指针，逐层下钻到叶子，O(log n) 次节点访问。
插入与分裂：叶子满（达到阶数）时对半分裂，中位键上推到父节点；父节点也满则递归向上分裂，最坏传导到根产生新根——树高因此加一。B+ 树只长根、从不下陷，这是它保持平衡的方式。
叶子链表：分裂时维护 next 指针，保证叶子层是一条全局有序链表。范围查询 [lo, hi] 只需一次树查找定位 lo，然后纯顺序扫描。

三、完整可运行实现（Python 3，约 200 行）

#!/usr/bin/env python3
"""B+Tree 模拟：插入/分裂、叶子链表范围查询、锁耦合并发协议"""

ORDER = 4   # 4 阶 B+树，每个节点最多 3 个键

class Node:
    def __init__(self, leaf=False):
        self.keys = []
        self.children = []   # 内部节点：子节点；叶子：值
        self.leaf = leaf
        self.next = None     # 叶子链表指针
        self.latch_count = 0 # 并发演示：当前持有的闩锁数

class BPlusTree:
    def __init__(self):
        self.root = Node(leaf=True)
        self.splits = 0

    def insert(self, key, val):
        path = []
        node = self.root
        while not node.leaf:
            path.append(node)
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            node = node.children[i]
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        node.keys.insert(i, key)
        node.children.insert(i, val)
        if len(node.keys) >= ORDER:
            self._split_leaf(node, path)

    def _split_leaf(self, leaf, path):
        self.splits += 1
        mid = len(leaf.keys) // 2
        new_leaf = Node(leaf=True)
        new_leaf.keys = leaf.keys[mid:]
        new_leaf.children = leaf.children[mid:]
        leaf.keys = leaf.keys[:mid]
        leaf.children = leaf.children[:mid]
        new_leaf.next = leaf.next     # 维护叶子链表
        leaf.next = new_leaf
        up_key = new_leaf.keys[0]
        self._propagate(up_key, new_leaf, path)

    def _propagate(self, key, new_node, path):
        if not path:
            new_root = Node()
            new_root.keys = [key]
            new_root.children = [self.root, new_node]
            self.root = new_root
            return
        parent = path.pop()
        i = 0
        while i < len(parent.keys) and key > parent.keys[i]:
            i += 1
        parent.keys.insert(i, key)
        parent.children.insert(i + 1, new_node)
        if len(parent.keys) >= ORDER:
            self._split_internal(parent, path)

    def _split_internal(self, node, path):
        self.splits += 1
        mid = len(node.keys) // 2
        up_key = node.keys[mid]
        new_node = Node()
        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._propagate(up_key, new_node, path)

    def range_query(self, lo, hi):
        """定位 lo 所在叶子，沿叶子链表扫到 hi"""
        node = self.root
        while not node.leaf:
            i = 0
            while i < len(node.keys) and lo >= node.keys[i]:
                i += 1
            node = node.children[i]
        out = []
        scanned = 0
        while node:
            for i, k in enumerate(node.keys):
                scanned += 1
                if lo <= k <= hi:
                    out.append(k)
                if k > hi:
                    return out, scanned
            node = node.next
        return out, scanned

    def height(self):
        h = 1
        n = self.root
        while not n.leaf:
            n = n.children[0]
            h += 1
        return h

print('=== B+Tree 模拟（4 阶） ===')
t = BPlusTree()
import random
random.seed(7)
keys = random.sample(range(1, 100), 20)
print('插入 20 个随机键:', keys[:8], '...')
for k in keys:
    t.insert(k, 'v%d' % k)
print('插入完成: 树高=%d, 根节点键=%s, 总分裂次数=%d'
      % (t.height(), t.root.keys, t.splits))

node = t.root
while not node.leaf:
    node = node.children[0]
chain = []
while node:
    chain.extend(node.keys)
    node = node.next
print('叶子链表(%d 键): %s' % (len(chain), chain))
print('链表全局有序: %s' % (chain == sorted(chain)))

res, scanned = t.range_query(30, 55)
print('范围查询 [30,55]: 命中 %s, 仅扫描 %d 个键（叶子链表顺序读）'
      % (res, scanned))

# ---------- 锁耦合（crabbing）演示 ----------
print()
print('--- 锁耦合(crabbing)查找 key=42 的加锁序列 ---')
t2 = BPlusTree()
for k in sorted(keys):
    t2.insert(k, 'v')

def crab_search(root, key):
    held = []
    node = root
    def latch(n, tag):
        n.latch_count += 1
        held.append(n)
        print('  加闩 %s' % tag)
    def unlatch(n, tag):
        n.latch_count -= 1
        held.remove(n)
        print('  释放 %s' % tag)
    latch(root, 'root(read)')
    while not node.leaf:
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:
            i += 1
        child = node.children[i]
        latch(child, 'child(read)')          # 先加子节点
        if len(child.keys) < ORDER - 1:
            unlatch(node, 'parent(read)')    # 子节点安全即放父
        node = child
    print('  到达叶子, 持有闩锁数=%d（无需全路径持有）' % len(held))

crab_search(t2.root, 42)
print('说明: 父闩在确认子节点安全后立即释放——'
      '并发度远高于全路径锁')

四、真实运行输出与解读

以上代码在 Python 3 下原样运行（仅依赖 random），输出如下：

=== B+Tree 模拟（4 阶） ===
插入 20 个随机键: [42, 20, 51, 84, 7, 10, 69, 13] ...
插入完成: 树高=3, 根节点键=[20, 51], 总分裂次数=9
叶子链表(20 键): [5, 7, 8, 9, 10, 12, 13, 20, 28, 31, 42,
                 47, 51, 54, 56, 65, 69, 71, 75, 84]
链表全局有序: True
范围查询 [30,55]: 命中 [31, 42, 47, 51, 54], 仅扫描 8 个键（叶子链表顺序读）

--- 锁耦合(crabbing)查找 key=42 的加锁序列 ---
  加闩 root(read)
  加闩 child(read)
  释放 parent(read)
  加闩 child(read)
  释放 parent(read)
  到达叶子, 持有闩锁数=1（无需全路径持有）
说明: 父闩在确认子节点安全后立即释放——并发度远高于全路径锁

分裂的真实代价：4 阶小树上插入 20 个键触发了 9 次分裂——阶数越小分裂越频繁。这正是生产数据库用几百阶（16KB 页能存几百个键）的原因：InnoDB 默认页大小下，千万行数据的索引树高通常只有 3~4，每次点查固定 3~4 次页 I/O。
范围查询的顺序性：查询 [30,55] 命中 5 个键，总共只扫了 8 个——定位起点后沿链表读，扫描成本与结果集大小成正比，与全表数据量无关。
锁耦合的精髓：演示中加锁序列是『锁父 → 锁子 → 确认子节点不会因本次操作分裂/合并 → 立即放父』，像螃蟹一样钳子交替前移。到达叶子时只持有 1 个闩锁，而不是全路径 3 个——并发度提升的本质是把锁的持有范围从『整条路径』压缩到『父子一对』。

五、理论分析

5.1 闩锁与锁的区分

数据库内核严格区分 latch 与 lock：lock 保护事务逻辑一致性（行锁、表锁，由锁管理器维护，随事务持有），latch 保护物理数据结构（B+ 树节点、缓冲页，只持有关键区几微秒）。锁耦合操作的是 latch。混淆两者会导致设计错误：用事务锁保护树结构会让点查退化成串行。

5.2 乐观协议：OLC 与 Blink 树

锁耦合仍要每级取闩。更激进的方案有两支：Blink 树（Lehman-Yao 1981）给每层加右链与 upper-fence key，查找全程无闩，分裂中的节点通过右链绕行；乐观锁耦合 OLC（Masstree、ART 所用）给每个节点配版本号，读路径零闩，只在结构变更时校验版本重来。现代内存索引几乎全部采用 OLC 变体。

5.3 缓冲池的协同

B+ 树节点即缓冲池中的页，闩锁与缓冲池的 fix/unfix 机制绑定：fix 一页即持有其闩，unfix 即释放。页替换（LRU/Clock）只考虑未 fix 的页。这层耦合解释了为什么高并发下『缓冲池命中率』与『闩锁竞争』必须一起看——热点根页既是缓存热点也是闩锁热点。

六、工程应用

InnoDB 参数：innodb_page_size（默认 16KB）决定阶数；innodb_buffer_pool_size 决定热页驻留；innodb_spin_wait_delay 调节闩锁自旋。SHOW ENGINE INNODB STATUS 的 SEMAPHORES 段直接暴露闩锁竞争。
索引设计原则：主键单调递增（自增/雪花 ID 趋势序）能让插入恒落在最右叶子，几乎不触发中间分裂；随机主键（UUID）则打散插入点，分裂频繁且页填充率低——实测写入吞吐可差 2~3 倍。
观测分裂：InnoDB 的 INFORMATION_SCHEMA.INNODB_METRICS 中 index_page_splits 计数分裂次数；突发上涨通常预示主键设计或批量导入顺序问题。

七、常见误区

误区 1：『B+ 树越高越慢，应该压低树高』。树高由阶数与数据量决定，4 层树支撑上亿行毫无问题；真正该关心的是根与上层节点是否常驻缓冲池——它们命中内存时，树高多一层只多一次内存二分。
误区 2：『叶子链表只是范围查询的优化』。叶子链表还是并发协议的一部分：Blink 树的右链让无闩查找成为可能，没有它就无法绕过正在分裂的节点。
误区 3：『锁耦合里的安全判断可以省』。『子节点未满即安全』的判断是整个协议正确性的基石：若分裂可能向上传导，就必须持有整条受影响路径的写闩。省掉判断会出现分裂改树与并发查找竞争的撕裂。
误区 4：『随机主键只是插入慢一点』。随机插入还会导致页填充率掉到 60%~70%（分裂各留半空），索引体积膨胀约 40%，连带缓冲池有效容量下降——写入慢只是冰山一角。

八、参考文献

D. Comer (1979). The Ubiquitous B-Tree. ACM Computing Surveys.（B 树家族的经典综述）
P. Lehman, S. Yao (1981). Efficient Locking for Concurrent Operations on B-Trees. ACM TODS.（Blink 树原始论文）
G. Graefe (2010). A Survey of B-Tree Locking Techniques. ACM TODS.（锁耦合到 OLC 的完整谱系）
V. Leis et al. (2013). The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. ICDE.（OLC 的现代应用）
MySQL Documentation: InnoDB Row Formats and Page Structure 与 INNODB_METRICS 表说明。

← 返回文章列表