What is a B-Tree?
B Tree is a self-balancing tree data structure. It stores and maintains data in a sorted form where the left children of the root are smaller than the root and the right children are larger than the root in value. It makes searching efficient and allows all operations in logarithmic time. It allows nodes with more than two children. B-tree is used for implementing multilevel indexing. Every node of the B-tree stores the key-value along with the data pointer pointing to the block in the disk file containing that key.
Properties of B-Tree
- Every node has at most m children where
mis the order of the B-Tree. - A node with
Kchildren containsK-1keys. - Every non-leaf node except the root node must have at least ām/2ā child nodes.
- The root must have at least 2 children if it is not the leaf node too.
- All leaves of a B-Tree stays at the same level.
- Unlike other trees, its height increases upwards towards the root, and insertion happens at the leaf node.
- The time complexity of all the operations of a B-Tree is O(log n), here ānā is the number of elements in the B-Tree.
Example of a B-Tree of order 4
What is a B+ Tree?
A B+ tree is similar to a B-tree, the only difference is that their leaves are linked at the bottom. Unlike B-tree, the nodes of the B+ tree do not store keys along with the pointers to the disk block. The internal nodes contain only keys and the leaf nodes contain the keys along with the data pointers. All the internal nodes are present at the leaves and are linked together and can be traversed just like a linked list.
B+ tree also removes one drawback of using B-tree. The internal nodes of the B-tree also store keys along with data pointers which take more space and significantly reduce the number of keys that can be stored at a node of the B-tree. Due to this the number of levels increases and searching time also increases. Unlike this, the B+ tree can store more keys than the B-tree of the same level because of their feature of storing pointers only at the leaf nodes. This contributes to storing more entries at fewer levels in the B+ tree and lessens the searching time for a key. This makes the B+ tree very efficient and very quick in accessing the data from the disks.
Example of B+ Tree
Differences between B-Tree and B+ Tree
| B-Tree | B+ Tree |
|---|---|
| All internal nodes and leaf nodes contain data pointers along with keys. | Only leaf nodes contain data pointers along with keys, internal nodes contain keys only. |
| There are no duplicate keys. | Duplicate keys are present in this, all internal nodes are also present at leaves. |
| Leaf nodes are not linked to each other. | Leaf nodes are linked to each other. |
| Sequential access of nodes is not possible. | All nodes are present at leaves, so sequential access is possible just like a linked list. |
| Searching for a key is slower. | Searching is faster. |
| For a particular number of entries, the height of the B-tree is larger. | The height of the B+ tree is lesser than B-tree for the same number of entries. |
