Cache-oblivious streaming B-trees

Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, Jelani Nelson

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 log2N 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.

    Original languageEnglish (US)
    Title of host publicationSPAA'07
    Subtitle of host publicationProceedings of the Nineteenth Annual Symposium on Parallelism in Algorithms and Architectures
    Number of pages12
    StatePublished - 2007
    EventSPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures - San Diego, CA, United States
    Duration: Jun 9 2007Jun 11 2007

    Publication series

    NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures


    OtherSPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures
    Country/TerritoryUnited States
    CitySan Diego, CA


    • Buffered repository tree
    • Cache-oblivious B-tree
    • Cascading array
    • Deamortized
    • Lookahead array
    • Shuttle tree

    ASJC Scopus subject areas

    • General Engineering


    Dive into the research topics of 'Cache-oblivious streaming B-trees'. Together they form a unique fingerprint.

    Cite this