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.
- Leaf with more than minimum required keys, delete.
- Leaf with less than minimum required keys, underflow!
- Internal
-> leaf underflow, can borrow from left?
- Internal
-> leaf underflow, can borrow from right?
- Internal
-> leaf underflow, merge with left!
- Internal
-> leaf underflow, merge with right!
- Internal
-> internal underflow, can borrow from left?
- Internal
-> internal underflow, can borrow from right?
- Internal
-> internal underflow, merge with left!
- 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]]
}
