Cache-Sensitive Memory Layout for Dynamic Binary Trees

Riku Saikkonen*, Eljas Soisalon-Soininen

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

Abstrakti

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.

AlkuperäiskieliEnglanti
Sivut630-649
Sivumäärä20
JulkaisuCOMPUTER JOURNAL
Vuosikerta59
Numero5
DOI - pysyväislinkit
TilaJulkaistu - 9 toukokuuta 2016
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki Sukella tutkimusaiheisiin 'Cache-Sensitive Memory Layout for Dynamic Binary Trees'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä