Spatial index structure based on R-tree and quadtree:RQOP_tree

A new index structure for spatial data,RQOP-tree,is proposed by setting up the order relation between data rectangles to partition the data spaces,aimed at the existing problems in current index structures based on R-tree and quadtree.In this structure,the middle nodes are constructed according to the distribution of spatial data instead of partitioning the data space evenly,therefore the height of the tree is guaranteed as low as possible and a comparatively small overlap between brother nodes can be kept.In the range query algorithm,the check of query window containing a node's MBR is introduced to speed up the query effectively for a comparatively large query window.The algorithm for constructing the index structure is given,and its time complexity as well as its correctness is presented.The algorithms for node insertion and range query are obtained.The experiment shows that the query speed is increased greatly.