Multidimensional spatial data handling is required in complex applications like geographic information systems, CAD, or automated cartography, where graphical data are frequently inserted and deleted. It is important to use a highly efficient data structure in such a dynamic environment described previously. In this thesis, we propose a new dynamic index structure for spatial retrieval, called BBR(Binary divided and Balanced Region) tree. Retrieve, insertion, and deletion algorithms for the structure are discussed. Unlike R-tree, BBR tree avoids overlaps of the rectangles in intermediate nodes and occupies less storage space than R-tree and $R^+$-tree. Its split and merge algorithms are simpler than that of R-tree or $R^+$-tree.
According to the simulation results, with respect to CPU time of the insertion operation, BBR tree has a better performance than R-tree or $R^+$-tree. In the case that objects are clustered spatially or their size is large, the storage utilization of BBR tree is more poor than that of R-tree or that of $R^+$-tree. Regarding the number of disk I/Os for a retrieve operation, R-tree has a better performance than BBR-tree or $R^+$-tree. But, regarding the number of false drops, $R^+$-tree has better performance than R-tree. BBR tree has a better performance than $R^+$-tree with respect to the number of disk I/Os and to the number of false drops when size of query range is small.
