Based On Three-dimensional Multi Level Adaptive Grid And R~+ Tree Hybrid Index Research

With the widespread application of geographic information systems(GIS),three-dimensional spatial data is a response to real-world entities,and the amount of data is getting larger and larger,showing the phenomenon of uneven data distribution.In the two-dimensional space,the existing indexing technology is relatively complete.However,in the three-dimensional space,when dealing with a large amount of unevenly distributed data,there are still many problems with a single index structure,which not only wastes a lot of space storage resources,but also has relatively high search efficiency.low.To solve this problem,this paper proposes a hybrid spatial index structure based on three-dimensional multi-level adaptive grid and R~+tree.The index structure is mainly composed of a two-level structure of multi-level grid and R~+tree.The main research contents are as follows.First,the data set is processed by the multi-level automatic grid division algorithm based on the normal distribution to obtain the length,width and height of the grid division,and then the data space is quickly and effectively divided by the multi-level adaptive grid structure,and then the R~+tree index structure is used in the middle The advantage of the zero overlap of the node directory rectangles,efficient spatial indexing,and finally the establishment and maintenance algorithm based on the index structure is given in detail,which better solves the space utilization rate of a single index structure under the condition of uneven distribution of massive data sets The problem is not high.Secondly,a series of algorithms based on various query operations under the three-dimensional multi-level adaptive grid-R~+tree are given,which mainly compare the most commonly used precision point queries,k nearest neighbor queries and inverse k nearest neighbor queries in spatial indexes.The analysis and detailed description of its implementation and algorithm flow fully prove that the three-dimensional multi-level adaptive grid-R~+tree hybrid index structure proposed in this paper has excellent query performance.Finally,this paper uses a dataset that obeys Gauss distribution to simulate the distribution of three-dimensional data.Through a large number of experimental comparison tests,it is proved that the hybrid index structure based on three-dimensional multi-level adaptive grid-R~+tree proposed in this paper is in the face of massive In the case of uneven data distribution,it has better performance in both index structure construction and query.