Collaborative Research: High-Performance Data Access through Memory Abstraction

几十年来，b树一直是外部内存搜索的首选数据结构，因为它们可以最大限度地减少搜索过程中执行的磁盘块访问数量。然而，众所周知，b树在经验上不是最优的，因为它们只在一个粒度级别（通常是磁盘块）上利用数据局部性，而不是在更粗的粒度（如磁盘轨道）或更细的粒度（如缓存线）上利用数据局部性。关于缓存无关数据结构和算法的理论发展已经展示了如何在每个粒度同时实现几乎最优的引用局部性。与缓存无关的数据结构的一个显著特性是，它们将程序员从为缓存和磁盘效果调优代码的负担中解放出来。pi最近的实验表明，缓存无关b树（CO b树）的性能可以超过高度调优的传统b树。CO b树实现了卓越的性能，因为它们对所有内存效果进行了近似优化。相比之下，缓存感知算法忽略了内存层次结构的重要方面。但是，CO b -树还不能用于文件系统和数据库，因为它们缺乏工业级b -树的基本功能，例如支持可变大小的键、并发访问和事务。研究人员建议研究CO b树如何发挥其潜力。研究人员计划研究数据结构、弦学和分布式系统中广泛的算法问题，以开发功能齐全的CO b树。此外，研究人员计划解决在线调度问题，以便虚拟内存系统可以为缓存遗忘提供有效的支持。这种算法工作对于将CO技术转移到计算机科学、工程和科学计算的其他领域是必要的，并且旨在改变科学家和工程师如何操作大量数据集。

ABSTRACT: High-Performance Data Access through Memory Abstraction B-trees have been the data structures of choice for external-memory searching for decades because they minimize the number of disk-block accesses performed during a search. It is well known, however, that B-trees are empirically suboptimal because they exploit data locality at only one level of granularity, typically disk blocks, but not at coarser granularities, such as disk tracks, or finer granularities, such as cache lines. Theoretical developments on cache-oblivious data structures and algorithms have shown how to achieve nearly optimal locality of reference simultaneously at every granularity. A striking feature of cache-oblivious data structures is that they free the programmer from the burden of tuning the code for cache and disk effects. The PIs' recent experiments suggest that cache-oblivious B-trees (CO B-trees) can surpass the performance of highly tuned traditional B-trees. CO B-trees achieve superior performance because they approximately optimize for all memory effects. In contrast, cache-aware algorithms ignore important aspects of the memory hierarchy. CO B-trees are not yet ready to be used in file systems and data bases, however, because they lack essential capabilities of industrial-strength B-trees, such as support for variable-size keys, concurrent accesses, and transactions. The researchers propose to investigate how CO B-trees can achieve their potential. The researchers plan to study the wide range of algorithmic problems in data structures, stringology, and distributed systems required to develop a full-featured CO B-tree. In addition, the researchers plan to solve online scheduling problems so that virtual-memory systems can provide efficient support for cache-obliviousness. This algorithmic work is necessary to transfer CO technology to other areas of computer science, engineering, and scientific computing and is intended to transform how scientists and engineers manipulate massive data sets.