B+ tree deletion

[theguitarist]

My B+ tree looks like :

         rest of tree     
       /
     9  10
   /  \   \
  5    9   10

If I need to delete 5, I can't simply remove it because the page wouldn't contain any elements after that.
So, I decide to merge with the right sibling.

I don't understand what I must do about the parent 9.
I cannot delete the 9 of the parent, and merge 5 and 9 leaf pages, because 9 isn't being deleted at all!

How do I proceed?

[theguitarist]

And, do the index elements of a B+ tree necessarily have to be a subset of the values stored in the leaf pages?

[mike_2000_17]

Usually, I find that the insertion / deletions are often easier to implement with a local "collect-destroy-rebuild" approach. What this means is that you inspect the local branches around the element to remove or near the place to insert. If you have the wiggle room necessary to simply remove/add the element, then that's all you do. If you need to do some restructuring, then you just figure out what is the root of the sub-tree that needs to be restructured (which is usually either the direct parent of the element to remove, or a close parent above that). Then, you do a little traversal of those nodes to "collect" them (collect the elements into a temporary storage). And then, rebuild a fresh sub-tree out of those elements. In my experience, this is not only easier to code, it is also cheaper to run on average than complicated tree surgeries.

Other than that, it is hard to give any kind of precise advice. You might want to provide a clearer explanation (and code) of how you store your nodes and how you link them.

And, do the index elements of a B+ tree necessarily have to be a subset of the values stored in the leaf pages?

As far as I know, no. However, it's probably rare to see an implementation that doesn't because it's trivial (both in coding and in run-time cost) to update the index elements whenever there is an insertion / removal of an element. And not enforcing that "rule" would probably lead to a few additional bits of code, that might end up costing you more than the trivial cost of updating the indices.