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:
“In all unmerciful actions, the worst of men pay this compliment at least to humanity, as to endeavour to wear as much of the appearance of it, as the case will well let them.”
—Laurence Sterne (1713–1768)
“I sometimes wonder that we can be so frivolous ... as to attend to the gross but somewhat foreign form of servitude called Negro Slavery, there are so many keen and subtle masters that enslave both north and south. It is hard to have a southern overseer; it is worse to have a northern one; but worst of all when you are the slave-driver of yourself.”
—Henry David Thoreau (1817–1862)
“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)