An analysis of B-trees and their variants

摘要

B-trees and their variants, B∗-trees, B+-trees, and B∗+-trees are described and the storage utilization and mean path length in such trees are studied. A new method to find the approximate operation costs and storage utilization in a B-tree and in B-tree variants is presented and the results are verified experimentally. This paper simultaneously serves as a tutorial on B-trees variants and their analyses while presenting new results.