{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 and .We design a new persistent index, ROART, based on adaptive radix tree (ART), taking all these practical aspects into account. ROART (i) proposes a method to reduce pointer chasing for range queries, (ii) minimizes persistence overhead with three optimizations, i.e., , and , and (iii) designs a fast memory management to prevent memory leaks, and eliminates the long recovery time by proposing an 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.