An efficient R-tree implementation over flash-memory storage systems

Abstract

For many applications with spatial data management such as Geographic Information Systems (GIS), block-oriented access over flash memory could introduce a significant number of node updates. Such node updates could result in a large number of out-place updates and garbage collection over flash memory and damage its reliability. In this paper, we propose a very different approach which could efficiently handle fine-grained updates due to R-tree index access of spatial data over flash memory. The implementation is done directly over the flash translation layer (FTL) without any modifications to existing application systems. The feasibility of the proposed methodology is demonstrated with significant improvement on system performance, overheads on flash-memory management, and energy dissipation.