Multidimensional B-trees: Analysis of dynamic behavior

The Multidimensional B-tree (MDBT) is a new method for multiple attribute indexing which uses B-trees to maintain the filial sets at each level and imposes an ordering on these filial sets in order to ensure efficient searching for various associative queries. In this paper, we show that the MDBT provides an attractive alternative to other indexing structures when frequent changes to the database occur. We present algorithms for maintaining the MDBT structure when insertions or deletions are posted which also account for some storage reclamation. Procedures for evaluating the average and worst-case times of our algorithms are given, showing that the maintenance of the MDBT structure can be done at a relatively low cost.