In a B-tree of order \(m\) containing \(p\) nodes, the average number of node…

Concept

In a B-tree of order m, every node other than the root must hold at least d = \(\lceil m/2 \rceil - 1\) keys (and at most m - 1 keys). When an insertion pushes a node's key count up to m, the node splits into two nodes and the median key is promoted to the parent, adding at least one new node to the tree. Because every non-root node is guaranteed at least this minimum occupancy d, the tree's total key count and its total node count are tightly linked -- and that link is what bounds how often splits can occur, on average, per insertion.

Application to this item

1. Let d = \(\lceil m/2 \rceil - 1\) be the minimum number of keys any non-root node holds in a B-tree of order m.

2. Build the tree from empty by N insertions, ending with p nodes in total (including the root); since each insertion adds exactly one key and none are ever removed, the tree then holds exactly N keys.

3. The root may hold as few as 1 key, but each of the other p - 1 nodes holds at least d keys, so the total key count satisfies N >= 1 + d(p - 1).

4. Every split adds at least one new node to the tree: an ordinary (non-root) split turns one node into two, adding one, while a root split additionally creates a fresh root above the two halves, adding two. So starting from a single node, the total number of splits performed over these N insertions is at most p - 1 -- one less than the final node count.

5. Combining these two facts, the average number of splits per insertion is at most (p - 1)/N, which by the previous step is at most (p - 1)/(1 + d(p - 1)) -- a quantity that is always less than \(\frac{1}{d}\), so the average number of splits per insertion is at most \(\frac{1}{d}\) = \(\frac{1}{\lceil m/2 \rceil - 1}\).

Cross-check

As a check, take m = 5 (order 5), so d = \(\lceil 5/2 \rceil - 1\) = 2, and suppose the tree currently has p = 5 nodes, reached from a single starting node. Then the total key count is at least 1 + 2 x 4 = 9, while the total number of splits performed is at most 5 - 1 = 4 (fewer still if any of those splits was a root split). So the average is at most 4/9, approximately 0.44, which is indeed below \(\frac{1}{d}\) = \(\frac{1}{2}\) -- consistent with the general bound.

So the average number of splits per insertion is at most \(\frac{1}{\lceil m/2 \rceil - 1}\). The expression \(\lceil m/2 \rceil - 1\) by itself is the minimum node occupancy, not its reciprocal, and \(\frac{1}{\lceil m/2 \rceil}\) uses the wrong denominator because it omits the '-1' term that this derivation requires.