OR-Tree: An Optimized Spatial Tree Index for Flash-Memory Storage Systems

Nowadays, flash memory is widely used in various portable devices such as PDAs (personal digital assistants) and HPCs (handheld PCs). With the development of location-based services (LBS) provided by those portable devices, how to provide efficient spatial data management over flash-equipped LBS devices has become a critical issue in recent years. In this paper, we aim to propose an efficient flash-optimized spatial tree index, called OR-tree, to improve the queries and updates on flash-resident spatial data. The OR-tree is based on R-tree and introduces two new techniques to make the R-tree suitable for flash memory storage system. First, we employ a lazy node splitting policy by introducing overflow nodes for the leaf nodes in R-tree. Next, we redesign the algorithms of update operations to adapt the unbalanced OR-tree structure. To evaluate the performance of the OR-tree, we conduct experiments on a spatial data set gathered from the R-tree portal. We run different workloads and compare the OR-tree with other competitors on the basis of different metrics including flash page usage, flash write count, erasure count, and runtime. The experimental results show that the OR-tree outperforms the competitors considering both space efficiency and time performance.