权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CPA: Practical Cache-Oblivious B-Trees

CPA：实用的忽略缓存的 B 树

基本信息

批准号：
0541209
负责人：
Charles Leiserson
金额：
$ 27.5万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2006
资助国家：
美国
起止时间：
2006-08-15 至 2009-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0541209&HistoricalAwards=false
关键词：
CPA Practical Cache Oblivious Trees

项目摘要

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.

实用的缓存不经意B树在过去的三十年里，B树一直是在磁盘上维护可搜索的、有序的数据的数据结构的选择。这种B树有时被称为“缓存感知”B树，因为它们感知内存层次结构中的一个特定块大小（例如磁盘块大小）并对其进行优化。相比之下，最近的理论结果表明，在原则上，如何建立一个“缓存无关”的B树，同时优化所有块大小，没有明确的测量或调整。尽管最近的实验表明，对于任何给定的块大小，缓存无关B-树都可以优于缓存感知B-树，有时是两个数量级，但缓存无关B-树还不实用。这个项目旨在了解如何在实践中实现缓存无关B树的理论承诺。建立一个实用的缓存无关搜索树库是一个困难的系统工程问题。现有的设计复杂且缺乏并发性。它们提供的是摊销后的业绩担保，而不是最坏情况下的业绩担保。它们不支持数据库和文件系统所需的事务语义。通过将理论见解与现代软件技术（如内存映射）相结合，该研究项目希望为缓存无关搜索树提供一个实用的库，提供可证明的性能保证。