Slide 15.6: B-tree deletions Slide 15.8: B-tree deletions (cont.) Home

B-tree Deletions (Cont.)

---

The simplest situation is illustrated in the result of deleting key C in the following figure. Deleting the key from the first leaf node does not cause an underflow in the node and does not change its largest value.

Consequently, deletion involves nothing more than removing the key from the node.

Removal of P from the second leaf node does not cause underflow, but it does change the largest key in the node. Hence, the second-level node must be modified to reflect this change. The key to the second leaf node becomes O, and the second-level node must be changed from P to O.

Since P was the largest key in the second node in the second level, the root node must also have key P replaced by O.