数据库系统内幕

59

第

4

章

B 树的实现

在上一章中，我们讨论了二进制格式的一般原理，并学习了如何创建单元格、构建层次

结构以及如何使用指针将它们与页进行连接。这些概念对原地更新和仅追加存储结构都

适用。在本章中，我们将讨论一些 B 树特有的概念。

本章各节在逻辑上分为三组。首先，我们将讨论数据组织：如何建立键和指针之间的关

系，以及如何实现页头和页之间的链接。

接下来，我们将讨论从根节点到叶子节点的整个下降过程：如何执行二分搜索，以及如

何收集相关内容并跟踪父节点，以备后续发生节点的分裂或合并时使用。

最后，我们将讨论优化技术（再平衡、仅在右边追加和批量加载）、维护过程和垃圾收集。

4.1

页头

页头保存有关可用于页定位、维护和优化的信息。它通常包含描述页内容和布局的标志

位、页中单元格的数量、标记空闲空间的上界与下界偏移量（用于追加单元格偏移量和

数据）以及其他有用的元数据。

例如，PostgreSQL 会在头部储存页大小和布局版本。在 MySQL InnoDB 中，页头保存

该页中的记录总数、层数和其他一些与实现相关的值。在 SQLite 中，页头存储单元格的

数量和最右指针。

4.1.1

魔数

文件或页头中经常放置的一个值是魔数。通常，它是一个多字节块，包含一个常数值，

表示该块代表一个页，并指定页的类型或标识其版本。

魔数通常用于校验和完整性检查 [GIAMPAOLO98]。随机偏移量下的字节序列与魔数完

全匹配的概率很小。如果匹配，则偏移量很可能是正确的。例如，为了验证页加载和对