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 attention of those who frequent the camp-meetings at Eastham is said to be divided between the preaching of the Methodists and the preaching of the billows on the back side of the Cape, for they all stream over here in the course of their stay. I trust that in this case the loudest voice carries it. With what effect may we suppose the ocean to say, “My hearers!” to the multitude on the bank. On that side some John N. Maffit; on this, the Reverend Poluphloisboios Thalassa.”
—Henry David Thoreau (1817–1862)
“... today ... photographers prefer disfigurement to adornment. It is now chic to do your worst to people.”
—Margaret Anderson (1886–1973)
“Forgetting: that is a divine capacity. And whoever aspires to the heights and wants to fly must cast off much that is heavy and make himself light—I call it a divine capacity for lightness.”
—Friedrich Nietzsche (1844–1900)