Some average performance measures for the B-tree
type: Item
instance of: scholarly article
title: Some average performance measures for the B-tree
zbMATH Open document ID: 0545.68054
DOI: 10.1007/BF00289710
author: William E. Wright
published in: Acta Informatica
publication date: 1985-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 3868631
zbMATH Keywords: multiway trees
zbMATH Keywords: indexes
zbMATH Keywords: file organization
zbMATH Keywords: average performance measures
zbMATH Keywords: large B-trees
zbMATH Keywords: average storage utilization
MaRDI profile type: Publication
cites work: Organization and maintenance of large ordered indexes
cites work: B-trees re-examined
cites work: Q5585021
cites work: Q4057549
cites work: Storage utilization in B*-trees with a generalized overflow technique
cites work: Space utilization and access path length in B-trees
cites work: Q3206351
cites work: On random 2-3 trees
full work available at URL: https://doi.org/10.1007/bf00289710
OpenAlex ID: W1978071187
description: scientific article; zbMATH DE number 3868631