# Is “promoting a key” a part of deleting internal node key in B+ Tree?

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:

yields this:

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:

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.

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

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.