B Tree vs B + Tree: Data Structure

Difference Between B Tree and B+ Tree

What is B Tree?

B-Tree is a self-balancing or special type of m-way tree. B-Trees are used mainly in disc access. If we want to understand the use of B-Trees, then we should think of the large amount of data that can’t be fitted in to the main memory which is RAM. When the number of keys is very large, the data is read from disc in the form of chunks or blocks. Disk is required to take more time to access as compared to the main memory access time. The idea behind of using B-Trees is to minimize the number of disk accesses it obvious if we reduce the number of disk accesses, then the searching time will also be reduced. Another advantage of the B-trees is, it has enough capability to store the large number of keys in a single node without increasing the height.

We already said that B-Tree is type of m-way search tree so it contains all of its properties which are given below:

• If the order of B-Tree is ‘m’ then, all nodes including root node can contain at most m-1 keys.
• Root node contains minimum 1 key.
•  All other nodes except root node contain minimum ceiling of (m/2)-1 keys.
• Every node of B-Tree has max m children.
• Root node can contain minimum 2 children.
• All internal nodes can contain minimum ceiling of (m/2) children.
• In B-Tree, all the leaf nodes should be at same level.

What is B+ Tree?

The B+ tree is referred as advance self-balanced tree because in B+ tree, the path length is fixed if we talk about every path from the root to the leaf of the tree. The meaning of same length is in the B+ tree all the leaf nodes present at the same level of the tree. In B+ tree, all the values are present in the leaf level.

Uses of B+ Tree

• Used in Dynamic Multilevel Indexing
• Used in Faster operations on the tree (insertion, deletion, search operations)
• Used in Database indexing

Comparison Table: -

B-Tree		B+ Tree
The keys and records can be stored in internal node as well as in leaf nodes of the tree.		The keys can be stored in the internal nodes and records are stored in the leaf nodes.
In the B-tree, the sequential access is not possible because leaf nodes are not connected to each other.		In B+ tree, the sequential access is possible because leaf nodes are connected to each other.
In B-tree, the records are stored either in internal nodes or in leaf nodes so because of this searching is quite inefficient in B-trees		In B+ tree, the records are stored in leaf nodes only so searching is quite efficient in B+ tree.
In B-tree, deletion of the internal nodes takes more time because we need to consider its child and the child may contain the record of the tree.		In B+ tree, deletion is very fast because the records of the tree are stored in the leaf nodes so we don’t need to consider the child of the internal node.
In B-tree, no redundant search keys are present		In B+ tree, redundant search keys may be present.