Implementation of B+ Tree in C

We will implement the B+ tree with its basic operations. Following are some of the basic operations that are required to work with the B+ Tree data structure:

Operation	Description	Time Complexity	Space Complexity
Insert	Adds a new element into the B+ tree and maintains the tree property.	O(log n)	O(1)
Delete Key	Removes an element from the B+ tree.	O(log n)	O(1)
Search	Searches for an element in the B+ tree using the key.	O(log n)	O(1)
Split Child	Splits a full child node during the insertion.	O(m)	O(1)
Merge Node	Merges two nodes during deletion if necessary.	O(m)	O(1)
Display	Traverses the whole B+ tree and prints all the elements.	O(n)	O(1)

where:

n: denotes the number of nodes in the B+ Tree.
m: denotes the minium order of the tree.

Algorithm for B+ Tree Insert Implementation

Below is the algorithm for the insert function of the B+ tree:

Check if the root node consists of at least two childrens.
Continue traversing the tree until reaching a leaf node.
If the leaf node is not full , insert the element into the key in increasing order.
If the leaf node is full split the leaf node.
After splitting the leaf node, promote the middle key to the parent node.
If the parent node has space, insert the promoted key in the correct position.
If the parent node is full, recursively split the parent node and promote the middle key to it’s parent.
Keep iterating through this procedure until you reach the root node.
If the root node is full, recursively repeat step 2- 5.

Example

The following diagram explains the workflow of inserting a new node in B+ tree:

STEP 1 – Let us take an example of seven elements :2, 4, 7, 10, 17, 21, 28 to insert into the B+ tree.

STEP 2 – Assume that the order is three, then each node must contain at least three nodes and two keys.

STEP 3 – Since we don’t have space to insert 10, which is an overflow condition in the node with three elements, we will split the middle element and then insert it.

STEP 4 – In the same way, we will insert 17 after 10 in the third node.

STEP 4 – Since we don’t have space after 17 to insert 21 in the above third node, we will split 10 from the last leaf node to insert 21 by placing 10 after 7 in the root node.

STEP 5 – To insert 28, we need to send 17 to the above node but, there is no space to insert 17 so, we need to split 7 to place 17 and finally insert 28.

Final B+ Tree after the insertion of all given elements

Algorithm for B+ Tree DeleteKey Implementation

The following is the algorithm to for the deletekey function of the B+ tree:

Find the leaf node that contains the key value.
If the key exists , remove it from the leaf node.
If the leaf node has fewer than n/2 keys after deletion , check it’s sibling to determine if redistribution or merging is needed.
Redistribute or merge with sibling:
If the left sibling has more than ⌈n/2⌉ keys, move the largest key from the left sibling to the current leaf node.
If the right sibling has more than ⌈n/2⌉ keys, move the smallest key from the right sibling to the current leaf node.
Adjust the parent node:
When merging, remove the key in the parent node that pointed to the merged node.
If the parent node now has fewer than ⌈n/2⌉ keys, recursively perform steps 3 and 4 on the parent node.
If merging involves the root node and the root becomes empty, decrease the height of the tree.

Example

The following diagram explains the workflow of inserting a new node in B+ tree:

Let’s assume we want to delete the key 70 from the tree shown in the image.

STEP 1 – First, we need to find the key 70 in the tree. In the given tree, 70 is located in the leaf node [70, 80].

STEP 2 – Remove the key 70 from the leaf node. After removal, the leaf node will contain [80].

STEP 3 – The leaf node [80] after deletion has 1 key, which is the minimum required, so no underflow occurs.

Algorithm for B+ Tree Search Implementation

The following is the algorithm to search an element into the B+ tree:

Start from the root node.
If the current node is a leaf:
Check each key in the node. If a key matches the search key, return true.
If no key matches, return false.
If the current node is not a leaf node:
Iterate through the keys in the node.
If a key in the node is greater than the search key, recursively search the child node corresponding to the current position.
If no such key is found, recursively search the rightmost child node.

Algorithm for B+ Tree Split Implementation

Below is the algorithm for the Split Child function of the B+ tree:

Create a new node newChild.
Identify the middle key in the child node (child) to split the node around it.
Move the keys and children after the middle key from the child node to the newChild node.
Place the middle key into the parent node at the suitable position.
Update the parent node to point to the newChild.
Retain the keys and children up to the middle key in the original child node.

Algorithm for B+ Tree MergeNode Implementation

Below is the algorithm for the Merge Node function of the B+ tree:

Add the separator key from the parent node (which separates the leftNode and rightNode) to the leftNode.
Move all keys and children from the rightNode to the leftNode.
Remove the separator key from the parent node.
Remove the pointer to the rightNode from the parent node.

Algorithm for B+ Tree Traversal

The following is the algorithm for the Display function of the B+ tree:

Start from the root node.
If the present node is a leaf node:
Print all keys in the node.
If the present node is not a leaf node:
For each key in the node, recursively traverse the corresponding child node.
After traversing a child node, print the current key.
Traverse to the rightmost child node after the last key.