Chapter 6

B-Tree Variants

B-Tree 的变种有一些共同的属性：树状结构，通过分裂跟合并来保持平衡，类似的查找跟插入算法。其他像并发控制、磁盘页的表现形式、相邻节点间的连接、维护的处理等实现，可能会有较大的差异。

在本章我们会讨论数种可以用来实现高效 B-Tree 的技术及具体的实现结构：

• Copy-on-write B-Trees 是一种跟 B-Tree 类似的数据结构，但是他们具有不可变的节点，因此不能够进行就地更新。相反的，他们的页会被复制、更新跟写入新的位置
• Lazy B-Trees 通过对同一个节点的接连的写入缓存到节点中来减少磁盘 I/O 的数量，在下一章中我们还会讨论 two-component LSM trees 这个使用更多缓存来实现的完全不可变的 B-Trees
• FD-Trees 使用了另一种不同的缓存方式，类似 LSM Trees，FD-Trees 更新一个更小的 B-Trees，在这棵树被填满时，他的内容会被马上写入到不可变 Run。更新会被从高层级的不可变 Run 向更低的层级的不可变 Run 传递。
• Bw-Trees 将 B-Tree 的节点分割为多个更小的部分以只添加的方式写入，通过将多个不同节点的写操作合并来减少小数据写入的开销。
• Cache-oblivious B-Trees 能够以类似构建内存数据结构的方式来处理基于磁盘的数据结构。