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 someone does something we disapprove of, we regard him as bad if we believe we can deter him from persisting in his conduct, but we regard him as mad if we believe we cannot. In either case, the crucial issue is our control of the other: the more we lose control over him, and the more he assumes control over himself, the more, in case of conflict, we are likely to consider him mad rather than just bad.”
—Thomas Szasz (b. 1920)
“... how have I used rivers, how have I used wars
to escape writing of the worst thing of all—
not the crimes of other, not even our own death,
but the failure to want our freedom passionately enough
so that blighted elms, sick rivers, massacres would seem
mere emblems of that desecration of ourselves?”
—Adrienne Rich (b. 1929)
“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)