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:
“There is not a more disgusting spectacle under the sun than our subserviency to British criticism. It is disgusting, first, because it is truckling, servile, pusillanimous—secondly, because of its gross irrationality. We know the British to bear us little but ill will—we know that, in no case do they utter unbiased opinions of American books ... we know all this, and yet, day after day, submit our necks to the degrading yoke of the crudest opinion that emanates from the fatherland.”
—Edgar Allan Poe (1809–1845)
“The worst thing about it is you don’t even know if you’re doing something wrong.”
—Christine Zajac, U.S. fifth-grade teacher. As quoted in Among Schoolchildren, “Awakening” section, part 3, by Tracy Kidder (1989)
“This monument, so imposing and tasteful, fittingly typifies the grand and symmetrical character of him in whose honor it has been builded. His was “the arduous greatness of things done.” No friendly hands constructed and placed for his ambition a ladder upon which he might climb. His own brave hands framed and nailed the cleats upon which he climbed to the heights of public usefulness and fame.”
—Benjamin Harrison (1833–1901)