Best Case and Worst Case Heights
Let h be the height of the classic B-tree. Let n > 0 be the number of entries in the tree. Let m be the maximum number of children a node can have. Each node can have at most m−1 keys.
It can be shown (by induction for example) that a B-tree of height h with all its keys completely filled has keys. Hence, the best case height of a B-tree is:
Let d be the minimum number of children an internal (non-root) node can have. For an ordinary B-tree, d=⌈m/2⌉.
The worst case height of a B-tree is:
Comer (1979, p. 127) and Cormen et al. (year, pp. 383–384) give a slightly different expression for the worst case height (perhaps because the root node is considered to have height 0).
Read more about this topic: B-tree
Famous quotes containing the words case, worst and/or heights:
“When trying a case [the famous judge] L. Cassius never failed to inquire “Who gained by it?” Man’s character is such that no one undertakes crimes without hope of gain.”
—Marcus Tullius Cicero (106–43 B.C.)
““If the law supposes that,” said Mr. Bumble, squeezing his hat emphatically in both hands, “the law is a ass—a idiot. If that’s the eye of the law, the law is a bachelor; and the worst I wish the law is, that his eye may be opened by experience—by experience.””
—Charles Dickens (1812–1870)
“The heights of popularity and patriotism are still the beaten road to power and tyranny; flattery to treachery; standing armies to arbitrary government; and the glory of God to the temporal interest of the clergy.”
—David Hume (1711–1776)