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:
“The landscape of the northern Sprawl woke confused memories of childhood for Case, dead grass tufting the cracks in a canted slab of freeway concrete. The train began to decelerate ten kilometers from the airport. Case watched the sun rise on the landscape of childhood, on broken slag and the rusting shells of refineries.”
—William Gibson (b. 1948)
“If a person tells me he has been to the worst places I have no reason to judge him; but if he tells me it was his superior wisdom that enabled him to go there, then I know he is a fraud.”
—Ludwig Wittgenstein (1889–1951)
“Never stay up on the barren heights of cleverness, but come down into the green valleys of silliness.”
—Ludwig Wittgenstein (1889–1951)