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:
“While the light burning within may have been divine, the outer case of the lamp was assuredly cheap enough. Whitman was, from first to last, a boorish, awkward poseur.”
—Rebecca Harding Davis (1831–1910)
“The worst thing I can say about democracy is that it has tolerated the Right Honourable Gentleman for four and a half years.”
—Aneurin Bevan (1897–1960)
“Never stay up on the barren heights of cleverness, but come down into the green valleys of silliness.”
—Ludwig Wittgenstein (1889–1951)