The maximum number of keys stored in a B-tree of order m and depth d is

Concept. In a B-tree of order m, no node has more than m children, and a node with c children holds exactly c − 1 keys, so an internal node holds at most m − 1 keys; a leaf has no children at all, yet it is capped at the same m − 1 keys, so the bound m − 1 applies to every node of the tree. Writing the depth as d means the tree spans d + 1 levels, numbered 0 for the root through d, and level i can hold at most mi nodes. The largest possible number of keys is therefore (largest number of nodes) × (largest number of keys per node).

Application.

1. Level 0 holds at most m0 = 1 node, level 1 at most m1 = m nodes, and in general level i at most mi nodes.

2. Adding this over all d + 1 levels gives the largest node count 1 + m + m2 + ⋯ + md.

3. That geometric series has the closed form (md+1 − 1) / (m − 1).

4. Each of those nodes stores at most m − 1 keys, so multiply the node count by m − 1, giving (m − 1) × (md+1 − 1) / (m − 1).

5. The factor (m − 1) cancels, leaving md+1 − 1 keys.

Cross-check.

• Take m = 2 and d = 1. The two levels hold a root with 1 key and 2 children with 1 key each, that is 3 keys in all, and the formula gives 22 − 1 = 3.

• Take m = 3 and d = 1. The root holds 2 keys and its 3 children hold 2 keys each, that is 2 + 6 = 8 keys, and the formula gives 32 − 1 = 8.

• Two traps are worth naming. Stopping at the node count alone leaves (md+1 − 1) / (m − 1), and reading depth d as d levels instead of d + 1 leaves (md − 1) / (m − 1). The quantity asked for here is keys, counted over d + 1 levels with the root at depth 0.

So the largest number of keys a B-tree of order m and depth d can store is md+1 − 1.