- Prepare
All Platforms Programming Aptitude Syllabus Interview Preparation Interview Exp. Off Campus - Prime Video
- Prime Mock

- Interview Experience
- Prime VideoNew
- Prime Mock
- Discussion Forum
- Nano Degree
- Prime Video
- Prime Mock

# 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
and**can delete a key from any node****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
(except that the root is allowed to have fewer than the minimum number n-1 of keys, where n is the degree).**ensure that a node doesn’t get too small during deletion** - 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.

**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**

**Case 2**

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

- If the child
, then**y that precedes k in node x has at least n keys**. Recursively**find the predecessor k0 of k in the sub-tree rooted at y**(We can find k0 and delete it in a single downward pass.)**delete k0, and replace k with k0 in x.** - If
, symmetrically,**y has fewer than n keys, then**If**examine the child z that follows k in node x.**of k in the subtree rooted at z. Recursively**z has at least n keys, then find the successor k0**(We can find k0 and delete it in a single downward pass.)**delete k0, and replace k with k0 in x.**

- Otherwise,
,**if both y and z have only n-1 keys**and y now contains 2n-1 keys. Then free z and recursively delete k from y.**merge k and all of z into y, so that x loses both k and the pointer to z,**

**Case 3**

If the * key k is not present in internal node x, *determine the root x.c(i) of the appropriate subtree

*if k is in the tree at all. If x.c(i)*

**that must contain k,***in this case as necessary*

**has only n-1 keys, execute step 1 or 2***. Then finish by recursing on the appropriate child of x.*

**to guarantee that we descend to a node containing at least n keys**- If x.c(i) has only n-1 keys but has an immediate sibling with at least n keys, g
and moving the appropriate child pointer from the sibling into x.c(i).**ive 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,** - If x.c(i) and both of x.c(i)’s immediate siblings have n-1 keys,
to become the median key for that node.**merge x.c(i) with one sibling, which involves moving a key from x down into the new merged node**

Learn more about DBMS here on this page.

Login/Signup to comment