Cache-Sensitive Memory Layout for Dynamic Binary Trees

We use cache-sensitive memory layouts to improve search performance in ordinary binary search trees, without increasing the time complexity of insertion or deletion. Our approach does not require changes to the structure of the nodes or the rebalancing strategy of the tree. Cache-sensitivity is maintained with a memory-layout invariant that keeps a given number of neighboring nodes in the tree stored in the same cache block. We show how to preserve it using worst-case constant-time operations executed when the tree changes. In our extensive experiments, the invariant consistently improved the search performance of large AVL and red-black trees by 26-32%, on synthetic data as well as realistic search tree operations extracted from a database benchmark. We also compare binary search trees with several cache-sensitive B-trees, and non-dynamic approaches for laying out tree nodes in a multi-level memory hierarchy.