4

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)

The image of the tree I don't understand

If yes then how come the data is deleted?

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

Crystal Meth
  • 589
  • 1
  • 4
  • 16

1 Answers1

2

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.

BenVlodgi
  • 2,135
  • 1
  • 13
  • 26
  • So does this mean that on changing the value of 13 to 16 in the non leaf node, the B+ tree will still remain valid? If, yes does it not mean that while deletion we can organize the tree as per our convenience(i.e. select any value for the non-leaf node that is between its children)? – Crystal Meth Mar 07 '14 at 01:46
  • Correct, the tree will function just the same by changing `13` to `16`. The results will be the same, which is the bottom row. The contents of the non leaf nodes are just directions, like a road map. Because a road in the USA changes, doesn't mean the Canadian maps need to change. Deletion of nodes may be handled differently in every system, but in an optimized system the non leaf nodes will only be updated if necessary, if the bounds of the values they point to change. In this case as long as `12 < X <= 16`, `X` can be `13, 14, 15, 16` – BenVlodgi Mar 07 '14 at 02:51
  • But will it not cause a problem when I enter 14 or 15. The position of 14 or 15 in the B+ tree will change depending on which search value is put there 13 or 16. For 13 it will go into the right child and for 16 it will go into the right child. Please explain. – Crystal Meth Mar 07 '14 at 13:25
  • @CrystalMeth I've added my response in the answer as it was too long to post here, and difficult to read/understand without some line breaks – BenVlodgi Mar 07 '14 at 13:54
  • I meant during insertion and not searching. While inserting 14 and 15 the tree structure will become different. Sorry for the misleading 'enter'. – Crystal Meth Mar 07 '14 at 14:40
  • @CrystalMeth Oh yes, the tree structure will change, depending on how the balancing is implemented, another leaf could be added, or many values would shift over to the other side of the tree, 12 or 14 might become the new root. Even assuming the entire structure doesn't change, that 13 identifier will probably disappear. – BenVlodgi Mar 07 '14 at 14:48
  • Thank you very much for explaining. I will still have to do a bit of research to get a better grasp on these structures. ;) – Crystal Meth Mar 07 '14 at 15:57
  • @CrystalMeth I'm happy to help, make sure to watch the videos I linked at the end of my original response. – BenVlodgi Mar 07 '14 at 16:07