A generic and efficient framework for flash-aware spatial indexing. (May 2019) - Carniel, Anderson C.; Ciferri, Ricardo R.; Ciferri, Cristina D.A.
Abstract: Spatial indexing on flash-based Solid State Drives (SSDs) has become a core aspect in spatial database applications, and has been carried out by flash-aware spatial indices . Although there are some flash-aware spatial indices proposed in the literature, they do not exploit all the benefits of SSDs, leading to loss of efficiency and durability. In this article, we propose eFIND, a new generic and efficient framework for flash-aware spatial indexing. eFIND takes into account the intrinsic characteristics of SSDs by employing (i) a write buffer to avoid expensive random writes, (ii) a flushing algorithm that smartly picks modifications to be flushed in batch to the SSD, (iii) a read buffer to decrease the overhead of random reads, (iv) a temporal control to avoid interleaved reads and writes, and (v) a log-structured approach to provide data durability . Performance tests showed the efficiency of eFIND. Compared to the state of the art, eFIND improved the construction of spatial indices from 43% to 77%, and the spatial query processing from 4% to 23%. Highlights: An efficient framework, called eFIND, that exploits the benefits of SSDs. eFIND transforms a disk-based spatial index into a flash-aware spatial index. A running example porting the R-tree to SSDs, creating the eFIND R-tree. An experimental evaluation to analyze the performance gains of eFIND. Performance tests that measure the effects of each design goal of eFIND.