Ubiquitous B-Tree

Abstract

B-trees have become, de facto, a standard for file organization. File indexes of users, dedicated database systems, and general-purpose access methods have all been proposed and implemented using B-trees. This paper reviews B-trees and shows why they have been so successful. It discusses the major variations of the B-tree, especially the W-tree, contrasting the relative merits and costs of each implementation. It illustrates a general purpose access method which uses a B-tree