B 树：磁盘巨人

算法背后的故事：矮个子图书管理员

想象一个拥有 10 亿本书的图书馆。

• 场景 A (二叉树)： 为了找一本书，你从入口开始。“左还是右？”你向左。“左还是右？”你向右。你可能需要穿过 30 道门（树的高度）才能找到书。
• 场景 B (B 树)： 图书管理员很矮，但胳膊很长。在入口处，他手里拿着 1000 张索引卡。他说：“书在 452 号房间。”你走到 452 号房间。那里，另一位管理员拿着 1000 张卡片。“12 号架子。”你走到 12 号架子。找到了。

在场景 B 中，你只穿过了 3 道门。 为什么？因为每个节点（管理员）掌握的信息量大得多。

这就是 B 树。它是为 硬盘 设计的，在那上面，“走路”（寻道）很慢，但“阅读”（传输数据）很快。

为什么需要它？

• 数据库： MySQL (InnoDB), PostgreSQL, SQLite 都使用 B 树（或 B+ 树）作为索引。
• 文件系统： NTFS (Windows), HFS+ (Mac), XFS 都使用 B 树来追踪文件。
• 为什么不用 BST？ 磁盘上的 BST 查找一条记录需要 30 次随机寻道，耗时约 300ms。B 树只需要 3 次 (~30ms)。

算法是如何“思考”的

这个算法是一个多路管理者。

1. 胖节点： 一个节点不是拥有 1 个键和 2 个孩子，而是拥有多达 $M$ 个键和 $M+1$ 个孩子（例如 M=1000）。
2. 排序： 节点内部的键是有序的。我们可以在节点内部使用二分查找（因为数据在 RAM 中，所以很快）。
3. 生长：
   • 插入发生在 叶子 处。
   • 如果叶子满了，它会从中间 分裂。中间的键被踢给父亲。
   • 如果父亲也满了，它也分裂。
   • 树是向上生长的，根节点始终在顶部。

工程决策：B 树 vs. B+ 树

在实践中，几乎所有人都使用 B+ 树 变体。

• B 树： 数据存储在所有节点中。
• B+ 树： 数据只存储在叶子中。内部节点只是路标（键）。叶子通过链表链接在一起。
  • 好处： 扫描“ID 从 100 到 200 的所有用户”超级快。你只需找到 100，然后沿着叶子的链表走即可。

实现参考 (Python 概念版)

实现一个 B 树是 500 行代码级别的工程。这里展示搜索逻辑，以体现“多路”特性。

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.children = []

def search(node, k):
    # 找到第一个大于或等于 k 的键
    i = 0
    while i < len(node.keys) and k > node.keys[i]:
        i += 1
    
    # 1. 在此节点中找到了吗？
    if i < len(node.keys) and node.keys[i] == k:
        return (node, i)
    
    # 2. 如果是叶子，说明找不到了
    if node.leaf:
        return None
        
    # 3. 递归进入正确的孩子
    return search(node.children[i], k)

# 魔法在于 'node.children[i]' 将搜索空间缩小了 
# M 倍（例如 1000），而不仅仅是 2 倍。

小结

B 树教会我们：硬件决定结构。当移动成本（磁盘 I/O）很高时，你应该在一次行程中携带尽可能多的东西。它提醒我们，高效的软件不仅仅关于 $O(N)$，更关乎理解机器的物理现实。