0
$\begingroup$

I was trying to learn B+ tree deletion operation and trying to contrast it with B tree deletion operation. However barely any book provided detailed step by step B+ tree deletion operation. So I was referring B+ tree key deletion from here.

The page says deleting 15 from this:

enter image description here

yields this:

enter image description here

Thus this somehow demotes key 13 to its right child and promotes key 11 to its parent. I do not find "promoting" any key specified in the B+ tree deletion algorithm given on the same page.

In step 4 of the B+ tree deletion algorithm on the same page, it says:

If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging.

If I am not wrong, if we follow this step, it should yield something like this:

enter image description here

So is the example wrong? I am not able to confirm as I am not able to find precise step by step procedure. The steps given on this page sounds a bit fuzzy.

$\endgroup$
  • $\begingroup$ Try working through the algorithm step by step and solidify that "feeling". $\endgroup$ – Raphael Sep 5 '16 at 13:35
1
$\begingroup$

I'd not attach too much importance to such kind of boundary cases: both solutions here are valid according to the definition of B+-Tree and depending on the order of operations, it is very common that B-Trees have different shapes for the same data. Here the difference between the two results is just the one between $<$ and $\leq$ in some condition and the choice is not imposed by an invariant of the data structure.

It seems to have a drastically different result because the tree is so close to be as sparse as possible and so close to be collapsible -- at most two more deletions will trigger that. The reason is not that trees close to the boundary are typical, it is because making readable pictures is easier in that case, in practice the number of buckets per node is greater than 4 and fewer nodes are just half-full. Being able to steal one element from the neighbor is more typical than having to merge with it.

Obviously if you know something about the patterns of insertion and deletions, you may prefer one version over other, but it will be a second order effect.

$\endgroup$
  • $\begingroup$ ok so there may exist different versions of insertions and deletions. But can you please explain how this example works by following the algorithm given on the same page. This example promotes 11 to its parent. And such promotion of any key is not at all specified in any step of the algorithm on the same page. $\endgroup$ – anir123 Sep 5 '16 at 12:55
  • $\begingroup$ In fact in step 4 of the B+ tree algo on same page it says: "If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging.", which if I am not wrong should yield what I drawn. Am I wrong? $\endgroup$ – anir123 Sep 5 '16 at 12:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.