INSERT (cont)

The only thing we can do is break this leaf into two smaller (both just barely m/2 each) leaves. But now the node above these leaves needs to know how to decide between the two of them. So, we must pass up the smallest key in the right leaf (after the split) to the parent node (as well as a pointer to the new leaf). This allows the search process to be successfully performed.

Unless of course, this new key & pointer overfills this node (maybe it had m children already), in which case this node must also be split into two, and a key/pointer pair passed up to its parent. In the worst case (when all the nodes in a line are full) we would have to split all of these node (even the root--this would create a new level).

The good news is that, in general, it is unlikely that any node will be split, let alone all of the nodes in a branch. Moreover, even if they all must be split, the cost is only O(log n), the number of disk hits is controlled by the height of the tree going down (to find the right leaf) and going back up again (doing the splits).

NEXT BACK