WROTree: Write and Range Query Optimal Tree in Persistent Memory
摘要
Persistent memory offers advantages such as byte-addressability, data persistence, and low latency. With Intel’s introduction of the eADR feature, data persistence has become much easier. However, existing ART variants in persistent memory still suffer from read/write amplification and don’t fully exploit eADR. To address these, we propose WROTree (Write and Range Query Optimal Tree): (1) We modify the traditional ART internal node structure by merging partial keys and child node pointers into a combined storage format, thereby reducing write overhead on internal nodes. (2) Leaf nodes use a bidirectional linked list, extract common key prefixes to minimize redundancy, and store the hot fingerprint array in DRAM—all to speed range queries and reduce read/write amplification. (3) It fully exploits eADR by adaptively selecting data persistence methods, thereby enhancing overall performance. Through experimental evaluation, WROTree achieves a 1.2 \(\times \) to 8 \(\times \) improvement in throughput for insertions and range queries compared to state-of-the-art ART-based persistent indexes, and the latency reduced to 0.15 \(\times \) to 0.65 \(\times \) . These results demonstrate WROTree’s superior performance in operations such as insertions, updates, and range queries.