Towards Data-Based Cache Optimization of B+-Trees

The rise of in-memory databases and systems with considerably large memories and cache sizes requires the rethinking of the proper implementation of index structures like B+-trees in such systems. While disk block-sized nodes and binary search were considered as good in the past, smaller node sizes and cache-friendly linear search within nodes can be noticeably more performant nowadays. Considering the probabilistic distribution of lookup values to the B+-tree as part of a memory-friendly and cache-aware layout is a consequent next step, which is studied in this paper. Favoring frequently visited nodes and paths in the regard of cache hits can improve the overall performance of the tree and, thus, of the entire database system. We provide such an optimized B+-tree layout, which takes the probabilistic distribution of the lookup values as a basis. Experimental evaluation shows that choosing rather small node sizes in combination with our optimization algorithm can improve the performance by up to in comparison to a default baseline.

  • Published in:
    International Workshop on Data Management on New Hardware
  • Type:
    Inproceedings
  • Authors:
    Kühn, Roland; Biebert, Daniel; Hakert, Christian; Chen, Jian-Jia; Teubner, Jens
  • Year:
    2023

Citation information

Kühn, Roland; Biebert, Daniel; Hakert, Christian; Chen, Jian-Jia; Teubner, Jens: Towards Data-Based Cache Optimization of B+-Trees, International Workshop on Data Management on New Hardware, 2023, https://dl.acm.org/doi/10.1145/3592980.3595316, Kuehn.etal.2023a,

Associated Lamarr Researchers

lamarr institute person Chen Jian Jia - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Prof. Dr. Jian-Jia Chen

Area Chair Resource-aware ML to the profile
lamarr institute person Teubner Jens - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Prof. Dr. Jens Teubner

Principal Investigator Resource-aware ML to the profile