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 Comparision | B tree | B+ tree |
|---|---|---|
| Pointers | All internal and leaf nodes have data pointers | Only leaf nodes have data pointers |
| Search | Since 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 Keys | No duplicate of keys is maintained in the tree. | Duplicate of keys are maintained and all nodes are present at the leaf. |
| Insertion | Insertion takes more time and it is not predictable sometimes. | Insertion is easier and the results are always the same. |
| Deletion | Deletion 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 Nodes | Leaf nodes are not stored as structural linked list. | Leaf nodes are stored as structural linked list. |
| Access | Sequential access to nodes is not possible | Sequential access is possible just like linked list |
| Height | For a particular number nodes height is larger | Height is lesser than B tree for the same number of nodes |
| Application | B-Trees used in Databases, Search engines | B+ Trees used in Multilevel Indexing, Database indexing |
| Number of Nodes | Number of nodes at any intermediary level ‘l’ is 2l. | Each intermediary node can have n/2 to n children. |