B-Tree Deletion

B-tree deletion follows yet another clever algorithm. Finding a value in a leaf node and deleting the value isn’t a big deal itself, but what happens when we delete a value from an internal node? Let’s take this tree, again, for an example:

a B-tree with three children nodes which are stored in the files 3.txt, 63.txt, and 160.txt

Imagine that we have to delete the 20. We’d end up with a root node that has one value, but three children, which would completely mess up the B-tree structure.

Because of this, B-tree deletion does the opposite of what insertion does. While insertion causes nodes to split in order to grow the tree, deletion fuses empty (or close to empty) nodes together in order to shrink the tree.

More specifically, when deleting a value causes a node to be less than half full, that’s when we start fusing nodes together. So if a node’s maximum capacity is 10 values, fusing will potentially occur when a node ends up with only 4 values.

I will let you research the specific details of B-tree deletion if you’re interested, as I need to save room in the book for some other important concepts.