Deletion in B-Tree

Deletion in B-Tree

 

In this article, we will learn about Deletion in B-Tree.

  • Deletion from a B-tree is more complicated than insertion
  • We can delete a key from any node and when we delete a key from an internal node, we will have to rearrange the node’s children.
  • We must make sure that deletion process doesn’t violate the B-tree properties.
  • We must ensure that a node doesn’t get too small during deletion (except that the root is allowed to have fewer than the minimum number n-1 of keys, where n is the degree). 
  • For deletion, we follow such an approach which might have to back up if a node along the path to where the key is to be deleted has the minimum number of keys.
B-tree delete 1

Various Cases of Deletion

Case 1. 

If the key k is in node x and x is a leaf, delete the key k from x.

Case 2

If the key k is in node x and x is an internal node, do the following.

  • If the child y that precedes k in node x has at least n keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k with k0 in x. (We can find k0 and delete it in a single downward pass.)
  • If y has fewer than n keys, then, symmetrically, examine the child z that follows k in node x. If z has at least n keys, then find the successor k0 of k in the subtree rooted at z. Recursively delete k0, and replace k with k0 in x. (We can find k0 and delete it in a single downward pass.)
B-tree delete 2
  •    Otherwise, if both y and z have only n-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2n-1 keys. Then free z and recursively delete k from y.

Case 3

 If the key k is not present in internal node x, determine the root x.c(i) of the appropriate subtree that must contain k, if k is in the tree at all. If x.c(i) has only n-1 keys, execute step 1 or 2 in this case as necessary to guarantee that we descend to a node containing at least n keys. Then finish by recursing on the appropriate child of x.

  • If x.c(i) has only n-1 keys but has an immediate sibling with at least n keys, give x.c(i) an extra key by moving a key from x down into x.c(i), moving a key from x.c(i) ’s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into x.c(i).
  • If x.c(i) and both of x.c(i)’s immediate siblings have n-1 keys, merge x.c(i) with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node.
B-tree delete 3
Learn more about DBMS here on this page.