B-trees: Bearing Fruits of All Kinds

Ooi, B.C. and Tan, K.-L.

    Index structures are often used to support search operations in large databases. Many advanced database application domains such as spatial databases, multimedia data bases, temporal databases, and object-oriented databases, call for index structures that are specially designed and tailored for the domains. Interestingly, in each of these domains, we find methods that are based on one distinct structure - the B-tree Invented some thirty years ago, the B-tree has been challenged repeatedly, but has retained is competitiveness. In this paper, we first give a quick review of B-trees. We then present its adaptations to various domains. For each domain, we present representative B-tree-based structures and their search operations. We conclude that the b-tree is truly an ubiquitous structure that has stood the test of times with wide acceptance in many domains.
Cite as: Ooi, B.C. and Tan, K.-L. (2002). B-trees: Bearing Fruits of All Kinds. In Proc. Thirteenth Australasian Database Conference (ADC2002), Melbourne, Australia. CRPIT, 5. Zhou, X., Ed. ACS. 13-20.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS