在 Go 中构建 B 树：理论与实现之间的差距
发布: (2026年1月14日 GMT+8 18:33)
6 min read
原文: Dev.to
Source: Dev.to
（此处未提供需要翻译的正文内容。如需翻译，请提供完整的文章文本。）
为什么使用 B‑树？
- 大多数数据库索引都是 B‑树（或 B+‑树）。
- 与二叉树（每个节点 2 个子节点）不同，B‑树的节点可以拥有多个子节点，数量由 阶 决定。
- 这种多路分支使 B‑树非常适合磁盘存储，因为每次读取磁盘块的代价很高。
我不会在这里重新解释 B‑树——《Database Internals》第 2 章已经把它讲得非常出色。本文假设你已经了解基础知识，重点讨论我在构建 B‑树时学到的内容。
实现要点
核心操作
- 节点内部的二分搜索 → 递归到相应的子节点。
- 节点分裂 – 保持树的平衡：找到中位数，分成两半，提升中位键。
- 根节点分裂 – 特殊情况：创建一个全新的根节点，包含提升的键，使树变得更高而不是更宽。
注意事项
| 问题 | 我的收获 |
|---|---|
| 分裂级联 | 插入键可能会触发向上级的分裂级联。必须正确更新每个父子指针。 |
| 内部节点分裂 | 不仅仅是移动一两个键——必须重新连接整个子图的子节点并修正它们的父指针。 |
| B 树 与 B+ 树 | B 树在每个节点存储数据；B+ 树仅在叶子节点存储数据（叶子之间通过链表链接以实现快速范围扫描）。我的实现一旦找到键就停止搜索，这很优雅，但会导致范围查询成本高。 |
| 偏斜插入 | 插入顺序键（1, 2, 3, …）会产生一个只有 50 个键的 7 层深树——一种病态情况，凸显了批量加载策略和 REINDEX 的必要性。 |
| 随机插入 | 产生了一个平衡良好的 3 层树，展示了 B 树的自然自平衡特性。 |
测试驱动开发 (TDD)
我在任何实现代码之前就编写了 20+ 单元测试（覆盖率 100%）*，*这些测试迫使我思考边界情况，并提前定义了“完成”的标准。
通过测试捕获的错误
- 重复键插入（忘记检查键是否已存在）。
- 索引边界的 off‑by‑one 错误。
- 分裂后子节点计数不匹配（
n个键 →n+1个子节点）。 - 分裂级联后父指针错误。
当所有测试最终全部通过时，信心立刻油然而生——不再需要祈祷，只剩下确信。
统计
| 指标 | 值 |
|---|---|
| 花费时间 | 大约15 小时，跨4天 |
| 代码规模 | 大约200 行 Go 代码 |
| 测试 | 超过20个单元测试，覆盖率100 % |
| 发现的错误 | 多得数不清（全部通过 TDD 捕获） |
| 消耗的咖啡 | 相当多 ☕️ |
反思
- 动手学习胜过被动阅读。看到树的指针在内存中变化，使抽象概念变得具体。
- TDD 不仅是最佳实践——它是一种思考工具。先编写测试迫使我明确想要的行为。
- B+树 vs B树——现在我明白了 PostgreSQL 为什么在索引中使用 B+树（更好的范围扫描），同时仍然欣赏纯 B树的优雅。
接下来是什么？
我计划深入研究 LSM‑树（日志结构合并树），它们颠倒了权衡：
- B‑树 → 优化读取（就地更新）。
- LSM‑树 → 优化写入（追加写入）。
实现压缩策略将是下一层的乐趣。 🤩
TL;DR
如果你对数据库内部原理感兴趣：
- 阅读 Database Internals（Alex Petrov 著）。
- 选取一种数据结构（B‑tree、LSM‑tree 等）并 动手实现。
- 使用 TDD 及早锁定边缘情况。
阅读与实现之间的差距正是产生真正 魔法 的地方。
你可以在我自托管的 GitLab 上看到完整实现（是的，我自己跑着实例：极客生活）。如果发现改进之处，欢迎提交 Pull Request！ 😊