Multidimensional B-trees: Analysis of dynamic behavior

Mohamed Ouksel*, Peter I Scheuermann

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

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
JournalBIT
Volume21
Issue number4
DOIs
StatePublished - Jan 1 1981

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Computational Mathematics
  • Applied Mathematics

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

  • Cite this