Is this B+ Tree Valid?

Question

In a B+ tree, can a non leaf node exist such that it's key value is deleted? What this means is that the B+ tree has a value in its intermediate non leaf node but not in any of its leaf nodes.

Consider the following structure. I came across this while studying B+ trees. In this structure 13 is not a leaf node. But it is a non leaf node. (In fact it was deleted in the previous instructions. Link for the picture. In this link go to the bottom of the page)

If yes then how come the data is deleted?

Is this a mistake or is there something I am missing?

Answer 1

The image you posted is valid. The only data returned by this tree is what you find in the last row. Because 13 has been removed from the tree, it has been removed from the last row. The fact that 13 exists in a non-leaf node is of no consequence to your results, it is just there to be a comparable value when traversing down the tree. In this case the tree would behave no differently if the 13 was changed to a 16 (based on the above convention).

Douglas Fisher did a comprehensive video series on B+ trees, which can be easier to learn from than reading articles. Part 1 can be found here.

---

Edit: My response in the comments was too long so I will put it here. Plus this is useful info.

If you are searching for a 12, and reach the 13, you will compare IS 12 < 13 or 13 <= 12, the left is true, so you will traverse down to the left leaf. This would have happened whether or not 13 was 16, because this is also true 12 < 16.

If you are searching for 16 and reach the 13 you will compare IS 16 < 13 or 13 <= 16, the right expression is true, so you will traverse down to the right leaf. Then you will find the value of 16 there.

If you are searching for 13 (which doesn't exist) you will ask IS 13 < 13 or 13 <= 13, the right expression is true, so you will traverse down to the right leaf and find that there is no 13 there and you will kick out at this point that 13 has no value.