There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree.
For example, given the following tree, how would we delete 26 and 63?
Is there a general approach?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Wikipedia describes such an algorithm, and there are surely many other sources, some of them more detailed. $\endgroup$– Yuval FilmusMay 12, 2019 at 14:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
B-tree deletion tends to be explained very badly in most textbooks, because the algorithm has one particular case which is complicated.
When inserting a leaf element in a B-tree, if a node becomes over-full, you split it. This has the effect of inserting a node into to its parent. If that node then becomes over-full, continue recursively.
When deleting a leaf element in a B-tree, if the node becomes under-full, you conceptually merge it with one of its neighbours and the common parent element. This "merge" (or "rotation") operation is the key to understanding B-tree deletion.
Let's take deleting 26 as our example. This leaves us with a node containing just 25, which is under-full.
Suppose you merged the node with its right neighbour and its common parent. This would leave you with a node containing the elements 26, 34, 45, 27, with the element 34 removed from the parent. This is exactly the same situation you would be in if you had a leaf node which contained three elements and added a fourth, leaving the node over-full. So just do what you would do if this were an insertion.
It's a similar story if you delete an interior element. Suppose you deleted the element 34. Then all you do is merge the two child nodes that it affects, giving you a node with the elements 25, 26, 45, and 47. This is exactly the situation you'd be in if you had a node with three elements and inserted a fourth.
In practice, you don't actually "merge", but you "rotate" elements between child nodes and the new common parent entry. "Merging" only happens if there is no way to "rotate" without one of the new nodes remaining under-full.
Assuming the usual B-tree variant, a node can store between $t-1$ and $2t-1$ entries, where $t$ is the minimum ply of the tree. If you need to merge, it's because an entry was deleted, either from one of the nodes being merged or its common parent. Either way, you have $2t-2$ entries that you have to deal with. The solution is to just make it one node, which has the effect of deleting a node from the parent node. You can now simply delete recursively.
Some care needs to be taken with the root node, because deleting from the root node may result in the height of the tree changing.
ADDENDUM
Do not read this until you fully understand the textbook algorithms, at least in theory, because I'm going to go off-textbook now and make a few comments about how real-world B-trees aren't the same as what you see in your textbook.
Real B-tree implementations are often designed for concurrency, which complicates both insertion and deletion even more; just because you hold an exclusive lock on a node, that doesn't mean you hold an exclusive lock on its parent. Unlike insertion, however, deleting an entry can, at worst, make a node under-full, and B-tree lookup operations still work on under-full nodes. So real implementations may just record that a node's parent needs rebalancing, and complete the rebalance later, perhaps with a concurrent task. (By the way, you can do a similar trick with insertion.)
Further on that point, because high concurrency means avoiding interior node deletion if you can, real B-tree implementations often try very hard to avoid it using aggressive rotation. So, for example, given a choice of two siblings with which to merge an under-full node, always choose the larger one. Even consider distributing the entries between three siblings at a time if that applies.
Real B-tree implementations are also often designed for ACID-safe database transactions. Implementing transaction-safety is beyond the scope of this discussion, but fully supporting two-phase commit and rollback affects how algorithms on B-trees are implemented.
Even though the size criterion is more strict, deletion from B+-trees can be less complex the interior nodes do not hold full entries. This is especially true when transactions are needed. Again, beyond the scope of this discussion, but this is one of many reasons why B+-trees are much more common in the wild than B-trees.
Finally, and most importantly, many real B-tree implementations have to deal with keys that aren't of a constant size, such as strings. This means that the upper and lower bounds of a real B-tree node are measured in bytes, not entries. This has implications, for example, when choosing which key should be the new common parent of a merged node. Real implementations try to choose the physically smallest one that also keeps the physical sizes of the new child nodes roughly equal.
$\begingroup$
$\endgroup$
All of the keys you want to delete in this particular example belong to the case when we are deleting keys from a leaf node, without need to rebalance a tree after deletion.
Algorithm for deleting a key from a leaf node consists of three steps:
1) Search for the value to delete.
2) If the value is in a leaf node, simply delete it from the node, because there are no subtrees to worry about.
3) If underflow happens (i.e., if we break one of the defining rules/properties of a B-tree - every non-root node has to have at least (M-1)/2 keys), rebalance the tree.
Also, if you are interested in implementation of rebalancing algorithm, beyond the scope of the given example, I suggest these sources:
