A model of the dynamic behavior of B-trees (Q1117687)

We present a practical and efficient model for the estimation of average performance measures of B-trees under dynamic conditions of insertions and deletions. Performance measures computed are average storage utilization, average path length, and average tree height. The model introduces a data structure, called a lineage tree, which permits a highly compact representation of B-trees while still retaining information needed to compute the above performance measures. The model then involves a Markov chain in which the states are ``lineages'' obtained from the lineage tree. Probabilities, based on the number of B- tree structures corresponding to each lineage, are derived for the transition from one lineage to another under certain dynamic conditions. Results are given for tree orders ranging from 5 up to 401, and for numbers of keys up to 140,000. Computer requirements are shown to be small to moderate.