Deletion of record from B+ tree

Question

I was going through the B+ tree deletion operation from the book Database System Concepts, 6th Edition by Henry F. Korth. One particular thing caught my attention.

A B+ tree is given. We have to delete the record "Gold" from this tree.

So we first locate the record by going down the tree and once we find the node, we delete the record. But this deletion leaves the node underfull, because a leaf node has to be at least half full or it has to have at least $\lceil{\frac{n - 1}{2}}\rceil$ values, where $n$ is the maximum number of pointers in each node.

So we merge the rightmost two nodes. But this leaves their parents left pointer pointing to nothing. We again have a violation. Because the internal nodes need to have at least two pointers. To get around this, we merge the parent with its sibling. Resulting tree is given below:

Now the problem I'm having is that, why the record "Gold" has been moved down? We could have just as easily moved the record "Katz" up without violating anything. And it makes more sense to me, because we've just deleted "Gold". So can anyone explain to me why this has been done like this in the book? And would I be right in saying that things would be the same if "Katz" had been moved up?

Answer 1

Yes and yes.

Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario where this would cause a problem either way.

When you delete a key (one practice I have seen is that) you delete the key along with the value. So, if you delete "Gold" you also delete all the keys with the value "Gold", so that no "Gold" remain. This wasn't done in this case and it's perfectly fine.

The thing about B tree and variants is that there are several ways you can implement them without violating any of the B tree properties. This leads to subtle differences like the one you've observed.