B+-trees
Abstract
Scope and Method of Study: This paper describes a data structure called the B+-tree, developed by D. Comer and D. Knuth. The B+-tree is a modification of the B-tree. The storage characteristics of the structure are discussed, and empirical data is given from actual test cases generated from an implementation of the B+-tree designed for test purposes. Buffering of the B+-tree nodes is discussed, along with empirical results from two buffering methods. The design of an application of B+-trees in a relational database is presented. Findings and Conclusions: The upper and lower bounds for storage utilization in a B+-tree were obtained analytically. An estimation of the average storage utilization was found empirically. Information was provided empirically and analytically on the effectiveness of the buffering of index nodes. Program listings and test results are included.
Collections
- OSU Master's Report [734]