Cache-Sensitive Memory Layout for Dynamic Binary Trees

Riku Saikkonen*, Eljas Soisalon-Soininen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)630-649
Number of pages20
JournalCOMPUTER JOURNAL
Volume59
Issue number5
DOIs
Publication statusPublished - 9 May 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • Binary search trees
  • cache-conscious data structures
  • experiments

Fingerprint Dive into the research topics of 'Cache-Sensitive Memory Layout for Dynamic Binary Trees'. Together they form a unique fingerprint.

Cite this