Multidimensional B-trees: Analysis of dynamic behavior

Mohamed Ouksel*, Peter Scheuermann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)401-418
Number of pages18
Issue number4
StatePublished - Dec 1981

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Multidimensional B-trees: Analysis of dynamic behavior'. Together they form a unique fingerprint.

Cite this