Cache-oblivious dynamic search trees

I have implemented a cache-oblivious dynamic search tree as an alternative to the ubiquitious B-tree. I use a binary tree with a "van Endcle Boas" layout whose leaves point to intervals in a "packed memory structure". We refer to the data structure as a COB-Tree. The COB-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, the COB-Tree contains no machine-dependent variables, performs well on any memory hierarchy, and requires minimal user-level memory management. For random insertion of data, my data structure performs 7.5 times faster than the Berkeley DB and 3 times faster than a memory mapped implementation of B-trees. The packed memory array of the COB-Tree 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 I employed memory mapping rather than explicit file operations.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Kasheff, Zardosht, 1981-

Advisor dc:contributor.advisor

• Bradley Kuszmaul.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/28417

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/28417