B-trees: Bearing Fruits of All Kinds

摘要

Index structures are often used to support search operations in large databases. Many advanced database application domains such as spatial databases, multimedia databases, 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 its 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.