Top Down Insertion in a B Tree

Question

I have a B-Tree of order 5. So the keys are between $\lceil n/2 \rceil- 1 \leq keys \leq n - 1$ and children are between $\lceil n/2 \rceil \leq children \leq n $. Am I doing it right? So a full node would be of 4 keys, how do I split that, because when I split that full node, I get uneven keys in any of the children.

Example: $\{G\}$ at level $0$, $\{A, C, E\}$ and $\{H, K, N, Q\}$ at level $1$

Here $\{H, K, N, Q\}$ is a full node, when I insert T, I must pre-split $\{H, K, N, Q\}$, I get one key in either of the subtree which is wrong as the selection of keys suggest that they must be between 2 and 4.

What am I doing wrong?

Answer 1

It seems you are doing nothing wrong. Like you say, for a B-tree of order $n$ the number of children is between $\lceil n/2 \rceil$ and $n$, the number of keys is one less. For $n=5$, keys are between $2$ and $4$. When you add a key to a node of size $4$, you get two new nodes of size $2$ and one new key which is pushed upwards. When this happens at the root, a new root with a single key is formed.

Your example. Add $T$ to the tree. At the root $G$ go right, to $\{H,K,N,Q\}$. With $T$ this becomes $\{H,K,N,Q,T\}$ which is too heavy and we split into $\{H,K\}$ and $\{Q,T\}$. Middle key $N$ is pushed upwards to the root. In the new configuration the root $\{G,N\}$ with two keys has three children $\{A,C,E\}$, $\{H,K\}$ and $\{Q,T\}$.