A Hybrid Structure Of Spatial Index Based On Multi-Grid And Qr-tree

With the thorough development of information technology, it produces large amounts of spatial data constantly in various fields. Face to vast amounts of spatial data with specificity and the complexity of spatial query, it must to recommend spatial indexing technology to improve the query performance of spatial database. As one of the key technologies of spatial database, the performance of spatial index directly affect the overall performance of the spatial database.In this paper, we study the popular spatial database indexing technology currently. First of all, the basic theories of various spatial database indexing technology is described, then we analyze the advantages and weaknesses of different index structures. Second, based on thorough study of the grid index and the QR-tree, this paper proposes a hybrid index based on multi-level grid and improved QR-tree, the basic idea of this index is that: First, it divides the research space by multi-level, which is the key to the whole index structure. The appropriate partitioning can effectively reduces the storage space and improve the efficiency of the system. And then QR-tree for every final level grid is established, which can reduce the overlap of space and improve the query efficiency.This paper also introduces lazy splitting technique when the nodes split. The main idea of this technology is that we not immediately split the overflow node, but insert the data-items into the adjacent siblings until they are full. When the neighboring siblings are full, it runs splitting operation use of clustering technology to obtain higher efficiency. This multi-level hybrid index can not only improve the overall query performance and search efficiency by this technique, but also greatly improve the space utilization of the system. It has important research value and good prospects.Finally, this paper accomplishes the simulation testing of the multi-level hybrid index by Java technology. The performance comparison between the multi-level hybrid index and the conventional QR-tree is made by examine a lot of experimental spatial data sets which are made randomly. Experimental results show that the construction of multi-level hybrid index is relatively low, and it has a high time complexity and space complexity.