ROART: Range-query Optimized Persistent ART

With the availability of commercial NVM devices such as Intel Optane DC PMM, it is time to start thinking about applying the existing persistent data structures in practice. This paper considers three practical aspects, which have significant influences on the design of persistent indexes, including functionality, performance and correctness.

We design a new persistent index, ROART, based on adaptive radix tree (ART), taking all these practical aspects into account. ROART (i) proposes a leaf compaction method to reduce pointer chasing for range queries, (ii) minimizes persistence overhead with three optimizations, i.e., entry compression, selective metadata persistence and minimally ordered split, and (iii) designs a fast memory management to prevent memory leaks, and eliminates the long recovery time by proposing an instant restart strategy. Evaluations show that ROART outperforms the state-of-the-art radix tree by up to 1.65x and B⁺-Trees by 1.17∼8.27x respectively.