A BALANCED HIERARCHICAL DATA STRUCTURE FOR MULTIDIMENSIONAL DATA WITHHIGHLY EFFICIENT DYNAMIC CHARACTERISTICS

A new multidimensional data structure, multidimensional tree (MD-tree) , is proposed. The MD-tree is developed by extending the concept of th e B-tree to the multidimensional data, so that the MD-tree is a height balanced tree similar to the B-tree. The theoretical worst-case stora ge utilization is guaranteed to hold more than 66.7%(2/3) of full capa city. In this paper, the structure of the MD-tree and the algorithms t o perform the insertion, deletion, and spatial searching am described. By the series of simulation tests, the performances of the MD-tree an d conventional methods are compared. The results indicate that storage utilization is more than 80% in practice, and that retrieval performa nce and dynamic characteristics are superior to conventional methods.