btree height bounds

The lowerbound and upperbound of the height of an $n$-key B-tree for $n\ge1 $

Definition[Minimum Degree]

Nodes have lower and upper bounds on the number of keys they can contain. We express these bounds in terms of a fixed integer $t\ge 2​$ called the minimum degree of the B-tree:

  • Every node other than the root must have at least $t-1​$ keys. Every internal node other than the root thus has at least $t​$ children. If the tree is nonempty, the root must have at least one key.
  • Every node may contain at most $2t-1$ keys. Therefore, an internal node may have at most $2t$ children.

The upperbound

Observation

To increase the height of an $n$-key B-tree, we want the keys at every node to be minimal.

The root node has at least $1$ key. Because this B-tree is non-empty, the root must have at least one key. As a result, at depth $1$, there are at least 2 nodes each with $t-1$ keys. At depth $2$, there will be at least $2t$ nodes each with $t-1$ keys. At depth $3$, there will be at least $2t^2$ nodes each with $t-1$ keys. Continuing the pattern, at depth $h$, there will be at least $2t^{h-1}$ nodes each with $t-1$ keys.

Hence, the minimum number of keys is given by
$$
n \ge 1 + 2(t-1) + 2t(t-1) + \cdots + 2t^{h-1}(t-1) = 1 + (t-1)\sum_{i=1}^h 2t^{i-1} = 2t^h - 1
$$

Rearranging gives
$$
h \le \log_t \frac{n+1}{2}
$$

The lowerbound

To decrease the height of an $n​$-key B-tree, we want the keys at every node to be maximal.

The root node has at most $2t-1$ keys. At depth 1, there are at most $2t$ nodes each with $2t-1$ keys. At depth 2, there are at most $(2t)^2$ nodes each with $2t-1$ keys. Continuing the pattern, at depth $h$, there are at most $(2t)^h$ nodes each with $2t-1​$ keys.

Hence, the maximum number of keys is given by
$$
n\le (2t-1) + 2t(2t-1) + (2t)^2(2t-1) + \cdots + (2t)^h(2t-1) = (2t-1) \sum_{i=0}^h (2t)^i= (2t)^{h+1}-1
$$
Rearranging gives
$$
h \ge \left[\log_{2t}(n+1)\right]-1
$$

The bounds

Put together and get
$$
\left[\log_{2t}(n+1)\right]-1 \le h \le \log_t \frac{n+1}{2}
$$