Slide 15.7: B-tree deletions Slide 16.1: Indexed sequential file access Home

B-tree Deletions (Cont.)

---

Removing H from the third leaf node leaves only a single key in that node and hence creates an underflow condition. Either Rule 1.a or Rule 1.b can be used to remove the underflow:

Rule 1.a—Key G has been moved from the second to the third leaf node, leaving two nodes in each leaf node.

The largest key in the second node is F, and the largest key in the third node is I.

Rule 1.b—After H is deleted, the last remaining key in the node, I, is inserted into the neighbor node, and the third leaf node is deleted.

For both cases, the leftmost node in the middle level has been modified to reflect the keys in the leaf nodes.