## Introduction

Before we directly jump into today's discussion, it is imperative to collect all the properties of B-Tree to understand the Delete operation. So, let's revisit them:

B Tree is a self-balancing __Data Structure__ that uses a set of rules to search, insert, and delete data in a faster and more memory-efficient manner. The following rules are followed to create a B Tree to accomplish this.

Rule 1: All leaf nodes must be at the same level.

Rule 2: All non-leaf nodes (except the root node) should have children at least [m/2].

Rule 3: All nodes ( except the root node) should have at least [m/2] - 1 key.

Rule 4: If the root node is a leaf node(only node in the tree), it will have no children and at least one key. If the root node is a non-leaf node, it will have at least two children and one key.

Rule 5: A non-leaf node with n-1 key values should have n non-null children.

From the below pictorial representation, we can obtain the properties of a B-Tree:

From the definition, we can conclude that any node except the root node in a B-Tree is half full, which avoids wastage of storage space. The B-Tree is perfectly balanced, so the number of nodes accessed to find a key decreases.

The following figure shows the minimum and a maximum number of children in any non-root and non-leaf node of B-trees of different orders.

Order of the tree |
Minimum Children (MIN) |
Maximum Children(MAX) |

4 |
2 |
4 |

5 |
3 |
5 |

M |
[M/2] |
M |

Also See, __Multiple Granularity in DBMS____ __and __Checkpoint in DBMS____.__

## Deletion in B-tree

While inserting a key, we had to ensure that the number of keys should not exceed MAX. Similarly, while deleting, we must watch that the number of keys in a node should not become less than MIN. While inserting, when the keys exceed MAX, we split the node into two nodes, and the median key went to the parent node; while deleting when the keys will become less than MIN, we will combine two nodes into one.

Now let us see how all this is done by studying the deletion cases. Deletion in a B-Tree can be classified into two cases:

- Deletion from the leaf node.
- Deletion from the non-leaf node.

Let us now elaborate on each case:

### Deletion From Leaf Node.

It will be divided into various cases. Let us study every case in detail.

#### If Node Has More Than MIN Keys,

In this case, deletion is very straightforward, and the key can be very easily deleted from the node by shifting other keys of the node.

#### If Node Has MIN Keys

After the deletion of a key, the node will have less than MIN keys and will become an underflow node. In such a case, we can borrow a key from the left or right sibling if any one of them has more than MIN keys.

Now you must be wondering which sibling to start from?

In our algorithm, we'll first try to borrow a key from the left sibling; if the left sibling has only MIN keys, then we'll try to borrow from the right sibling.

- When a key is borrowed from the
**left**sibling, the separator key in the parent is moved to the underflow node, and the**last**key from the left sibling is moved to the parent. - When a key is borrowed from the
**right**sibling, the separator key in the parent is moved to the underflow node, and the**first**key from the right sibling is moved to the parent. All the remaining keys in the right sibling are moved from one position to the left.

Time for some examples:

- Delete 15 from the tree:

Here key 15 is to be deleted from the node [15, 19]. Since this node has only MIN keys, we will try to borrow from its left sibling[ 3,7,9,11], which has more than MIN keys.

The parent of these nodes is node [12, 20], and the separator key is 12. Hence, the last key of the left sibling (11) is moved to the place of the separator key, which is moved to the underflow node.

The resulting tree after deletion of 15 will be:-

**Note**: The involvement of the separator key is necessary since if we simply borrow 11 and put it at the place of 15, then the property of the B-tree will be violated.

- Delete 19 from the tree:

As we can see above, key 19 will be deleted by borrowing the left sibling, so key nine will be moved up to the parent node, and 11 will be shifted to the underflow node. In the underflow node, the key 12 will be shifted to the right to make place for 11. The resultant tree will look like this:

- Delete 45 from the tree:

As we can see in the diagram itself, the left sibling of the [45, 47] is [35, 38], which has only MIN keys, so we can't borrow from it. Thus, we will try to borrow from the right sibling, i.e., [65, 78, 80]. As discussed above, while borrowing from the right sibling, the first key of the node is moved to the parent node. In this case, the first key of the right sibling(65) will be moved to the parent node, and the separator key from the parent node(55) will be moved to the underflow node.

In the underflow node, 47 is shifted left to make room for 55. In the right sibling, 78 and 80 are moved to the left to fill the gap created by the removal of 65.

The resulting tree will look like this:

**Note**: If both left and right siblings of the underflow node have MIN keys, then we canâ€™t borrow from any of the siblings. In this case, the underflow node is combined with its left( or right ) sibling.

Letâ€™s see an example for the same:

- Delete 47 from the tree:

If we try to delete 47 from the tree which has only MIN keys and if we delete it, it leads to the underflow condition, so we'll try to borrow from the left sibling [ 35, 38], which also has only MIN keys, then we try to borrow from the right sibling [ 78, 80] which has again MIN keys only. So, what should we do now?

Weâ€™ll combine the left sibling node with the key left in the current node. For combining these two nodes, the separator key(40) from the parent node will move down in the combined node.

But the parent node also has only MIN keys.

In this case, when the parent node becomes underflow, we will borrow a key from its left sibling. But if we look at its left sibling, it also has only MIN keys.

Here, the separator key ( 30) the root node comes down in the combined node, which becomes the new root of the tree, and the height of the tree decreases by one.

The resulting tree will look like this:

### Deletion From Non-Leaf Node,

In this case, the successor key is copied at the place of the key to be removed, and then the successor is deleted. The successor key is the smallest key in the right subtree and will always be in the leaf node. So this case reduces to the above-mentioned approaches.

Letâ€™s retake the above B-tree example:

- Delete 12 from the tree:

The successor key of 12 is 15, this weâ€™ll copy 15 at the place of 12, and now our task reduces to deletion of 15 from the leaf node. This deletion is performed by borrowing a key from the left sibling.

Now let us conclude the above discussion by looking at the flowchart:

Now that you have gained a good understanding of how deletion takes place in B-Tree, it's time to look at its Implementation:

You can also read about the __Multiple Granularity Locking__ and __Recursive Relationship in DBMS____.__