$B^+$ tree Reference.
In a $B^+$ tree only the leaf nodes have a pointer to actual data (record pointers) whereas internal nodes points to index blocks.
In the given question we have
- $M: \text{Number of pointers in internal nodes} = 3.$
- $L: \text{Number of data items in a leaf node} = 3.$
- Further we can see that right biasing is used while splitting a node (same key value moving to the right, in a $B^+$ tree all internal key values will be present in leaf node as only the leaf node actually points to the data record)
To insert $34$ we’ll first place it in the sorted order among the leaf nodes.
Now, we see that the block (being the leaf node the pointers here are record pointers) having $34$ is overflowing and so we’ll split it and move the center element to the parent block. There might be a confusion as to whether $34$ or $50$ should move up, but if we see the question it is following right biasing (same key value is going to the right) and so $50$ must move up.
Now, we have an overflow in the internal node as the maximum capacity of an internal node is $3$ block pointers but we are having $4$ here. So we must again split and move $50$ upwards.
Now we have an overflow in the root node and so we must again split and move $120$ upwards making a new root.
Now all the $B^+$ tree requirements are satisfied and so the insertion algorithm terminates.