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$
  • 2
    $\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.

| cite | improve this answer | |
$\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$ – Maha 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$ – Maha Sep 5 '16 at 12:58
1
$\begingroup$

I share your perception of the problem. The literature on B trees (and it's variants) are written by people who already understand the problem and as such they easily gloss over some details. This does make it difficult to understand.

The case of the B+ tree delete operation is somewhat absurd because in contrast with the insert operation (which is comparatively straightforward) the delete operation is not and is riddled with edge cases.

  1. Leaf with more than minimum required keys, delete.
  2. Leaf with less than minimum required keys, underflow!
  3. Internal -> leaf underflow, can borrow from left?
  4. Internal -> leaf underflow, can borrow from right?
  5. Internal -> leaf underflow, merge with left!
  6. Internal -> leaf underflow, merge with right!
  7. Internal -> internal underflow, can borrow from left?
  8. Internal -> internal underflow, can borrow from right?
  9. Internal -> internal underflow, merge with left!
  10. Internal -> internal underflow, merge with right!

Note that we have to treat children of internal nodes differently wether they are internal or leaf nodes. This is why we have two sets of borrow and merge operations to consider.

For each of the borrow and merge operations we also must consider the left or right case. I've decided to favour the left case, and only use the right case when the left case is impossible. This is an implementation detail and completely arbitrary (and I bet it is also a source of additional confusion).

I choose to illustrate how to implement B+ tree delete with the follow JavaScript snippet. However, this is only a high level overview of the actual code, it will not run as is.

function remove(node, value) {
  if (isLeaf(node)) {
    return deleteIn(node, value)
  } else {
    // internal node

    const [k, v] = node

    const index = findIndex(k, value)
    const subtree = v.get(index)
    const underflow = remove(subtree, value)

    if (underflow) {
      if (isLeaf(subtree)) {
        // can we borrow?

        if (leafBorrow(node, index, v, -1)) {
          return false
        }

        if (leafBorrow(node, index, v, +1)) {
          return false
        }

        // we must merge!

        if (0 < index) {
          return leafMerge(node, index, subtree, -1)
        } else {
          // we only merge right when we cannot merge left

          return leafMerge(node, index, subtree, +1)
        }
      } else {
        // can we borrow?

        if (internalBorrow(node, index, subtree, -1)) {
          return false
        }

        if (internalBorrow(node, index, subtree, +1)) {
          return false
        }

        // we must merge!

        if (0 < index) {
          return internalMerge(node, index, subtree, -1)
        } else {
          // we only merge right when we cannot merge left

          return internalMerge(node, index, subtree, +1)
        }
      }
    }
  }
}

The underflow condition is triggered when the a B tree of order m falls below it's minimum required keys Math.ceil(m / 2) - 1. I've omitted this from the code above but that's what the code would do to signal underflow.

Leaf node underflow is just node.size < Math.ceil(m / 2) - 1 while internal node underflow is node[0].size < Math.ceil(m / 2) - 1. I use positional notation to select either the internal node keys node[0] or children node[1], this is abbreviated in the example as const [k, v] = node (deconstructing syntax).

leafBorrow and internalBorrow return true on success. Borrowing only succeeds when there are more than minimum required keys so that the result of borrowing does not itself lead to an underflow condition. That's why we opt out if we succeed in borrowing.

leafMerge and internalMerge can modify the tree in such a way that the tree keeps underflowing until we hit the root, so they may propagate the underflow condition.

The devil is in the details of leafBorrow, internalBorrow, leafMerge and internalMerge but at least by doing this we can break down the delete operation into 4 distinct parts. What I recommend now is studying each of these cases in isolation with an small tree of order 3 and 4 (the smallest possible B+ trees).

The B+ tree visualizer is a great tool but it doesn't properly illustrate what's actually going on in great detail. There's too much movement in one go. However, it will help.

leafBorrow

Given a B+ tree of order 3 like this:

{
  "k": [2],
  "v": [[1], [2, 3]]
}

To delete 1 we trigger underflow.

{
  "k": [2],
  "v": [[], [2, 3]]
}

Borrow 2 from right.

{
  "k": [2],
  "v": [[2], [3]]
}

And update separator. Always left most value (which may or may note be imminently accessible).

{
  "k": [3],
  "v": [[2], [3]]
}

Note that a helper function that will get the first value (the value to use as separator) from a subtree will come in handy. In this case the value is right there but this isn't the case for internalBorrow.

internalBorrow

Given a B+ tree of order 3 like this:

{
  "k": [3],
  "v": [
    {
      "k": [2],
      "v": [[1], [2]]
    },
    {
      "k": [4, 5],
      "v": [[3], [4], [5]]
    }
  ]
}

To delete 1 we trigger underflow, as per usual.

{
  "k": [3],
  "v": [
    {
      "k": [],
      "v": [[2]]
    },
    {
      "k": [4, 5],
      "v": [[3], [4], [5]]
    }
  ]
}

Borrow from right by going via the parent. We'll bring over the leftmost right subtree by concatenating the keys [] and [3], and the children [[2]] and [[3]] in that order because we are bringing over a subtree from the right side of the tree.

{
  "k": [3],
  "v": [
    {
      "k": [3],
      "v": [[2], [2]]
    },
    {
      "k": [5],
      "v": [[4], [5]]
    }
  ]
}

Update separator to 4 (the smallest value found in the right subtree). This is where that helper function to find the smallest value in a subtree is useful.

{
  "k": [4],
  "v": [
    {
      "k": [3],
      "v": [[2], [3]]
    },
    {
      "k": [5],
      "v": [[4], [5]]
    }
  ]
}

leafMerge

A leaf node must merge with it's left or right sibling when it cannot borrow from it's left or right sibling.

Given a B+ tree of order 3 like this:

{
  "k": [2],
  "v": [[1], [2]]
}
  • To delete 1 we need to merge with the right leaf.
  • To delete 2 we need to merge with the left leaf.

When we merge, we also delete one separator key.

{
  "k": [],
  "v": [[2]]
}
{
  "k": [],
  "v": [[1]]
}

Given a B+ tree of order 4 like this:

{
  "k": [5],
  "v": [
    {
      "k": [3],
      "v": [[2, 3]]
    },
    {
      "k": [11],
      "v": [
        [5, 7],
        [11, 13]
      ]
    }
  ]
}

To delete 2 we merge with right.

{
  "k": [5],
  "v": [
    {
      "k": [],
      "v": [[3]]
    },
    {
      "k": [11],
      "v": [
        [5, 7],
        [11, 13]
      ]
    }
  ]
}

This will trigger an internalMerge.

internalMerge

An internal node merge operation happen in response to an underflow condition triggered by leafMerge.

Given a B+ tree of order 4 with a present underflow condition like this:

{
  "k": [5],
  "v": [
    {
      "k": [],
      "v": [[3]]
    },
    {
      "k": [11],
      "v": [
        [5, 7],
        [11, 13]
      ]
    }
  ]
}

To me, this looks like a three-way merge. We'll be concatenating the keys [], [5] and [11] to construct [5, 11] and concatenating the children [[3]] and [[5, 7], [11, 13]] to construct [[3], [5, 7], [11, 13]]. It's worth pointing out that the empty containers are only empty because the B+ tree is of order 3 or 4. They wouldn't empty completely (for a non root node) if m was greater than 4. Don't make the mistake of thinking that they are irrelevant because they are empty (in this small example) it will depend on what the required minimum number of keys are, i.e. Math.ceil(m/2)-1.

The result should be:

{
  "k": [5, 11],
  "v": [[3], [5, 7], [11, 13]]
}
| cite | improve this answer | |
$\endgroup$

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.