Right-Only Appends

许多的数据库系统使用单调递增的值来作为主要索引的 Key,这为优化提供了一个机会,因为所有的插入操作都会发生在索引的末端 (即最右子节点),所以大部分的分裂也都只会发生在每一个层级的最右端。此外,因为 Key 是单调递增的,假定删除跟删除操作的比例比较低,所以非叶子节点相对于随机的无序 Key 来说会产生更少的碎片。

PostgreSQL 将这种场景称为 faskpath。当插入的 Key 严格大于最右测的页的第一个 Key 且左右侧的页有足够的空间来保存新插入的实体时,新的实体会被直接插入到已缓存的最右侧叶子节点中,因此插入操作可以完全跳过对树路径的读取。

SQLite 也有类似的称为 quickbalance 的概念,当插入的实体足够靠右的一侧并且目标节点是满的 (即称为整棵树中最大的实体),他并不会触发重平衡或分裂节点的操作,而是会分配一个新的最右侧节点,并为父节点添加指向他的指针。 (SQLite 更多实现平衡的方式可以参考 Rebalancing 章节) 尽管这个新添加的页几乎处于空的状态 (相对于分裂产生的半满节点来说),但他很有可能会很快的又被填满了。

Bulk Loading

如果我们有预先排好序的数据并且想进行批量的读取,或者需要重新构建树时 (比如进行碎片整理),可以从 Right-Only Append 的想法中走的更远一点。因为要保存到树中的数据已经是有序的,在批量读取时我们只需要将数据添加到树的最右侧的位置。

在这个场景,我们可以完全避免分裂跟合并,使用自底向上,逐层写入或在当前层有足够的指针数时马上写入其上层节点的方式来构建整棵树。

其中一个实现批量读取的方法是将预先排好序的数据逐页写入叶子节点 (而不是单独的逐个插入元素)。在写完所有的叶子节点后,我们将他的第一个 Key 上升到父节点,然后使用常规的方法来构建更层次的级别。因为添加的 Key 是有序的,所有的分裂操作都只会发生在最右侧节点。

因为 B-Tree 始终是从最底层 (叶子层) 进行构建的,所以可以在构建任何更高级别的节点前完成所有叶子节点。让让我们可以在构建更高级别的节点前,先持有所有叶子的指针信息。这种方式的优点是我们不需要处理任何基于磁盘的分裂跟合并操作。与此同时,只需要在内存中保存当前需要的跟树相关的最少信息 (比如当前填充中叶子节点的所有的父节点)

不可变的 B-Tree 可以用相同的方式来构建,但是,跟可变的 B-Tree 不同的地方在于,他不需要额外的空间开销来处理后续的修改操作,因为现在对树的所有操作都是最终的版本。所有的页可以完全的填满,提高使用率并带来更高的性能。