Difference between B-tree and B+-tree.
1 Answer
B Tree Index Files B+ Tree Index Files
This is a binary tree structure similar to B+ tree. But here each node will have only two branches and each node will have some records. Hence here no need to traverse till leaf node to get the data. This is a balanced tree with intermediary nodes and leaf nodes. Intermediary nodes contain only pointers/address to the leaf nodes. All leaf nodes will have records and all are at same distance from the root.
It has more height compared to width. Most width is more compared to height.
Number of nodes at any intermediary level 'l' is 2 l.  Each of the intermediary nodes will have only 2 sub nodes. Each intermediary node can have n/2 to n children. Only root node will have 2 children.
Even a leaf node level will have 2 l nodes. Hence total nodes in the B Tree are $2^{ l+1} - 1$. Leaf node stores (n-1)/2 to n-1 values
It might have fewer nodes compared to B+ tree as each node will have data. Automatically Adjust the nodes to fit the new record. Similarly it re-organizes the nodes in the case of delete, if required. Hence it does not alter the definition of B+ tree.
Since each node has record, there might not be required to traverse till leaf node. Reorganization of the nodes does not affect the performance of the file. This is because, even after the rearrangement all the records are still found in leaf nodes and are all at equidistance. There is no change in distance of records from neither root nor the time to traverse till leaf node.
If the tree is very big, then we have to traverse through most of the nodes to get the records. Only few records can be fetched at the intermediary nodes or near to the root. Hence this method might be slower. If there is any rearrangement of nodes while insertion or deletion, then it would be an overhead. It takes little effort, time and space. But this disadvantage can be ignored compared to the speed of traversal
Please log in to add an answer.

Continue reading...

The best way to discover useful content is by searching it.