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:
“A new talker will often call her caregiver “mommy,” which makes parents worry that the child is confused about who is who. She isn’t. This is a case of limited vocabulary rather than mixed-up identities. When a child has only one word for the female person who takes care of her, calling both of them “mommy” is understandable.”
—Amy Laura Dombro (20th century)
“When I go to hell, I mean to carry a bribe: for look you, good gifts evermore make way for the worst persons.”
—John Webster (1580–1625)
“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)