What is B+ Tree in Data Structure? | Data Structure Tutorial

In this article, you will learn about the B+ tree.

A B+ tree is a modest form of a self-balancing tree in which all the values are present at the leaf level. An essential concept that needs to be understood before learning the B+ tree is multilevel indexing. It makes accessing the data easier and faster. 

Properties of a B+ Tree

1. All leaves are placed at the same level.
2. The root node must have at least two children.
3. Each node except the root node can have a maximum of m children and at least m/2 children.
4. Each node of the B+ tree can have a maximum of m-1 keys and a minimum of [m/2] - 1 key.

Comparison Between a B- Tree and a B+ Tree

1. The data pointers are only present at the leaf nodes on a B+ tree whereas the data pointers are always present in the internal, leaf, or root nodes on a B-Tree. 
2. In B-Tree, the leaves are not connected. However, in a B+ tree, the leaves are connected. 
3. The rate of operations on a B+ Tree is much faster than on a B- Tree.

Searching on a B+ Tree

The following steps need to be performed to search for data in a B+ Tree of order m. Let the data to be searched be x.

1. First from the root node. Compare x with the keys at the root node i.e [x1, x2, x3, . . . . . . x(m-1)].
2. If the value of the x is less than the x1, then traverse to the left child of the root node.
3. Otherwise if x == x1, compare x2. If x is less than x2, x lies between x1 and x2. So, search the element in the left child of x2. 
4. If x is greater than x2, go for x3, x4, . . . . . x(m-1). Now, repeat steps 2 and 3 again and again.
5. Perform the above steps until you will reach the leaf node. 
6. If x exists in the leaf node, return the value true otherwise return the value false.

Applications of B+ Tree 

• Multilevel Indexing
• It helps in performing operations faster such as insertion, deletion, or search).
• Database Indexing