Log-Compact R-Tree: An Efficient Spatial Index for SSD

R-Tree structure is widely adopted as a general spatial index with the assumption that the deployed system is equipped with magnetic hard disk. While the application of SSD becomes more and more popular, traditional optimization of R-Tree structure on SSD is much less desirable than that on magnetic hard disk. Existing flash-aware index approaches employ log mechanism to reduce random writes at a cost of large amount of read. A novel index named Log Compact R-Tree (LCR-tree) is proposed in this paper. Distinguished from previous attempts, compacted log is introduced to combine newly arrival log with origin ones on the same node, which renders great decrement of random writes with at most one additional read for each node access. Extensive experiments illustrate that the proposed LCR-Tree can achieve up to 3 times benefit against existing approaches.