Some average performance measures for the B-tree

DOI10.1007/BF00289710MaRDI QIDQ797287zbMATH OpenOpenAlexFDO

Authors William E. Wright

Publication date 1985

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00289710

zbMATH Keywords

average performance measuresaverage storage utilizationfile organizationindexeslarge B-treesmultiway trees

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Review text

Several average performance measures are presented for large B-trees formed from insertions, where large refers to the number of keys. Formulas are first derived for the expected number of nodes of each size on the bottom level of the tree, where the size of a node is the number of keys currently contained in the node. This is followed by formulas for the probability of making an insertion into a node of a given size, the probability of a split during an insertion into a node, and the expected number of splits during an insertion into the tree. Is is shown that for large trees of high order m, the expected number of splits per insertion is approximately \(1/(\ln 2)m).\) A formula is presented for the average storage utilization, and it is shown that this average approaches ln 2 as m approaches infinity. A simpler formula is derived for the average storage utilization at the bottom level of the tree, and it is shown that this formula is an increasing function of m ranging from 2/3 to ln 2. It is shown that the expected tree height and the expected search path length are approximately logarithmic to the base (ln 2)m. Simulation results are presented to corroborate the theoretical analysis.

Recommendations

• A model of the dynamic behavior of B-trees
• Expected behaviour of \(B^+\)-trees under random insertions
• Height-balanced trees of order (β, γ, δ)
• Modeling B-tree insertion activity
• Toward a formal derivation of the expected behavior of prefix B-trees

Cites work

• B-trees re-examined
• scientific article; zbMATH DE number 3648167 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• On random 2-3 trees
• Organization and maintenance of large ordered indexes
• Space utilization and access path length in B-trees
• Storage utilization in B*-trees with a generalized overflow technique

Cited in

(14)

• Expected behaviour of \(B^+\)-trees under random insertions
• A model of the dynamic behavior of B-trees
• A uniform model for the storage utilization of B-tree-like structures
• Estimating block accesses in a \(\text{B}^+\)-tree whose leaf records are of arbitrary size
• Space saving generalization of \(B\)-trees with \(2/3\) utilization
• Variance of storage requirements for B+-trees
• Toward a formal derivation of the expected behavior of prefix B-trees
• The average height of a node in the BANG abstract directory tree
• scientific article; zbMATH DE number 3843183 (Why is no real title available?)
• Height-balanced trees of order (β, γ, δ)
• Memory management for B-trees
• scientific article; zbMATH DE number 3954287 (Why is no real title available?)
• scientific article; zbMATH DE number 17553 (Why is no real title available?)
• B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half

This page was built for publication: Some average performance measures for the B-tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q797287)