A New R-tree Spatial Index Based on Space Grid Coordinate Division

摘要

The intermediate nodes of traditional R-tree use the smallest bounding rectangle as the indicator, in the case of rapid increasing in the amount of data, it will generate much overlapping and coverage between MBR, the index performance and query efficiency will drop significantly. This paper will use the data structure based on grid coordinate division to indicate the intermediate nodes MBR of R-tree, a new R-tree index (GR-tree) based on grid coordinates division is proposed, grid coordinates make the location of space entities and its MBR confirmed, therefore reduce the overlap and coverage between MBR, and by using coordinate tree and circular linked list to store spatial object entities, during the process of index operation, the performance of inserting, deleting, querying algorithm is superior to that of the traditional R-tree, so it can greatly reduce the time complexity of algorithm.