Memory Reference Locality and Periodic Relocation in Main Memory Search Trees
K. Oksanen, Lauri Malmi · 1995
Memory reference locality is widely known to have an increasingly important effect on the performance of algorithms. We demonstrate and explain why the performance of the binary tree search algorithm varies considerably depending on how the tree is laid out in the main memory. We present an algorithm which relocates a binary tree so that maximal performance can be achieved and discuss how updates degrade the locality of the tree. 1 Introduction Binary search trees are widely used index structures in applications where the whole index can be stored in main memory. To avoid the bad worst case behaviour of these trees, various strategies have been developed to maintain them in balance. Global balancing algorithms periodically rebuild the whole tree [3, 9, 15]. Balanced trees, e.g. AVL-trees and red-black trees, perform rebalancing coupled with each update operation [1, 5, 6, 8, 11, 13]. These data structures and algorithms were developed and analyzed assuming the Random Access Memo...