B Tree vs B+ Tree

Posted September 12, 2022 by Rohith and Anusha ‐ 2 min read

B-Tree is known as a self-balancing tree as its nodes are sorted in the inorder traversal. In B-tree, a node can have more than two children. B-tree has a height of logM N (Where ‘M’ is the order of tree and N is the number of nodes). B+ tree eliminates the drawback B-tree used for indexing by storing data pointers only at the leaf nodes of the tree. Thus, the structure of leaf nodes of a B+ tree is quite different from the structure of internal nodes of the B tree.

Basis of ComparisionB treeB+ tree
PointersAll internal and leaf nodes have data pointersOnly leaf nodes have data pointers
SearchSince all keys are not available at leaf, search often takes more time.All keys are at leaf nodes, hence search is faster and more accurate.
Redundant KeysNo duplicate of keys is maintained in the tree.Duplicate of keys are maintained and all nodes are present at the leaf.
InsertionInsertion takes more time and it is not predictable sometimes.Insertion is easier and the results are always the same.
DeletionDeletion of the internal node is very complex and the tree has to undergo a lot of transformations.Deletion of any node is easy because all node are found at leaf.
Leaf NodesLeaf nodes are not stored as structural linked list.Leaf nodes are stored as structural linked list.
AccessSequential access to nodes is not possibleSequential access is possible just like linked list
HeightFor a particular number nodes height is largerHeight is lesser than B tree for the same number of nodes
ApplicationB-Trees used in Databases, Search enginesB+ Trees used in Multilevel Indexing, Database indexing
Number of NodesNumber of nodes at any intermediary level ‘l’ is 2l.Each intermediary node can have n/2 to n children.
quick-references blog differences b-tree b+-tree

Subscribe For More Content