B+ Tree

Introduction to B+ Trees

A B+ Tree is simply a balanced binary search tree, in which all data is stored in the leaf nodes, while the internal nodes store just the indices. Each leaf is at the same height and all leaf nodes have links to the other leaf nodes. The root node always has a minimum of two children.

Everything keeps developing with time, our way of living, scientific inventions, be it literally anything! Such is the case with B trees!

The concept of B+ trees exists because of it being much more convenient, both in terms of operations on it, as well as efficiency.

We will discuss everything here in the next few sections, but a good knowledge of B trees is recommended before proceeding! Check out our B trees article here: B Tree

Once you're done, we are ready to proceed! To have a more clear picture of how a B+ tree looks like, let's now study its properties, one by one!

Properties of B+ Trees

1. All data is stored in the leaf nodes, while the internal nodes store just the indices.
2. Each leaf is at the same height.
3. All leaf nodes have links to the other leaf nodes.
4. The root node has a minimum of two children.
5. Each node except root can have a maximum of m children and a minimum of m/2 children.
6. Each node can contain a maximum of m-1 keys and a minimum of ⌈m/2⌉ - 1 keys.

Go through all the above points again, you'll see how all these properties make up a perfect B+ tree, in which all leaf nodes are at the same level, and how some of the values stored in the internal nodes act as pointers to the actual data present in the leaf nodes.

All these leaf nodes are linked to each other, making up a linked list. Also, if you're wondering, this is why B+ trees are an important concept in DBMS!

We discussed that B+ trees are advanced and different from B trees. But how? We are about to find it out now!

Difference Between B Tree and B+ Tree

Now, we will have a look at how B+ Trees are different from B Trees, in detail:

These are the points that differentiate B+ trees from B trees.

Also, do you remember that we earlier stated that operations on B+ trees are relatively easier? You must be wondering why! Let's deep dive to find out that why we say that!

Operations on B+ Tree

Let's look at the steps to perform the operations of insertion, deletion and searching a node in a B+ tree, along with an example each:

Insertion in B+ Tree

So first up is insertion. We will also learn how a B+ tree is created, here in this section! Let's begin!

Before we look at the steps of insertion of a node, let's understand the possible cases:

Case 1: The leaf node is not full

Insert the key into the leaf node in increasing order if the leaf isn't full.

Case 2: The leaf node is full

Step 1: Insert the new node as a leaf node, in the increasing order. Now since the leaf node was already full, some balancing would be needed.

Step 2: Break the node at m/2th position.

Step 3: Add the m/2nd key to the parent node.

Step 4: In case the parent node is already full, just repeat the steps 2 and 3.

Reading the algorithm alone is not enough! Follow the example discussed below to understand how B+ trees are created and elements are inserted!

Example:

We need to use the following data to create the B+ Tree: 1, 4, 7, 10, 17, 21, 31

We suppose the order(m) of the tree to be 4. The following facts can be deduced from this:

Max Children = 4 Min Children: m/2 = 2 Max Keys: m - 1 = 3 Min Keys: ⌈m/2⌉ - 1 = 1

1. Now, for our first step, let's insert 1, 4 and 7 into the first node.

2. The next element to be inserted is 10, but since there is no space in the current node (due to the maximum number of keys being 3), we need to split it.

Here, we need to decide if we will be breaking the node at 4 or 7. Breaking the node at 4 will make the tree left biased, while breaking the node at 7 will make the tree right biased. Choose either of left biased, or right biased and follow it throughout the whole process!

3. For this example, let's choose the right biased tree. Hence, split the node at 7 and move it up..

4. Now we have split it into: (i) 1,4 and a blank space (since the maximum number of keys in a node is 3) and,
   (ii) 7 and 10. We can now insert 17 into node(ii) as it would come after 10 in the ascending order.

5. Next to be inserted is 21, and ideally it should be placed after 17. But since the node is full with 3 keys, we will have to split this node. Now since we chose right biased after step 2, we will split the node in this way: (i) 7, 10 and a blank space (ii) 17, 21 and a blank space.

6. Finally, let's insert 31. It should be placed after 21 in the last leaf node. Which completes our B+ tree!

Note that all nodes have a minimum of 2 children, satisfying the facts that we deduced before we started implementing the B+ tree!

Deletion in B+ Tree

Now we know how a B+ tree is created and how nodes are inserted. But what if we have added a node that we don't need anymore? Yes, we can delete it, but there are some rules to be followed!
Similar to insertion, we have two cases for deletion too!

Case 1: If the value to be deleted is present in the leaf node only

If the value to be deleted is present in the leaf node only, then just simply delete it!

Case 2: If the value to be deleted is present in the leaf node and has a pointer to it as well

Locate the node that you want to delete and remove it from the leaf node, but we also need to remove it from the index that points to this node. Remove the pointer and move the first value of the right child into the parent node.

That's it!

Example:

Delete the value 21 from the following B+ Tree:

After Deletion:

Since 21 is present only in the leaf node and deleting it wouldn't invalidate the minimum number of keys (that is 1, as calculated), we can simply remove it!

Searching in B+ Tree

Searching in a B+ tree is really simple and efficient due to the fact that the leaf nodes, which v=contain the data are linked to each other by pointers, forming a linked list, as we discussed earlier too! This is why B+ tree finds its applications in DBMS too!

So, we are gonna understand the procedure for the same now, with the help of the following algorithm:

1. Perform a binary search on the current node's records.
2. If a record matching the search key is discovered, return it.
3. Report an unsuccessful search if the current node is a leaf node and the key is not found.
4. Otherwise, go back to the beginning and repeat the process.

Example:

Search for 10 in the given B+ tree:

Firstly, we need to look at the indices. We have two of them, 7 and 17. Clearly 10 lies between them, so we need to search in the records between 7 and 17 which is leaf node number 2! And there is our required value, 10!

Pretty simple, isn't it? Hopefully you've been able to understand how all these operations- insertion, deletion and searching work in the case of B+ trees. Also, you may have been able to see how these are easier as compared to operations performed on a B tree. ::