Editing B-tree (section)

==Best case and worst case heights==
Let {{nowrap|''h'' ≥ –1}} be the height of the classic B-tree (see {{Section link|Tree (data structure)|Terminology}} for the tree height definition). Let {{nowrap|''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 {{nowrap|''m''−1}} keys.

It can be shown (by induction for example) that a B-tree of height ''h'' with all its nodes completely filled has {{nowrap|1=''n'' = ''m''<sup>''h''+1</sup>–1}} entries. Hence, the best case height (i.e. the minimum height) of a B-tree is:
: <math>h_{\mathrm{min}} = \lceil \log_{m} (n+1) \rceil -1</math>

Let <math>d</math> be the minimum number of children an internal (non-root) node must have. For an ordinary B-tree, <math> d = \left\lceil m/2 \right\rceil. </math>

Comer (1979) and Cormen et al. (2001) give the worst case height (the maximum height) of a B-tree as:<ref>{{harvnb|Comer|1979|p=127}}; {{harvnb|Cormen|Leiserson|Rivest|Stein|2001|pp=439–440}}</ref>
: <math>h_{\mathrm{max}} = \left\lfloor \log_{d}\frac{n+1}{2} \right\rfloor .</math>