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?

  • $\begingroup$ Or should I follow the scheme of selecting keys $n - 1 \leq keys \leq 2n - 1$? $\endgroup$ – Abdussami Tayyab May 18 '14 at 11:47

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\}$.

  • $\begingroup$ Okay. Have a nice day =) $\endgroup$ – Abdussami Tayyab May 18 '14 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.