ROART: Range-query Optimized Persistent ART
summary
ROART is a persistent index built on adaptive radix tree that implements leaf compaction to store up to 64 leaves in a contiguous array, reducing pointer chasing for range scans, and applies entry compression, selective metadata persistence, and minimally ordered splits to cut flush/fence overhead. It ships a two-layer allocator DCMM using postcard-GC plus an instant restart recovery so allocation stays fast and recovery runs concurrently. Evaluations show ROART outperforms a state-of-the-art radix tree by up to 1.65x and B+-Trees by 1.17–8.27x.
AI-written summary · about
chapters (14)
- 0:00Start
- 0:33Persistent Indexes
- 0:52Motivations
- 1:20Functionality Range queries support
- 4:27Correctness—Memory Safety
- 5:50Performance of Allocators
- 6:31Design Choices
- 7:06Leaf Compaction
- 7:37More on Performance
- 7:59Making ROART Correct
- 9:25Instant Restart
- 10:48Performance Breakdown
- 11:07Range Query Performance
- 11:21Conclusion
related talks
17mArctic: A Practical Lock-Free Adaptive Radix Tree
15m"Range as a Key" is the Key! Fast and Compact Cloud Block Store Index with RASK
50mPostgreSQL meets ART - Using Adaptive Radix Tree to speed up vacuuming
23mSRFI-167, SRFI-168 and the functional store
17mA New Radix-Tree Based Memory Storage Engine
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
20mBridging the Gap between Relational OLTP and Graph-based OLAP
38mLight and Adaptive Indexing for Immutable Databases