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

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.