B Plus Tree

B + Tree

B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search operations.

In B Tree, Keys and records both can be stored in the internal as well as leaf nodes. Whereas, in B+ tree, records (data) can only be stored on the leaf nodes while internal nodes can only store the key values.

The leaf nodes of a B+ tree are linked together in the form of a singly linked lists to make the search queries more efficient.

B+ Tree are used to store the large amount of data which can not be stored in the main memory. Due to the fact that, size of main memory is always limited, the internal nodes (keys to access records) of the B+ tree are stored in the main memory whereas, leaf nodes are stored in the secondary memory.

Properties of a B+ Tree

1. All leaves are at the same level.
2. The root has at least two children.
3. Each node except root can have a maximum of m children and at least m/2 children.
4. Each node can contain a maximum of m - 1 keys and a minimum of ⌈m/2⌉ - 1 keys.

 

Searching on a B+ Tree

 

Let us search k = 45 on the following B+ tree.

1.Compare k with the root node. 

 

k is not found at the root

 

2.Since k > 25, go to the right child.

 

 Go to right of the root

 

3. Compare k with 35. Since k > 30, compare k with 45.

 

k not found

 

4.Since k ≥ 45, so go to the right child. 

 

go to the right.

 

5. k is found.

 

Insertion Operation

  

Steps for insertion in B+ Tree

1. Every element is inserted into a leaf node. So, go to the appropriate leaf node.
2. Insert the key into the leaf node in increasing order only if there is no overflow. If there is an overflow go ahead with the following steps mentioned below to deal with overflow while maintaining the B+ Tree properties.

 

Properties for insertion B+ Tree

Case 1: Overflow in leaf node

1. Split the leaf node into two nodes.
2. First node contains ceil((m-1)/2) values.
3. Second node contains the remaining values.
4. Copy the smallest search key value from second node to the parent node.(Right biased)

Case 2: Overflow in non-leaf node

1. Split the non leaf node into two nodes.
2. First node contains ceil(m/2)-1 values.
3. Move the smallest among remaining to the parent.
4. Second node contains the remaining keys.

 Example

 

Insert the following key values 6, 16, 26, 36, 46 on a B+ tree with order = 3.

 

Solution:

The order is 3 so at maximum in a node so there can be only 2 search key values. As insertion happens on a leaf node only in a B+ tree so insert search key value 6 and 16 in increasing order in the node.  

We cannot insert 26 in the same node as it causes an overflow in the leaf node, We have to split the leaf node according to the rules. First part contains ceil((3-1)/2) values i.e., only 6. The second node contains the remaining values i.e., 16 and 26. Then also copy the smallest search key value from the second node to the parent node i.e., 16 to the parent node.

 

 Now the next value is 36 that is to be inserted after 26 but in that node, it causes an overflow again in that leaf node. Again follow the above steps to split the node. First part contains ceil((3-1)/2) values i.e., only 16. The second node contains the remaining values i.e., 26 and 36. Then also copy the smallest search key value from the second node to the parent node i.e., 26 to the parent node. 

 

Now we have to insert 46 which is to be inserted after 36 but it causes an overflow in the leaf node. So we split the node according to the rules. The first part contains 26 and the second part contains 36 and 46 but now we also have to copy 36 to the parent node but it causes overflow as only two search key values can be accommodated in a node. Now follow the steps to deal with overflow in the non-leaf node.
First node contains ceil(3/2)-1 values i.e. ’16’.
Move the smallest among remaining to the parent i.e ’26’ will be the new parent node.
The second node contains the remaining keys i.e ’36’ and the rest of the leaf nodes remain the same. 

 

Deletion Operation

Before going through the steps below, one must know these facts about a B+ tree of degree m.

1. A node can have a maximum of m children. (i.e. 3)
2. A node can contain a maximum of m - 1 keys. (i.e. 2)
3. A node should have a minimum of ⌈m/2⌉ children. (i.e. 2)
4. A node (except root node) should contain a minimum of ⌈m/2⌉ - 1 keys. (i.e. 1)

While deleting a key, we have to take care of the keys present in the internal nodes (i.e. indexes) as well because the values are redundant in a B+ tree. Search the key to be deleted then follow the following steps.

Case I

The key to be deleted is present only at the leaf node not in the indexes (or internal nodes). There are two cases for it:

1. There is more than the minimum number of keys in the node. Simply delete the key.  

 

Deleting 40 from B + Tree 

 

 2. There is an exact minimum number of keys in the node. Delete the key and borrow a key from the immediate sibling. Add the median key of the sibling node to the parent. 

 

Deleting 5 from B + Tree  

 

Case II

The key to be deleted is present in the internal nodes as well. Then we have to remove them from the internal nodes as well. There are the following cases for this situation.

1. If there is more than the minimum number of keys in the node, simply delete the key from the leaf node and delete the key from the internal node as well.
Fill the empty space in the internal node with the in order successor.  

 

 Deleting 45 from B + Tree  

 

 

2. If there is an exact minimum number of keys in the node, then delete the key and borrow a key from its immediate sibling (through the parent).
Fill the empty space created in the index (internal node) with the borrowed key.  

Deleting 35 from B + Tree 

 

3. This case is similar to Case II(1) but here, empty space is generated above the immediate parent node.
After deleting the key, merge the empty space with its sibling.
Fill the empty space in the grandparent node with the inorder successor.  

 

 Deleting 25 from B + Tree

 

Case III

In this case, the height of the tree gets shrinked. It is a little complicated.Deleting 55 from the tree below leads to this condition.

                                               Deleting 55 from B + Tree