We implemented a cache-oblivious dynamic search tree as
an alternative to the ubiquitious B-tree. We used a binary tree
with a "van Emde Boas" layout whose leaves point to intervals
in a "packed memory structure". The search tree supports
efficient lookup, as well as efficient amortized insertion
and deletion. Efficient implementation of a B-tree requires
understanding the cache-line size and page size and is
optimized for a specific memory hierarchy. In contrast, a
cache-oblivious dynamic search tree contains no
machine-dependent variables, performs well on any memory
hierarchy, and requires minimal user-level memory management.
For random insertion of data, the data structure performs
better than the Berkeley DB and a good implementation of
B-trees. Another advantage of my data structure is that
the packed memory array maintains data in sorted order,
allows sequential reads at high speeds, and data insertions
and deletions with few data writes on average. In addition,
the data structure is easy to implement because he employed
memory mapping rather than making the data stored on disk be
a single level store.
We also have designed cache-oblivious search trees
for which the keys can be very long (imagine a key,
such as a DNA sequence, that is larger than main
memory), and trees into which data can be quickly
inserted.
|
|
Cache-Oblivious Streaming B-trees
by Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley Kuszmaul, and Jelani Nelson
Proceedings of the Nineteenth ACM Symposium on Parallelism in Algorithms and Architectures
San Diego, CA, USA
Pages: 81–92
June 9–11,
2007
To download the paper:
ps format
pdf format
BibTeX
|
Cache-Oblivious String B-Trees
by Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul
Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Chicago, IL
Pages: 223–242
June,
2006
To download the paper:
pdf format
BibTeX
|
|
Concurrent Cache-Oblivious B-Trees
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul
Proceedings of the Seventeenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Las Vegas, NV, USA
Pages: 228–237
July 17–20,
2005
To download the paper:
ps format
pdf format
BibTeX
|
Cache-Oblivious Dynamic Search Trees
by Zardosht Kasheff
Master's Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
June,
2004
To download the paper:
pdf format
BibTeX
|
|
Cache-Oblivious Algorithms
by Harald Prokop
Master's Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
June,
1999
To download the paper:
ps format
pdf format
BibTeX
|
|