Cache-Efficient Balanced Search Trees Through Core Partitioning
Mahdi Amani

We introduce the core partitioning scheme, which maintains a balanced search tree as a dynamic collection of complete binary trees called cores. Using this technique we achieve the same theoretical efficiency of modern cache-oblivious data structures, but using the classic structures such as weighted balanced trees or AVL trees. We show that these “classic data structures” can be competitive to very modern ones in the cache oblivious memory model using our core partitioning scheme. We preserve the original topology and algorithms of the given balanced search tree using a simple post-processing with guaranteed performance to completely rebuild the changed cores (possibly all of them) after each update. Using our core partitioning scheme, we show how to store balanced trees such as weight-balanced trees and height-balanced trees (AVLs), so that they simultaneously achieve good memory allocation, space-efficient representation, and cache obliviousness.