Efficient management of spatial data is essential for applications such as navigation, urban planning, and location-based services. With the rapid growth of spatial data volume and complexity, traditional storage solutions like SSDs are increasingly inadequate in meeting the performance demands of such workloads. Persistent Memory (PMEM) emerges as a promising alternative, offering low latency, high throughput, and byte-addressable access, while retaining data even after power loss. These characteristics make PMEM particularly attractive for spatial indexing structures such as the R-Tree, which are central to spatial data management. However, existing R-Tree implementations on PMEM-such as FBR using mutex-based synchronization and PMR using PMwCAS-suffer from scalability bottlenecks in multi-threaded environments. Mutex-based synchronization introduces significant contention, while PMwCAS provides only partial lock-freedom and incurs non-negligible overhead. To address these limitations, we propose TSR (Test and Set based R-Tree), an effective synchronization method based on Test-and-Set (TAS) instructions. By applying TAS at the node level, TSR minimizes contention and enables higher concurrency during insert operations. We have conducted extensive experiments using real PMEM hardware and demonstrate that TSR outperforms both FBR and PMwCAS in terms of insertion throughput and scalability. At eight threads, TSR improves throughput by up to 66% compared to FBR and 44% over PMwCAS. Our contributions are threefold: (1) we demonstrate the performance advantage of PMEM over SSDs in spatial indexing workloads; (2) we propose a TAS-based synchronization method that achieves better thread scalability; and (3) we provide a comprehensive performance analysis of R-Tree implementations under different synchronization strategies on PMEM.
Yoshioka et al. (Thu,) studied this question.