Indexing Points on Flash-based Solid State Drives using the xBR+-tree
Spatial database systems and Geographic Information Systems often employ spatial indices to speed up the processing of spatial queries. Currently, they are also interested in exploiting the positive characteristics of flash-based Solid State Drives (SSDs) like fast reads and writes. However, designing spatial indices for SSDs, termed flash-aware spatial indices, has been a challenging task because of the intrinsic characteristics of these devices. Among existing works in the literature, FAST and eFIND distinguish themselves by proposing general approaches that can be employed to design flash-aware spatial indices. In this article, we apply these approaches to the xBR+-tree, an efficient spatial index for points. The goal is to understand how they should be adapted in order to deal with the particular properties of the xBR+-tree. As a result, we specify two novel flash-aware spatial indices for points, the eFIND xBR+-tree and the FAST xBR+-tree. We also conduct a performance evaluation to analyze their performance. As main conclusion, we point out that eFIND fits very well with the xBR+-tree and allowed to reduce the processing of the index construction from 30.8% to 91.4% and the execution of spatial queries from 22.5% to 46%.