CPA: Practical Cache-Oblivious B-Trees

实用的与缓存无关的b树30多年来，b树一直是在磁盘上维护可搜索、有序数据的首选数据结构。这样的b树有时被称为“缓存感知的”b树，因为它们能够感知内存层次结构中的特定块大小（如磁盘块大小），并对其进行优化。相反，最近的理论结果表明，原则上如何构建一个“缓存无关”的b树，它可以同时优化所有块大小，而无需显式测量或调优。尽管最近的实验表明，对于任何给定的块大小，缓存无关b树的性能都优于缓存感知b树，有时甚至高出两个数量级，但缓存无关b树还不实用。本项目旨在了解如何在实践中实现与缓存无关的b树的理论承诺。构建一个实用的缓参无关搜索树库是一个困难的系统工程问题。现有的设计是复杂的，缺乏并发性。它们提供平摊性能保证，而不是最坏情况下的性能保证。它们不支持数据库和文件系统所需的事务语义。通过将理论见解与现代软件技术（如内存映射）相结合，该研究项目希望为无关缓存的搜索树提供一个实用的库，以提供可证明的性能保证。

Practical Cache-Oblivious B-Trees For over three decades, the B-tree has been the data structure of choice for maintaining searchable, ordered data on disk. Such B-trees are sometimes referred to as "cache-aware" B-trees because they are aware of, and optimize for, one particular block size (such as the disk block size) in the memory hierarchy. In contrast, recent theoretical results show how, in principle, to build a "cache-oblivious" B-tree, which simultaneously optimizes for all block sizes with no explicit measurement or tuning. Although recent experiments show that cache-oblivious B-trees can outperform cache-aware B-trees for any given block size, sometimes by two orders of magnitude, cache-oblivious B-trees are not yet practical. This project aims to understand how the theoretical promise of cache-oblivious B-trees can be realized in practice. Building a practical library for cache-oblivious search trees is a difficult systems engineering problem. Existing designs are complex and lack concurrency. They provide amortized performance guarantees rather than worst-case performance guarantees. They do not support the transactional semantics required by databases and file systems. By combining theoretical insights with modern software technology, such as memory mapping, this research project hopes to provide a practical library for cache-oblivious search trees that offers provable guarantees of performance.