B-tree
Best case and worst case heights

Let h ≥ –1 be the height of the classic B-tree (see Tree (data structure) § Terminology for the tree height definition). 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 nodes completely filled has n = m –1 entries. Hence, the best case height (i.e. the minimum height) of a B-tree is:

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

Comer (1979) and Cormen et al. (2001) give the worst case height (the maximum height) of a B-tree as
combination:two_responses