B-Tree vs B+ Tree Memory Usage
This blog helps to understand the difference in using B-Tree and B+ Tree in databases.
Let’s understand how each of the mentioned data structure works.
B-Tree
B-Trees stores both data and index on each node.
In such databases, due to bigger tuple, it is difficult to keep everything in memory. Hence some of the records are managed outside main memory by the use of data pointers.
When some of the data gets stored on disk, there are few disadvantages.
- Accessing disk will take longer as the searching requires numerous cycles of disk hops.
- The search operations of external drives are generally not very efficient.
- Memory management is poor when data has to be re-arranged after a search operation (add, delete, search).
B+ Tree
B+ tree eliminates the drawback B-tree, 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.
It is significantly easy to store all the indexes in main memory as the data resides only on leaf level.
- In a B tree search keys and data are stored in all nodes. But in a B+ tree data is stored only in leaf nodes.
- Full scan of a B+ tree is very easy because all data are found in leaf nodes. Full scan of a B tree requires a full traversal which might require additional disk accesses.
- In a B tree, data may be found in leaf nodes or internal nodes. Deletion of internal nodes is very complicated. In a B+ tree, data is only found in leaf nodes. Deletion of leaf nodes is easy.
- Insertion in B tree is more complicated than B+ tree.
- B+ trees store redundant search keys but B tree has no redundant value.
- In a B+ tree, leaf node data is ordered as a sequential linked list but in a B tree the leaf node cannot be stored using a linked list. Many database systems’ implementations prefer the structural simplicity of a B+ tree.
