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:
“I never forget a face, but in your case Ill be glad to make an exception.”
—Groucho Marx (18951977)
“The books we think we ought to read are poky, dull, and dry;
The books that we would like to read we are ashamed to buy;
The books that people talk about we never can recall;
And the books that people give us, oh, theyre the worst of all.”
—Carolyn Wells (18701942)
“Give me the keys. I feel for the common chord again,
Sliding by semi-tones till I sink to a minor,yes,
And I blunt it into a ninth, and I stand on alien ground,
Surveying a while the heights I rolled from into the deep;
Which, hark, I have dared and done, for my resting-place is found,
The C Major of this life: so, now I will try to sleep.”
—Robert Browning (18121889)