2-Level R-tree Spatial Index Based on Spatial Grids and Hilbert R-tree

Multi-level spatial index techniques are always used in the management of large spatial databases.This paper presents a novel 2-level index structure,which is based on the schemas of spatial grid-file,Hilbert R-tree and common R-tree.This new structure is named H2R-tree,and detailed algorithms are given.Using real data for test,the new method is proved to show superior performances in several aspects.The first,it suits for grid management with no additional demand;the second,H2R-tree shows better query efficiency;the third,it supports local independent update;the forth,it is suitable for distributed data management,and easy for realization;and the last,former bulk-loading methods can be applied in H2R-tree easily.Generally,H2R-tree is specifically suitable for the indexing of highly skewed,distributed,and large spatial database.