B-Tree in Data Structure

B-Tree

The m-way search tree minimizes the time of file access due to its reduced height. But it is required to keep the height of the tree as low as possible and for this purpose, we need to balance the height of the tree. This balanced M-way search tree is called B-Tree. A B-tree of order M is an M-way search tree in which:

1. The root node has at least 1 key value and at most M-1 key values.
2. The other nodes except the root contain at least [M/2]-1 key values and M-1 key values.
3. All leaf nodes are on the same level.
4. Keys are arranged in a defined order within the node.

Rules for Insertion B-tree

1. At first, search the tree to check the existence of new key values in the tree. If no duplicate key is found, then get the leaf node N where the new key is to be inserted.
2. If N is not full, then insert the new key in N and exit.
3. If N is full, then split the node into two new nodes at its median value and move the median key value to its parent node.

Rules for Deletion B-tree

In B-tree deletion is done from the leaf node only. If we need to delete a key from an internal node then replace the node with its immediate successor until a key from any leaf node is promoted to its upper level. Then balance the tree according to the given rules:

1. If the leaf node has enough keys, then simply remove it.

2. If the leaf node contains less than the minimum number of keys, then check its immediate left sibling node and immediate right sibling node.

iii. If both the sibling nodes have a minimum number of keys, then create a new node merging the two leaf nodes and the intervening key value of their parent node.