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.enter image description here

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:enter image description here

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.