An Improvement of Index Method and Structure Based on R-Tree

The spatial query based on conventional R-tree index structure has been processed mostly in two steps, the filter step and the refinement step, and the R-tree’s interior nodes contains only index entries. However, the conventional index structure and algorithm have little effect on improving access efficiency especially for massive spatial data. A new index structure and method in this paper are proposed to improve query efficiency with the strategy of increasing the space to reduce the time. Firstly, the new index access method and structure based on R-tree are presented, and the interior node contains not only index entries but also data entries, also the data entry contains both the MBR and the maximum enclosed circle (MEC) of the spatial data object. Secondly, the algorithm of insertion, deletion, searching based on the new index structure and method is proposed. Thirdly, a series of tests of the new index structure and method based on R-tree is presented, which indicates that the new index outperforms the conventional index based on R-tree. Therefore, it improves the query efficiency of spatial data by and large, and it also is useful for current spatial database systems.