Polytechnic University

This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache oblivious and locality preserving. A cache-oblivious data struc-ture has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specic parameterization. A locality-preserving dictionary main-tains elements of similar key values stored close together for fast access to ranges of data with consecutive keys. The data structure presented here is a simplication of the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton. Like the cache-oblivious B-tree, this structure supports search operations using only O(log B N) block operations at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(log B N + log 2 N=B) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(log