B-tree - Best Case and Worst Case Heights

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 I’ll be glad to make an exception.”
    —Groucho Marx (1895–1977)

    “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, they’re the worst of all.”
    —Carolyn Wells (1870–1942)

    “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)