Recently, researches have been performed on a general method that can improve the cache performance of the R-Tree in the main memory to reduce the size of an entry so that a node can store more entries. However, this method generally requires additional processes to reduce information of entries. In addition, the cache miss always occurs on moving between a parent node and a child node. To solve these problems, this paper proposes the SPR-Tree (Selective Prefetching R-Tree), which is an extended R-Tree indexing method using selective prefetching according to node size in the main memory. The SPR-Tree can produce wider nodes to optimize prefetching without additional modifications on the R-Tree. Moreover, the SPR-Tree can reduce the cache miss that can occur in the R-Tree. In our simulation, the search, insert, and delete performance of the SPR-Tree improved up to 40%, 10%, 30% respectively, compared with the R-Tree.
['Hong-Koo Kang', 'Joung-Joon Kim', 'Dong-Oh Kim', 'Ki-Joon Han']
An Extended R-Tree Indexing Method Using Selective Prefetching in Main Memory