| Digital City and Digital Earth is becoming mature gradually. Baidu map, Google map and other application software walk into our lives step by step by step. Spatial data index technology plays an important role in the fields of geographic information system(GIS). It directly determines the performance of the entire software system. In order to find the better spatial data index method, many researcher is making unremitting efforts to study on the spatial data structure. Therefore the study on it has significance both in theory and practice. R-tree’s appearance provides a better spatial data indexing method, avoiding the comparison of massive data. After that many kinds of modified R-tree continuously improve the efficiency of spatial data index.This thesis studies the RQOP tree, which is a spatial data index structure having outstanding searching performance at present. By checking the relationship between the data used in practical application and restructuring the RQOP tree, make the tree more compact and then we can achieve the spatial data indexing mechanism with higher performance. Because RQOP tree is faster than other R-tree, CF tree etc., therefore, this article’s main purpose is that research and improve RQOP tree so as to improve the searching speed and reduce the storage space.RQOP tree as the spatial data tree, defines the priority sequence of the Minimum Bounding Rectangle(MBR Minimum Bounding Rectangle), and divides the spatial target data into quadtree structure according to these priority sequences, therefore, makes the tree highly balanced and provides a good performance for searching spatial data. The traditional R-tree data solved the searching function to spatial data, however RQOP tree combines the advantages of the R-tree, and further improves the efficiency of searching spatial data. Study deeply and improve RQOP tree have a positive effect on raising spatial data process.In order to obtain the spatial data index structure with higher performance, this thesis takes the spatial objects’ Minimum Bounding Rectangle(Minimum Bounding Rectangle) as the approximate expression, and discuss the division method of data space accoding to the sequence relationship between spatial objects. At the same time, using defined sequence relationship between spatial objects studied therelationship between regions with a certain expression in a tree structure.Studied the spatial data’s query problem, insert issue, remove problem, and then obtained results as the follows:In-depth research on how to establish the four division method containing the inclusion relationships of the spatial data. Improve the division criteria on the basis of the original RQOP tree. After adopt new guidelines, construct the new RQOP tree with the minimum coverage, the minimum overlap of the four division method. Make the entity data not only exist in the bottom, but also its inclusion relationships can be reflected in the tree’s structure. Reduce cotyledons’ node, then make the overall structure more compact, and show the effectiveness of the new division method through experiments.The new RQOP tree’s node insertion, deletions need to use new methods, experiments show that the new method for inserting, deleting data in a more compact space, its efficiency also has had improved.For the improved new RQOP tree, using cutting rules to search. For the spatial entity data containing inclusion relationships, cutting rules don’t need to change its core algorithm. Cutting force remains unchanged, experiments proved more compact data structure had more index efficiency in the cutting rule. Its query effect has been improved to a certain degree. On this basis of this, giving a new query algorithm.Based on the above research, this article presents an improved spatial data index strcture based on RQOP tree. This structure proposed optimization program for the use of intermediate nodes, experiments show that the method proposed in this thesis has a high practicability to improve the efficiency of index. |
