# 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}

$$