Optimizing R-tree for flash memory

R-tree has been widely used in spatial data management and data analysis to improve the performance of spatial data retrieval. However, the original R-tree is designed for magnetic disks, and has poor performance on flash memory, due to the special features of flash memory such as asymmetric read! write speeds (fast read, slow write) and the erase-before-write feature. Particularly, the original updating mechanism of R-tree usually has to update a few interior nodes when inserting an indexing item into or deleting an item from a leaf node, yielding many slow writes to flash memory. With the wide use of flash memory in many location-based fields, e.g., to store moving trajectories in intelligent transportation systems, how to optimize R-tree for flash memory has become a critical issue. In this paper, we propose a novel spatial index named Flash-Optimized R-tree that is optimized for flash memory. In particular, we propose to defer the node-splitting operations on R-tree by introducing overflow nodes, which results in an unbalanced tree structure. With this mechanism, we can reduce random writes to flash memory and improve the overall performance of R-tree. In addition, we present a new buffering scheme to efficiently cache the updates to the tree, which can further reduce random writes to flash memory. We conduct extensive experiments on real flash-memory storage devices as well as a flash memory simulation platform to evaluate the performance of our proposal, and the results suggest the efficiency of our proposal with respect to different metrics. (C) 2015 Elsevier Ltd. All rights reserved.