下载掌阅APP，畅读海量书库
立即打开
页头保存有关可用于页定位、维护和优化的信息。它通常包含描述页内容和布局的标志位、页中单元格的数量、标记空闲空间的上界与下界偏移量（用于追加单元格偏移量和数据）以及其他有用的元数据。
例如，PostgreSQL会在头部储存页大小和布局版本。在MySQL InnoDB中，页头保存该页中的记录总数、层数和其他一些与实现相关的值。在SQLite中，页头存储单元格的数量和最右指针。
文件或页头中经常放置的一个值是魔数。通常，它是一个多字节块，包含一个常数值，表示该块代表一个页，并指定页的类型或标识其版本。
魔数通常用于校验和完整性检查[GIAMPAOLO98]。随机偏移量下的字节序列与魔数完全匹配的概率很小。如果匹配，则偏移量很可能是正确的。例如，为了验证页加载和对齐是否正确，在写入期间，我们可以将魔数50 41 47 45（“PAGE”（页）的十六进制表示）放入头部。在读取过程中，我们通过把从头部读取的四个字节与预期的字节序列进行比较来校验页。
一些实现存储了前序和后继指针，指向左、右同级页。这些指针有助于定位相邻节点，而不必返回父节点。这种方法为分裂和合并操作增加了一些复杂度，因为同级偏移量也必须同时更新。例如，当一个非最右边的节点被拆分时，其同级右节点的后向指针（之前指向被拆分的节点）必须被重新绑定以指向新创建的节点。
在图4-1中可以看到，要定位一个同级节点，除非有指针指向同级节点，否则我们必须通过父节点才能定位。这个操作可能一直上升到根节点，因为直接父节点只能帮助找到它自己的子一级节点。如果在页头中存储直接连接同级节点的指针，我们便可以方便地通过这些指针来定位同一层上的前序或后继节点。
图4-1：通过跟随父节点（a）或同级指针（b）来定位同级节点
存储同级指针的缺点之一是在分裂和合并期间必须更新它们。由于更新必须在同级节点中进行，而不是在分裂/合并节点中进行，所以可能需要额外的锁。我们将在5.3.8节中讨论同级指针在并发B树的实现中是如何发挥作用的。
B树分隔键有严格的不变式：它用于将树拆分为子树并对这些子树进行遍历，因此指向子页的指针总是比指向键的指针多一个。这就是2.3.5节中提到的+1的来源。
在2.3.2节中，我们描述了分隔键不变式。在许多实现中，节点看起来更像图4-2中所示的节点：每个分隔键都有一个子指针，而最后一个指针则单独存储，因为它并没有与任何键相匹配。你可以将其与图2-10进行比较。
图4-2：最右指针
这个额外的指针可以存储在头部，例如，其在SQLite中的具体实现便是如此。
如果最右侧的子指针被拆分，并且新的单元格被追加到其父节点上，则必须重新分配最右子指针。如图4-3所示，拆分后追加到父节点的单元格（灰色）包含被提升的键，并指向拆分节点。此时分配了一个指向新节点的指针来替代原先的最右指针。SQLite描述并实现了类似的方法。
图4-3：节点拆分期间最右指针的更新（被提升的键用灰色表示）
我们可以采用一种稍微不同的方法，将单元格中的最右指针与节点的高键（high key）存储在一起。节点的高键表示当前节点下的子树中可能存在的最高的键。PostgreSQL使用了这种方法，称为Blink树（有关此方法隐含的并发含义，请参见5.3.8节）。
B树有N个键（用K i 表示）和N+1个指针（用P i 表示）。在每个子树中，键以K i-1 ≤K s <K i 为界。K 0 =-∞是隐含的，并不在节点中表示。
Blink树向每个节点添加一个K N+1 键。它指定了指针P N 指向的子树中所存储的键的上限，因此它是当前子树中所存储的值的一个上限。这两种方法如图4-4所示：a）展示了没有高键的节点，b）展示了具有高键的节点。
图4-4：没有高键的B树（a）和有高键的B树（b）
在这种情况下，指针可以成对存储，并且每个单元格都可以有相应的指针，这可以简化最右指针的处理，因为没有那么多的边界条件需要考虑。
在图4-5中，你可以看到这两种方法的页结构示意图，以及在这些情况下搜索空间是如何被不同地划分的：在第一种情况下上界是+∞，在第二种情况下上界是K 3 。
图4-5：使用+∞作为虚拟键（a）与存储高键（b）
节点大小和树扇出是固定且不会动态改变的。我们也很难找到一个普遍最优的值：如果树中存在变长值，并且它们足够大，那么页中只能放下少数几个值；如果值很小，我们最终会浪费保留的空间。
B树算法规定每个节点持有特定数量的元素。由于某些值具有不同的大小，所以根据B树算法，可能会出现这样一种情况：节点尚未满，但保存该节点固定大小的页上已经没有更多的可用空间了。调整页大小需要将已经写入的数据复制到新区域，这通常是不切实际的。但我们仍然需要找到一种方法来增加或扩展页大小。
为了实现变长节点而无须将数据复制到新的连续区域，我们可以从多个链接起来的页中构建节点。例如，默认页大小为4K，而在插入几个值之后，其数据大小增长到4K以上。此时我们并不使用任意大小的页，而是允许节点以4K为增量进行增长，因此我们可以分配一个4K的扩展页，并从原始页链接到它。这些链接起来的页被称为溢出页（overflow page）。为简洁起见，在本节中，我们将原始页称为主页（primary page）。
大多数B树的实现最多只允许在节点中直接存储某个固定字节数量的载荷数据，并将其余字节溢出到溢出页。这个数值是通过将节点大小除以扇出得到的。使用这种方法，我们根本不会遇到页面没有可用空间的情况，因为页面总是至少具有max_payload_size个字节。有关SQLite中溢出页的更多信息，请参见SQLite源代码存储库和MySQL InnoDB文档。
当插入的数据大于max_payload_size时，检查节点是否已经具有任何相关联的溢出页。如果溢出页已经存在并且有足够的可用空间，则要写入的数据中的额外字节将会溢出到该溢出页中；否则，将分配新的溢出页。
在图4-6中，你可以看到一个主页和一个溢出页，记录从主页指向溢出页，数据在它们之上是连续的。
图4-6：溢出页
溢出页需要一些额外的记录，因为它可能会像主页一样变得碎片化，而我们必须能够通过回收空间来写入新的数据，或者在不需要溢出页时丢弃它。
当分配第一个溢出页时，其页ID存储在主页的头部。如果单个溢出页不够，则通过在前一个溢出页的头部保存下一个溢出页的ID的方式，将多个溢出页链接在一起。要查找给定的数据，我们可能不得不遍历多个溢出页。
由于键通常具有很高的基数，所以只存储键的一部分是有意义的，因为大多数比较可以通过驻留在主页中的部分截断的键来进行。
对于数据记录，我们必须定位其溢出部分，以便将其返回用户。然而，因为这是一个不那么频繁的操作，所以问题并不大。如果所有的数据记录都过大，那么值得考虑采用针对长值的blob存储。