Optimal Hierarchical Layouts for Cache-Oblivious Search Trees

Peter Lindstrom, Deepak Rajan

This paper proposes a general framework for generating cache-oblivious layouts for binary search trees. A cache-oblivious layout attempts to minimize cache misses on any hierarchic…