A crash tolerant b-tree data structure for database retrieval systems
James Vandendorpe · 1980
The B-tree data structure is the standard mechanism used to index direct access files. While reliability is a concern for the entire industry, no one had yet examined the effects on the B-tree structure when a system is abnormally terminated. Furthermore, while several variant B-tree structures have been proposed, they have not been fully explored in terms of their reliability in the face of system failure. This thesis addresses these two questions, and proposes a B'-tree structure which allows both the detection and the correction of damage caused by abnormal termination. The programs which update secondary stored B-trees are shown to contain critical paths. If a program crashes while executing within a critical path, the B-tree either loses indices or produces duplicated indices that are temporarily inaccessible. It is shown that there is no way to protect the standard B-tree structure from this kind of failure. A new B'-tree structure is proposed that allows error detection and recovery at negligible cost. The new structure differs from the standard B-tree by the inclusion of three additional fields: Median(x); Nephew(x); and Successor(x). The Nephew field is only used as a reference during error detection and is never traversed. The new B'-tree structure permits timely detection of crash damage and provides enough additional information to restart the update that caused the damage. The cost in storage and time complexity of the B'-tree protection scheme is shown to be negligible. The increase in storage for an order m B'-tree is 0(1/m) over its order m B-tree counterpart (practical values of m exceed 100). From the viewpoint of extra time, the protected update algorithms are essentially free, although there is a slightly increased overhead for key deletion. Neither error detection nor error recovery, however, increase the number of I/O operations beyond those that would normally occur. The B'-tree structure is potentially useful in large data bases and information retrieval systems. It may also serve as a partitioning mechanism for organizing k-d trees on secondary storage, and to protect them from crash. This partitioning also allows the application of heuristics that improve insertion efficiency, heretofore a major drawback to using the k-d tree. Since the k-d structure provides excellent lower performance bounds for range and nearest neighbor queries, their data base application would seem a profitable investigation.