MD-tree: a balanced hierarchical data structure for multidimensional data with highly efficient dynamic characteristics

A multidimensional data structure, the MD-tree (multidimensional tree), is proposed. The MD-tree is developed by extending the concept of the B-tree to multidimensional data, so that the MD-tree is a height-balanced tree similar to the B-tree and, even its worst-case storage utilization is more than 66.7%. A description is given of the structure of an MD-tree and the results of a series of simulation tests which indicate that the storage utilization is more than 80% in practice and that the retrieval performance and the dynamic characteristics are superior to those of conventional methods