EUVIMEDObjevte EUVIMED
Crossref

ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries

Arash Khalaji, Trevor Brown, Khuzaima Daudjee

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-26

DOI: 10.1145/3802015 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Arash Khalaji and 2 co-authors. 51 references.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

Indexes are essential for efficient query processing in database systems, with ordered indexes particularly suited for supporting range queries. Non-volatile memory (NVM) technology offers fast, byte-addressable access and persistence across system failures, enabling rapid recovery without costly index reconstruction. While recent efforts have focused on building durable NVM-based indexes for point queries and updates, they often lack efficient support for concurrent range queries with correctness. We present PermART, a persistent, versioned adaptive radix tree that surpasses current NVM-based indexes in point query and update performance and supports efficient, consistent, range queries under concurrency. By integrating multiversioning into ART, we enable efficient, linearizable range queries while improving point operation performance through in-node logging. Our evaluation shows that our persistent ART matches or exceeds the performance of current NVM-based indexes for point queries and updates, while offering correct, linearizable range queries, which existing indexes do not provide.

Cite

APA

Khalaji, A., Brown, T., & Daudjee, K. (2026). ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802015

Vancouver

Khalaji A, Brown T, Daudjee K. ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802015

BibTeX
@article{Khalaji2026,
  author = {Khalaji, Arash and Brown, Trevor and Daudjee, Khuzaima},
  title = {ART That Lasts: Persistent Multiversion Adaptive Radix Trees with Fast Atomic Range Queries},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3802015}
}
Start for free →