Cache-oblivious streaming B-trees
Cache-oblivious streaming B-trees
复制标题
DOI：
10.1145/1248377.1248393
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
M. A. Bender;Martín Farach-Colton;Jeremy T. Fineman;Yonatan R. Fogel;Bradley C. Kuszmaul;Jelani Nelson
中科院分区：
文献类型：
--
作者：
M. A. Bender;Martín Farach-Colton;Jeremy T. Fineman;Yonatan R. Fogel;Bradley C. Kuszmaul;Jelani Nelson
流B树是一种有效实现插入和范围查询的字典。我们提出了两个高速缓存无关流B树，穿梭树，和高速缓存无关前瞻阵列（COLA）。对于块传输大小B和N个元素，穿梭树在最优O（log B+1 N）传输，L个连续元素的范围查询在最优O（log B+1 N +L/B）传输，以及O中的插入（（log B+1N）/BΘ（1/（log log B）2）+（log 2N）/B）传输，如果对于任何常数c >1，B ≥（log N）1+c log log log 2 N，则这是对传统B树的渐近加速。COLA在O（log N）传输中实现搜索，在O（log N + L/B）传输中实现范围查询，在分期O（（log N）/B）传输中实现插入，匹配（缓存感知）缓冲存储库树的边界。部分摊销的COLA匹配这些界限，但如果内存大小M = Ω（log N），则将最坏情况下的插入成本降低到O（log N）。我们还提出了一个缓存感知版本的COLA，前瞻数组，它实现了相同的边界Brodal和Fagerberg的（缓存感知）Bε树。我们比较我们的COLA实现传统的B树。我们的COLA实现在随机插入时运行速度快790倍，在排序数据插入时慢3.1倍，在搜索时慢3.5倍。
A streaming B-tree is a dictionary that efficiently implements insertions and range queries. We present two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious lookahead array (COLA). For block-transfer size B and on N elements, the shuttle tree implements searches in optimal O(log B+1N) transfers, range queries of L successive elements in optimal O(log B+1N +L/B) transfers, and insertions in O((log B+1N)/BΘ(1/(log log B)2)+(log2N)/B) transfers, which is an asymptotic speedup over traditional B-trees if B ≥ (log N)1+c log log log2 N for any constant c >1. A COLA implements searches in O(log N) transfers, range queries in O(log N + L/B) transfers, and insertions in amortized O((log N)/B) transfers, matching the bounds for a (cache-aware) buffered repository tree. A partially deamortized COLA matches these bounds but reduces the worst-case insertion cost to O(log N) if memory size M = Ω(log N). We also present a cache-aware version of the COLA, the lookahead array, which achieves the same bounds as Brodal and Fagerberg's (cache-aware) Bε-tree. We compare our COLA implementation to a traditional B-tree. Our COLA implementation runs 790 times faster for random inser-tions, 3.1 times slower for insertions of sorted data, and 3.5 times slower for searches.