Updated September 27, 2023
Difference Between B Tree vs B + Tree
B tree and B + tree is defined as a concept of self-balancing trees and each of the 2 concepts differing from each other in some aspects which we will talk about in this article, but before that, we should know that B tree is a generalization of a Binary search tree (where each internal nodes stores key which is greater than keys in the tree’s left subtree and is lesser than the tree’s right subtree) and each node of the B tree having more than one key more than 2 child nodes on the basis of the m value (m denotes the order of the tree) and B + tree is an advanced self-balanced tree and every path originating from the root of the tree to the leaf of the tree has the same length. There are some properties each of the trees exhibits and are the basis of points of differences between these 2 concepts and we will talk about it more in the upcoming sections.
Head to Head Comparison between B Tree vs B + Tree (Infographics)
Below are the top 8 differences between B Tree vs B + Tree:
Key Differences between B Tree vs B + Tree
Before we learn about the differences of a B Tree vs B + Tree, we need to understand some properties which must be followed for any tree to be classified as a B Tree, and after we understand them to look at the distinguished pointers for those mentioned properties which makes them a B + Tree.
- There can be the possibility of having the same number of children as the order of the tree i.e. a tree with order m can have at max m children.
- The internal nodes (internal nodes are the ones that are non-leaf and non-root) have a number at least half the order of the tree.
- There should be at least 2 children and the only exception to that is being a leaf.
- The number of keys should be one less than the number of children of a non-leaf node.
- The leaf must appear on the same level.
On contrary, in a B + Tree, the leaf nodes are linked together in a doubly-linked list and the internal nodes only hold keys and route the path to the correct leaf nodes.
On the basis of how B Tree or a B + Tree is constituted, we see that the properties mentioned above greatly affects the build of the tree and henceforth affects the way data is present in both the types of trees as in a B Tree, the internal and leaf node has data whereas B + Tree have data only in the leaf node. Similarly, the leaf nodes in a B Tree are not linked to each other whereas, in a B + Tree, the leaf nodes are linked in a doubly-linked list.
It is the search, insertion, and deletion time that gets affected as a result of the implementation of these 2 types of trees and is what we will see being mentioned as one of the key genres of comparison in the table in the next section and will mention the 8 genres of differentiation.
B Tree vs B + Tree Comparison Table
Comparison between B Tree vs B + Tree are given below:
|
Intention |
B Tree |
B + Tree |
| Pointers or Data present in | In a B tree, all the internal and the leaf nodes have data pointers. | The difference from the B tree is the presence of data pointers only in the leaf node and not in the internal node. |
| Search time | The search often takes more time as all keys are not necessarily present on the leaf. | The search is faster and more accurate as the keys in B + tree is present in the leaf node itself. |
| Links of the Leaf nodes | The leaf nodes in a B Tree are not linked to each other. | The leaf nodes are linked to each other thus enabling sequential access to the nodes. |
| Presence of duplicate or redundant keys | There are no duplicate keys in a B Tree as the keys can’t be repeatedly stored. | Here there is a possibility of redundancy as the internal nodes contain the keys and redundancy is inevitable. |
| Insertion Algorithm | During insertion into a B Tree, it might take more time and the outcome is not predictable sometimes. | The results of insertion is always the same unlike B Tree and the algorithm for insertion is faster as well. |
| Deleting Algorithm | A lot of transformation is undergone in case of a deletion of an internal node and hence deletion operation is a very costly affair in B Tree. | Since all the nodes are found at the leaf, hence the deletion of a node is an easier operation to handle in a B + tree. |
| Traversal to get data | Here, each of the nodes has 2 branches and the node here also contains some records, hence traversal till the leaf node is not necessary. | Since all the leaf nodes are at the same level and records are only available at the leaf nodes thus making the traversal till the leaf node an absolute necessity. |
| The Leaf nodes | In B Tree the leaf nodes are NOT stored as a structurally linked list | In B + Tree the leaf nodes are stored as a structurally linked list |
Conclusion
Going through all the differences, we are able to interpret that though there is some similarity at a superficial level for example, in terms of the problem statement they cater to till the similarity at a granular level, for example, presence of 2 to m children where m denotes the order of the tree there are a variety of pointers where both of them are poles apart and these are the pointers one would need to keep in mind not only while implementing concepts but also while architecting the software product and deciding on the key elements that are necessary for the software product. We use these 2 data structures in times when the data size is huge, and the main memory can’t contain the entire data and using the concepts of B Tree and B + Tree we store the data in disks. Ultimately the crux of the matter is that B + Tree’s search is faster and efficient.
Recommended Articles
This is a guide to B Tree vs B + Tree. Here we also discuss the B Tree vs B + Tree key differences with infographics and a comparison table. You may also have a look at the following articles to learn more –
