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.

Answer 2

To get the tree you've drawn after inserting the values 10 to 100, the Order of your tree must be 4 not 3. Otherwise the answer given is correct: order m allows m-1 keys in each leaf and each node. After that the Wikipedia description gets a bit confusing as it concentrates on children not keys, and doesn't mention what to do with rounding. Dealing with just keys, the rules are:

Max keys for all nodes = Order-1
Min keys for leaf nodes = floor(Order/2)
Min keys for internal nodes = floor(maxkeys/2)

So you are correct in having one key in the node (order=4, max=3, minleaf=2, minnode=1). You might find this page useful as it has an online JavaScript version of the processes as well as documentation of both insert and delete:

http://goneill.co.nz/btree.php