Cache Oblivious Search Trees via Binary Trees of Small Height
Gerth Stølting Brodal
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
![]()
For storing
The basic idea of our data structure is to maintain a dynamic
binary tree of height 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. The source code of the programs, our scripts and tools, and the data we present here are available online under ftp.brics.dk/RS/01/36/Experiments/ Available as PostScript, PDF. |