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’m here in case you succeed.”
—Dean Devlin, U.S. screenwriter, and Roland Emmerich. Jack O’Neil (Kurt Russell)
“The worst vice of the solitary is the worship of his food.”
—Cyril Connolly (1903–1974)
“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 (1812–1889)