Design And Implementation Of The Auto-adapted And Dynamic-balanced Spatial Index-QER～+-tree

In the process of designing spatial databases, spatial index is usually created for improving the efficiency of data access and management. Different indexing structures of spatial data and different techniques of index management has different system performance. The complexity of indexing structure is decided by the complexity of spatial data. Spatial index, as an assistant spatial data structure between spatial operation algorithms and spatial objects, can eliminate a lot of spatial objects that have no relation with appointed spatial operations via filtering. So spatial index can not only decrease the operation range of spatial data, but also improve the speed and efficiency of spatial operations. Spatial index is the pivotal technique to improve the efficiency of spatial query and spatial operations etc.In the past twenty years, domestic and overseas scholars proposed a lot of spatial indexing techniques, including the series of R-tree, the series of quad-tree, grid index and so forth. Each one of them has strengths and weaknesses. This paper sums up the research proceeding of spatial index simply. In addition, it studies many typical indexing techniques deeply, and mainly analyses the structures, operation algorithms and performance.This paper proposed QER~+-tree, a new quick speed spatial indexing structure based on quad-tree, R-tree and R+-tree, by way of combining the strengths of some index techniques. The data structure and interrelated algorithms are stated. The performance is also testified by experiments. QER~+-tree breaks down a large R-tree to a lot of small R-tree and R~+-tree. So it can restrain the query space and decrease the overlap of index space. In addition, QER~+-tree uses the way of reinserting by force while splitting nodes. It can better the trees' structure. So QER~+-tree raises the indexing performance in so doing.The study results show that QER~+-tree is an efficient spatial data index structure. The performance of insertion, deletion and especially searching is more superiority than R-tree and R+-tree by using this structure.