下载掌阅APP，畅读海量书库
立即打开
到目前为止，我们主要讨论的是B树中面向用户的操作。但是，在查询的同时还会发生一些其他的过程，包括维护存储完整性、回收空间、减少开销以及维持页有序。在后台执行这些操作可以使我们节省一些时间，避免在插入、更新和删除期间为清理付出代价。
之前描述过的分槽页的设计（参见3.5节）需要在页上执行维护操作，以维持其良好的形态。例如，内部节点中后续的分裂和合并，或叶子层上的插入、更新和删除，可能导致页中有足够的逻辑空间但没有足够的连续空间，因为它已经碎片化了。图4-11展示了这种情况的一个例子：页中仍然有一些可用的逻辑空间，但是它是碎片化的并且被两个已删除的（垃圾）记录分割开来，在头部/单元格指针和单元格之间也有一些剩余的可用空间。
图4-11：一个碎片化页的例子
B树的遍历始于根节点。如果一条数据记录可以通过从根节点向下追踪指针到达，那么称它为存活的（即可寻址的）。而不可寻址的数据记录则称为垃圾数据：这些记录没有被任何地方引用，也不能被读取或解释，因此它们的内容是作废的。
你可以在图4-11中看到这一区别：仍然具有指向它们的指针的单元格是可寻址的，而这便与已移除或覆盖的单元格不同。由于性能，通常不会对垃圾区域进行填零操作，因为这些区域最终还是会被新数据所覆盖。
让我们考虑一下在什么情况下页会进入这样一种状态：页包含无法寻址的数据，并且不得不进行压实（compact）。在叶子层上，删除操作仅从头部移除单元格偏移量，而单元格本身保持不变。在这样做之后，对应的单元格不再是可寻址的，它的内容将不再出现在查询结果中，也不需要将其置为null或移动相邻单元格。
当页被分裂时，只对偏移量进行调整。由于页的其余部分不可寻址，所以偏移量被截断的单元格不再可访问，因此每当新数据到达时，它们将被覆盖，或者在清扫进程中被垃圾收集。
有些数据库依赖于垃圾收集，并将已删除和更新的单元格留在原位，以便进行多版本并发控制（参见5.3.6节）。在更新完成之前，单元格对于并发执行的事务保持可访问性，一旦没有其他线程访问它们，就可以立即回收单元格。一些数据库维护跟踪幽灵记录（ghost record）的数据结构，一旦所有可能已经看到它们的事务完成，这些幽灵记录就会被回收[WEIKUM01]。
由于删除操作仅丢弃单元格偏移量，而非搬运剩余单元格或物理地移除目标单元格以释放占用的空间，所以释放的字节可能最终分散在整个页上。在这种情况下，我们说页是碎片化的（fragmented），需要进行碎片整理。
要进行写操作，我们通常需要可以放入单元格的一块连续的空闲区域。要将空闲碎片重新组合在一起来满足写入的需要，我们必须重写页面。
插入操作保留元组的插入顺序。这对空间碎片并没有显著的影响，但是如果将元组按顺序排列，则将有助于在顺序读取时进行高速缓存预取。
更新操作主要适用于叶子层：内部页的键多用于引导导航，其仅定义了子树的边界。此外，更新是在每个键的基础上执行的，除非创建溢出页，否则这通常不会导致树中的结构更改。然而，在叶子层上，更新操作不会改变单元格顺序，并会试图避免页重写。这意味着，虽然单元格的多个版本中只有一个能被寻址，但是可能最后所有版本都被保存了。
负责空间回收和页重写的过程称为压实（compaction）、清扫（vacuum）或直接称为维护（maintenance）。如果页中没有足够的物理可用空间，则可以在写入时同步进行页重写（以避免创建不必要的溢出页），但压实通常是指一个单独的异步过程，负责遍历页、进行垃圾回收并重写其内容。
这个过程回收死亡的单元格所占用的空间，并按逻辑顺序重写单元格。当页被重写时，它也可能被移动到文件中的新位置。未使用的内存页变为可用状态并归还至页缓冲区。新的可用磁盘页的ID被添加到空闲页列表（free page list，有时称为空闲列表（freelist
））中。这些信息必须被持久化，才能在节点崩溃和重启时幸存下来，并确保可用空间不会丢失或泄露。