Concept - B*Trees - NTFS Directory Trees

Deleting nodes in B*Trees - NTFS Directory Trees

For the deletion examples we'll start very simply then get complicated very fast. One large example shows all the ways in which delete affects the tree.

Figure 1

Starting with a simple node, we delete E.

Figure 2

Then we delete A.

Figure 3

This leaves us with an empty node.

Figure 4

Now we start with a large example tree. We want to delete G. It's got children, so we find the successor J, delete G and put J in its place. If the key doesn't have any children, this this stage can be skipped.

Figure 5

Now we have transformed the problem into a leaf being deleted. Unfortunately this leaves us with a deficient node !. Our siblings don't have any keys we can steal to make up our numbers, so to fix this, we will have to combine with a sibling.

Figure 6

We have demoted K and adopted O from our right-hand sibling. Unfortunately that leaves us with a deficient node !, so we work on that node next. This time we have a sibling with a key we can steal. To keep the tree in order, we will promote E and demote J.

Figure 7

If you look closely, you will see that one of the nodes (containing F) has swapped sides of the tree. Because the pointers on-disk only point downwards, the the F node isn't changed.

Once a steal has occurred, the operation is complete.