Research On Query Algorithm Based On MB-tree

In recent years, research on query algorithm of the spatial database is more andmore attentive. Nearest neighbor query, reverse nearest neighbor query, continuousnearest neighbor query, direction query are the most fashionable objects ofinvestigation. All the time, R-tree, R*-tree, R+-tree storage structures without orderrelations have been studied. The queries will access more data nodes, which resultedin increasing the number of disk I/O. This paper uses MB-tree that has an orderrelation as the storage structure to research the reverse nearest neighbor queryalgorithm and the direction query algorithm.MB-tree updating, reverse nearest neighbor query and directional query baseson MB-tree were researched deeply and detailedly. The following results wereachieved.Firstly, the update algorithm of MB-tree was given, including insertionalgorithm and deletion algorithm. The dealing methods were given for the cases ofoverflow and lowflow.Secondly, the detailed analysis for the position between the query point andMBR was done when reverse nearest neighbor query is processed. Based on this, thecorresponding theorems for different cases were given. According them, the pruningrules for reverse nearest neighbor query were set up so that the reverse nearestneighbor query based on MB-tree was proposed. Then The algorithm’s correctnessand finitness were proved. And the algorithm’s time complexity was given.Thirdly, the detailed analysis for the position between the query point and MBRwas done when directional query is prcessed. Based on this, the correspondingtheorems for different cases were given. According them, the pruning rules fordirectional query were set up so that the directional query based on MB-tree wasproposed. Then The algorithm’s correctness and finitness were proved. And thealgorithm’s time complexity was given.Finally, experimental analysis for directional query was made to show newalgorithm’s high effectiveness.