In B-trees which element gets promoted when the node splits

Question

Let's say there is a B-tree of order 8. This means it can have 8 pointers and 7 elements. Say the letters A through G are stored in this B-tree. So this B-tree is just a single node containing 7 elements.

Then you try to insert J into the tree. There's no room, so you have to split the node and create a new root node. Which element gets promoted up into the root node?

Answer 1

When you want to insert a new element in a full node (with 2*t - 1 keys)

• you split it by choosing the median key of the node (the key that is the middle)
• you generate the two new children with t-1 keys each (splitting it according to the previous key)
• the median value remains in the father node
• then you proceed by normal insertion algorithm, looking where you should place the new element.