Loading, please wait...

A to Z Full Forms and Acronyms

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

Dec 18, 2022 #DataStructureTutorial, 206 Views
In this article, you will learn about the B+ tree.

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
A to Z Full Forms and Acronyms