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:
“In the case of scandal, as in that of robbery, the receiver is always thought as bad as the thief.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“There’s a victory and defeat—the first and best of victories, the lowest and worst of defeats—which each man gains or sustains at the hands not of another, but of himself.”
—Plato (c. 427–347 B.C.)
“I have never been in any country where they did not do something better than we do it, think some thoughts better than we think, catch some inspiration from heights above our own.”
—Maria Mitchell (1818–1889)