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:
“If a playwright tried to see eye to eye with everybody, he would get the worst case of strabismus since Hannibal lost an eye trying to count his nineteen elephants during a snowstorm while crossing the Alps.”
—James Thurber (1894–1961)
“The worst sin that can be committed against the artist is to take him at his word, to see in his work a fulfillment instead of an horizon.”
—Henry Miller (1891–1980)
“We shall make mistakes, but they must never be mistakes which result from faintness of heart or abandonment of moral principles. I remember that my old school master Dr. Peabody said in days that seemed to us then to be secure and untroubled, he said things in life will not always run smoothly, sometimes we will be rising toward the heights and all will seem to reverse itself and start downward. The great thing to remember is that the trend of civilization itself is forever upward.”
—Franklin D. Roosevelt (1882–1945)