R-tree is a popular dynamic spatial index structure in spatial databases. The traditional R-tree is easily constrained by the limited DRAM capacity when facing massive-scale spatial data today, making it difficult to achieve low latency. Emerging persistent memory (PM) offers DRAM-scale latency, byte addressability, large capacity, and low cost, bringing new opportunities for R-tree. However, integrating R-tree into PM has the following challenges:(1)PM has different access characteristics from DRAM, it has higher latency and different access granularity. (2) The overhead of persistent instructions is high, especially during split. (3) The overhead of concurrency control cannot be ignored, especially in PM-based systems. In this paper, we propose HR-tree, a hybrid PM-DRAM R-tree to address the challenges above. HR-tree uses a collaborative PM-DRAM approach to minimize the read and write operation costs on PM while ensuring recoverability. It employs a write coalescing mechanism during split and selective persistence for leaf nodes to minimize persistence overhead. Finally, HR-tree proposes a lightweight concurrent control strategy to reduce locking overhead. Experimental results with the real-world datasets show that the HR-tree outperforms the state-of-the-art PM-based R-tree(FBR-tree) and hybrid FBR-tree by up to 3.2 \(\times \) and 1.4 \(\times \) , respectively.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

HR-Tree: A Hybrid PMem-DRAM and Write-Optimized R-Tree for Spatial Data Storage

  • Rui Zhang,
  • Yukai Huang,
  • Lulu Chen,
  • Shangyi Sun,
  • Ming Yan,
  • Jie Wu

摘要

R-tree is a popular dynamic spatial index structure in spatial databases. The traditional R-tree is easily constrained by the limited DRAM capacity when facing massive-scale spatial data today, making it difficult to achieve low latency. Emerging persistent memory (PM) offers DRAM-scale latency, byte addressability, large capacity, and low cost, bringing new opportunities for R-tree. However, integrating R-tree into PM has the following challenges:(1)PM has different access characteristics from DRAM, it has higher latency and different access granularity. (2) The overhead of persistent instructions is high, especially during split. (3) The overhead of concurrency control cannot be ignored, especially in PM-based systems. In this paper, we propose HR-tree, a hybrid PM-DRAM R-tree to address the challenges above. HR-tree uses a collaborative PM-DRAM approach to minimize the read and write operation costs on PM while ensuring recoverability. It employs a write coalescing mechanism during split and selective persistence for leaf nodes to minimize persistence overhead. Finally, HR-tree proposes a lightweight concurrent control strategy to reduce locking overhead. Experimental results with the real-world datasets show that the HR-tree outperforms the state-of-the-art PM-based R-tree(FBR-tree) and hybrid FBR-tree by up to 3.2 \(\times \) and 1.4 \(\times \) , respectively.