EUVIMEDEUVIMED entdecken
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 · 18.05.2026 · 4 (3) · 1-26

DOI: 10.1145/3802015 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Arash Khalaji und 2 weiteren Autor:innen. Die Arbeit nennt 51 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

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}
}
Kostenlos starten →