Understanding B+ tree insertion

Question

I'm trying to create a B+ tree with the following sequence,

10 20 30 40 50 60 70 80 90 100

all index nodes should have minimum of 2 and max of 3 keys. I was able to insert till 90, but as soon as insert 100 it increases the height from 2 to 3.

The problem is second child of root has one node, and I cannot fix it. It should have atleast 2, right? Can someone guide me?

UPDATE: I'm following this algorithm

If the bucket is not full (at most b - 1 entries after the insertion), add the record.
Otherwise, split the bucket.
Allocate new leaf and move half the bucket's elements to the new bucket.
Insert the new leaf's smallest key and address into the parent.
If the parent is full, split it too.
Add the middle key to the parent node.
Repeat until a parent is found that need not split.
If the root splits, create a new root which has one key and two pointers. (That is, the value that gets pushed to the new root gets removed from the original node)

P.S: I'm doing it manually, by hand, to understand the algorithm. There's no code!

Answer 1

I believe your B+ Tree is O.K, assuming the order of your B+ Tree is 3. If the order is m, each internal node can have ⌈m/2⌉ to m children. In your case, each internal node can have 2 to 3 children. In a B+ Tree if a node is having just 2 it children, then it requires only 1 key, so no constraints are violated by your B+ Tree.

If you are still confused, look at this B+ Tree Simulator. Try it.