On optimizing scalar self-rebalancing trees - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2020

On optimizing scalar self-rebalancing trees

(1, 2, 3) , (1, 2, 3) , (4, 5)
1
2
3
4
5

Abstract

Balanced trees are pervasive and very often found in databases or other systems which are built around querying non-static data. In this paper, we show that trees implemented as a collection of pointers shows bad data locality, poor cache performance and suffer from a lack of parallelism opportunities. We propose an alternative implementation based on arrays. Both implementations appear to be equivalently efficient time-wise. This new layout exposes new parallelism opportunities which can be then exploited by an optimizing polyhedral compiler.
Fichier principal
Vignette du fichier
RR-9343.pdf (897.03 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02573052 , version 1 (14-05-2020)

Identifiers

  • HAL Id : hal-02573052 , version 1

Cite

Paul Iannetta, Laure Gonnord, Lionel Morel. On optimizing scalar self-rebalancing trees. [Research Report] RR-9343, ENS LYON; Inria - Research Centre Grenoble – Rhône-Alpes; Université de Lyon I Claude Bernard. 2020. ⟨hal-02573052⟩
284 View
213 Download

Share

Gmail Facebook Twitter LinkedIn More