Skip to Main content Skip to Navigation
Reports

On optimizing scalar self-rebalancing trees

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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-02573052
Contributor : Paul Iannetta <>
Submitted on : Thursday, May 14, 2020 - 9:42:38 AM
Last modification on : Wednesday, October 14, 2020 - 4:21:51 AM

File

RR-9343.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02573052, version 1

Collections

Citation

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, pp.15. ⟨hal-02573052⟩

Share

Metrics

Record views

94

Files downloads

336