Cache Oblivious Search Trees via Binary Trees of Small Height

Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob

Technical Report, BRICS-RS-01-36, BRICS, Department of Computer Science, Aarhus University, 20 pages, October 2001.

Abstract

We propose a version of cache oblivious search trees which is simpler than the previous proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In particular, our data structure avoids the use of weight balanced B-trees, and can be implemented as just a single array of data elements, without the use of pointers. The structure also improves space utilization.

For storing n elements, our proposal uses (1+ε)n times the element size of memory, and performs searches in worst case O(logB n) memory transfers, updates in amortized O((log2 n)/(ε B)) memory transfers, and range queries in worst case O(logB n + k/B) memory transfers, where k is the size of the output.

The basic idea of our data structure is to maintain a dynamic binary tree of height log n+O(1) using existing methods, embed this tree in a static binary tree, which in turn is embedded in an array in a cache oblivious fashion, using the van Emde Boas layout of Prokop.

We also investigate the practicality of cache obliviousness in the area of search trees, by providing an empirical comparison of different methods for laying out a search tree in memory.

Copyright notice

Copyright © 2001, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-01-36.pdf (313 Kb)

Note

The source code of the programs, our scripts and tools, and the data we present: brics-rs-01-36-experiments.tgz.

BIBTEX entry

@techreport{brics-rs-01-36,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Riko Jacob",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "October",
  number = "BRICS-RS-01-36",
  pages = "20",
  title = "Cache Oblivious Search Trees via Binary Trees of Small Height",
  year = "2001"
}