Chapter 4

Implementing B-Trees

在上一章中，我们讨论了二进制格式的构成，以及了解到了如何创建 Cell、构建对应的层级结构以及通过指针来将各个页连接起来。这些概念同时适用于就地更新及只有添加操作的两种类型的存储结构。在本章，我们会针对性的讨论关于 B-Tree 的概念。

我们将本章按照逻辑分为三部分，第一部分我们会讨论组织：如何创建 Key 跟指针的联系，以及如何实现页的头部信息跟页之间的链接信息。

紧接着我们讨论从根到叶子节点下降过程的处理，如何实现二分查找及如何收集信息及如何在分裂跟合并操作中保持对父节点的跟踪。

最后，我们会讨论一些优化技术 (重新平衡、right-only appends 只限右侧添加操作跟 bulk loading 批量读取)，管理操作以及垃圾回收。