Cache-Oblivious Streaming B-Trees
View/ Open
Author
Bender, Michael A.
Farach-Colton, Martin
Fineman, Jeremy T.
Fogel, Yonatan R.
Kuszmaul, Bradley C.
Published Version
https://doi.org/10.1145/1248377.1248393Metadata
Show full item recordCitation
Bender, Michael A, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley C. Kuszmaul, and Jelani Nelson. 2007. "Cache-oblivious streaming B-trees." In Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '07, June 9-11, 2007, San Diego, CA: 81-92. New York, NY: ACM.Abstract
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+1}N)\) transfers, range queries of L successive elements in optimal \(O(log_{B+1}N +L/B)\) transfers, and insertions in \(O((log_{B+1}N)/B^{\Theta(1/(log log B)^2)}+(log^2N)/B)\) transfers, which is an asymptotic speedup over traditional B-trees if \(B ≥ (log N)^{1+c log log log^2 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 = \Omega(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^{\epsilon}\)-tree. We compare our COLA implementation to a traditional B-tree. Our COLA implementation runs 790 times faster for random insertions, 3.1 times slower for insertions of sorted data, and 3.5 times slower for searches.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:13826440
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)