第 33 课 - B 树与 B+ 树

所属模块：树结构难度：advanced 标签：b-tree, b-plus, disk, database 上一课：红黑树 下一课：字典树（Trie）

1. 学习目标

理解 B 树和 B+ 树的产生背景和在数据库/文件系统中的核心价值。
掌握 B 树的结构定义、性质及核心的插入与删除操作原理。
清晰辨别 B 树与 B+ 树的结构差异，并理解 B+ 树为何更适用于数据库索引。
了解 B 树家族在实际系统（如 MySQL InnoDB）中的应用方式。

2. 核心概念

想象一下，你在图书馆找一本关于“烹饪”的书。图书馆不是只有一个放着所有书的大书架，而是有很多分区：A区放历史，B区放科学，C区放生活...，而“烹饪”书在“生活”区。为了找到它，你先到大厅看分区图（B 树的根节点），找到“生活”区，然后再到该区的具体书架（子节点）上找到这本书。

B 树 (B-Tree) 就像这个图书馆的索引系统。它是一种平衡多路查找树。与二叉树（每个节点最多两个孩子）不同，B 树的节点可以有多个孩子（称为“阶”，Order）。一个 M 阶的 B 树满足以下性质：

每个节点最多有 M 个孩子。
除了根节点和叶子节点，每个节点至少有 ⌈M/2⌉ 个孩子（根节点至少 2 个孩子，如果不是叶子的话）。
一个有 K 个孩子的非叶子节点，包含 K-1 个有序的键值（Key），用于索引。
所有叶子节点出现在同一层。

关键优势：由于每个节点可以存放多个键和指针，树的高度大大降低。这意味着查找一个记录需要的磁盘 I/O 次数非常少，而磁盘 I/O 通常是数据库系统的性能瓶颈。

B+ 树 (B+ Tree) 是 B 树的一种优化变体，是数据库索引的事实标准。它与 B 树的主要区别：

数据存储位置：B 树的键和数据记录分布在所有节点上。B+ 树只将数据记录（或指向记录的指针）存储在叶子节点，内部节点只存键和指向孩子的指针，充当纯粹的“路标”。
叶子节点链表：B+ 树的所有叶子节点通过一个双向链表连接。这使得范围查询（如 WHERE id > 100 AND id < 500）变得极其高效，只需遍历链表即可，无需回溯树的内部节点。
内部节点容量：由于内部节点不存数据，只存“路标”，因此一个内部节点可以容纳更多的键，使得树变得更“矮胖”，查找更快。

生活化比喻：

B 树：像一本百科全书，目录（索引）和具体词条解释穿插在每一页上。
B+ 树：像一本末尾附有详细索引的字典。目录部分（内部节点）只有词和页码，而所有词条解释（数据）都按顺序集中在书的后面（叶子节点），并且词条之间用空白页（链表）连接，方便你快速翻阅所有相关词条。

3. 代码示例

注意：完整实现一个可用于生产的 B 树或 B+ 树非常复杂。以下是一个简化的、仅用于演示插入逻辑和结构验证的 Python 3 示例（3阶 B 树）。它省略了删除、复杂的分裂合并和磁盘 I/O 模拟。

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []      # 存储键值
        self.children = []  # 存储子节点引用
        self.leaf = leaf    # 是否是叶子节点

    def __str__(self):
        return f"Keys: {self.keys}"

class BTree:
    def __init__(self, t=3): # t 是树的最小度数 (minimum degree)，这里是3阶
        self.root = BTreeNode(leaf=True)
        self.t = t

    def search(self, node, key):
        """在以 node 为根的子树中搜索键 key"""
        i = 0
        # 在当前节点的 keys 中找到第一个大于等于 key 的位置
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        # 找到 key
        if i < len(node.keys) and key == node.keys[i]:
            return (node, i)  # 返回节点和键的索引
        # 如果是叶子节点还没找到，说明 key 不存在
        elif node.leaf:
            return None
        # 否则，递归去对应的子节点中找
        else:
            return self.search(node.children[i], key)

    def insert(self, key):
        """插入一个键 key 到 B 树中"""
        root = self.root
        # 根节点满了，需要先分裂根节点，树高增加1
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode()
            self.root = new_root
            new_root.children.insert(0, root)
            self._split_child(new_root, 0)
            self._insert_non_full(new_root, key)
        else:
            self._insert_non_full(root, key)

    def _insert_non_full(self, node, key):
        """将 key 插入到一个未满的节点 node 中"""
        i = len(node.keys) - 1
        if node.leaf:
            # 如果是叶子节点，直接在合适位置插入
            node.keys.append(0) # 扩容
            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) == (2 * self.t) - 1:
                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, i):
        """分裂 parent 的第 i 个子节点（已满）"""
        t = self.t
        y = parent.children[i] # 要分裂的节点
        z = BTreeNode(leaf=y.leaf) # 新创建的节点

        # 将 y 的后半部分 (t-1个键) 移动到 z
        z.keys = y.keys[t: (2*t)-1]
        y.keys = y.keys[0: t-1]

        # 如果 y 不是叶子，还要移动孩子
        if not y.leaf:
            z.children = y.children[t: 2*t]
            y.children = y.children[0: t]

        # 将 y 的中间键提升到父节点 parent
        parent.children.insert(i+1, z)
        parent.keys.insert(i, y.keys.pop()) # y 的最后一个键就是中间键

    def traverse(self):
        """层序遍历树，用于调试"""
        if self.root:
            queue = [self.root]
            while queue:
                node = queue.pop(0)
                print(node.keys, end=" ")
                if not node.leaf:
                    queue.extend(node.children)
            print()

# 测试代码
btree = BTree()
keys = [10, 20, 5, 6, 12, 30, 7, 17]

for key in keys:
    btree.insert(key)
    print(f"插入 {key} 后:")
    btree.traverse()

# 搜索测试
result = btree.search(btree.root, 17)
if result:
    node, idx = result
    print(f"找到键 17，在节点 {node.keys} 的索引 {idx}")
else:
    print("未找到键 17")

4. 实践练习

概念理解（易）：假设我们有一个 4 阶（M=4）的 B+ 树。请画出依次插入键值 1, 2, 3, 4, 5, 6, 7, 8 后的最终结构图（只需画出叶子节点链和上一层内部节点即可）。
代码修改（中）：在上面的 BTree 类中，添加一个 range_query(low, high) 方法，假设树中存储的是整数，返回所有在 [low, high] 区间内的键的列表。（提示：需要结合搜索和遍历逻辑）
分析思考（难）：为什么在实现数据库索引时，B+ 树通常比 B 树更受欢迎？请从查询性能（点查和范围查）、空间利用、以及与磁盘预读特性的匹配三个方面进行阐述。

5. 常见错误

混淆 B 树和 B+ 树：错误地认为两者结构相同。关键区别在于：B+ 树的内部节点不存数据且叶子节点有链表。
忽略节点分裂：在插入时，必须检查节点是否已满（2t-1 个键），并在递归插入前进行分裂，否则会破坏树的平衡性质。
误解“阶”的概念：阶 (Order) 的定义在不同教材中可能不同。有的指最大孩子数 (M)，有的指最小度数 (t)。务必确认定义。本课使用 t（最小度数），一个节点最多有 2t-1 个键。
B+ 树范围查询性能误区：以为在 B+ 树上做范围查询和 B 树一样复杂。实际上，B+ 树的叶子链表使得范围查询只需定位到起点，然后顺序扫描链表即可，效率极高。

6. 小结

B 树和 B+ 树是为磁盘存储优化的平衡多路查找树，通过降低树高来减少 I/O。
B 树：键和数据分布在所有节点。适用于文件系统。
B+ 树：数据只存于叶子节点，叶子节点由链表连接，内部节点仅作索引。是关系型数据库索引的首选。
核心操作（插入、删除）依赖于节点的分裂与合并来维持平衡。
理解这两种树，对于深入理解数据库索引原理（如 MySQL InnoDB 的聚簇索引）至关重要。

下一课预告：我们将学习另一种重要的树结构——字典树（Trie），它在处理字符串前缀匹配等问题上有着独特的优势。

练习编辑器

rust