Understanding B + Tree Insertion

Question

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

10 20 30 40 50 60 70 80 90 100

all index nodes must have a minimum of 2 and a maximum of 3 keys. I was able to insert up to 90, but as soon as insert 100 increases the height from 2 to 3.

The problem is that the second child root has one node, and I cannot fix it. He must have at least 2, right? Can anybody help me?

UPDATE: I follow 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 elements to the new bucket. Insert the new leaf 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) 

PS: I do it manually to understand the algorithm. There is no code!

Answer 1

I believe that your B + tree is ok if the order of your B + tree is 3. If the order is m , each inner node can have lceil; m / 2? to m In your case, each internal node can have 2 to 3 children. In the B + tree, if the node has only 2 of its children, then this requires only 1 key, so no restrictions will be violated by your B + tree.

If you're still confused, take a look at the B+ Tree Simulator . Give it a try.

Answer 2

To get the tree that you drew after inserting values ​​from 10 to 100, the order of your tree should be not 4, but 3. Otherwise, the correct answer: order m allows you to use the m-1 keys in each sheet and each node. After that, Wikipedia's description becomes a bit confusing, as it focuses on children, not keys, and does not mention what to do with rounding. When using only keys, the rules:

 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 right that one key in node (order = 4, max = 3, minleaf = 2, minnode = 1). You may find this page useful, as it has a JavaScript version for the online version, as well as documentation for inserting and deleting:

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