5.4.4 B-Trees: Deletion

Delete (r, x)

Delete a record r with key value = x

• Locate the leaf L containing r
• Remove r from L.

  Case 1: L does not become empty after deletion

  • if r is not the first record in L, then there is no need to fix the key values at higher levels.
  • If r is the first record in L, then

    -

    if L is not the first child of its parent P, then set the key value in P's entry for L to be the new first key value in L

    -

    if L is the first child of P, the key of r is not recorded in P; locate the lowest ancestor A of P such that L is not the leftmost descendent of A and set the appropriate key value in A.

  Case 2: L becomes empty after deletion of r

  • Return L to the file system
  • Adjust the keys and pointers in P (parent of L) to reflect the removal of L
  • If the number of children of P now < $\lceil$m/2$\rceil$, examine the node P' immediately to the left or the right. If P' has at least 1 + $\lceil$m/2$\rceil$children, distribute the keys and pointers in P and P' evenly between Pand P'.

    -

    Modify the key values for P and P' in the parent of P

    -

    If necessary, ripple the effects to as many ancestors of P as are affected.

    -

    If the number of children of P' is exactly $\lceil$m/2$\rceil$, we combine P and P' into a single node with 2$\lceil$m/2$\rceil$ -1 children. Then remove the key and pointer to P' from the parent for P'. If the effects of deletion ripple all the way back to the root, combine the only two children of the root. The resulting combined node is the new root and the old root is returned to the file system. The number of levels decreases by 1.

See Figure 5.27 for an example.