CPA: Practical Cache-Oblivious B-Trees

实用缓存无关B-树三十多年来，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.