Multidimensional B-trees for associative searching in database systems

Peter Scheuermann*, Mohamed Ouksel

*Corresponding author for this work

Research output: Contribution to journalArticle

41 Scopus citations

Abstract

A new method for multiple attribute indexing, the Multidimensional B-Tree (MBDT), is developed. This method is well suited for dynamic databases, since it handles several types of associative queries efficiently and requires low-cost maintenance. Algorithms and search strategies for exact match, partial match, and range queries are presented and statistical procedures are given to estimate the average and worst case retrieval times. The applicability of our organization to practical databases is discussed and analytical tradeoffs with regard to index organizations based on k-d trees are established.

Original languageEnglish (US)
Pages (from-to)123-137
Number of pages15
JournalInformation Systems
Volume7
Issue number2
DOIs
StatePublished - 1982

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Multidimensional B-trees for associative searching in database systems'. Together they form a unique fingerprint.

  • Cite this