数据库系统内幕

45

第

3

章

文件格式

我们已经介绍了 B 树的基本语义，现在，我们可以探索 B 树以及其他数据结构究竟是如

何在磁盘上实现的。访问磁盘和访问主存有所不同：从应用开发者的视角看，主存访问

几乎是透明的。由于虚拟内存机制 [BHATTACHARJEE17] 的存在，我们不用手动管理

偏移量。而磁盘则是通过系统调用来访问的（参见

https://databass.dev/links/54

），我们通

常要指定目标文件内的偏移量，然后把数据从磁盘上的形式解析成适合主存的形式。

这意味着，要想设计一个高效的磁盘数据结构，必须牢记这一区别。为此，我们必须想

出一种易于构造、修改和解析的文件格式。在本章中，我们将会讨论通用的原理和实

践，它们可以帮助我们设计各种磁盘结构，而不仅仅是 B 树。

B 树有很多种可能的实现，在这里我们会讨论几种有用的技术。不同实现的细节可能有

所不同，但是通用的原理是不变的。理解 B 树的基本原理（比如分裂和合并）是很有必

要的，但这对于实际的实现来说还远远不够。要想做出一个有用的成品，还要掌握很多

知识。

磁盘数据结构中指针管理的语义与内存中的有所不同，你可以将磁盘上的 B 树看作一种

页管理机制：算法需要组合

页

并在页中移动。需要计算页和指向它们的指针并将它们放

置在相应的位置。

由于 B 树最复杂的地方在于它的可变性，所以我们将会讨论页布局、分裂、迁移等可

变数据结构中的概念。之后，当讨论 LSM 树 （参 见 7.1 节）时，我们会专注于排序和维

护，因为那是 LSM 树最复杂的地方。

3.1

动机 ...