B+ Tree
•In
B-trees the traversing of the nodes is done in inorder manner which is time
consuming. We want such a data structure of B-tree which will allow us to
access data sequentially, instead of inorder traversing.
• Definition : In B+ trees from leaf
nodes reference to any other node can be possible. The leaves in B+tree form a
linked list which is useful in scanning the nodes sequentially.
• The
insertion and deletion operations are similar to B-trees.
•Example : Consider following B+tree.
• From
leaf node only any key can be accessed of entire tree. There is no need to
traverse the tree in inorder fashion.
•Thus
B+tree gives faster access to any key.
Ex. 5.2.1 Construct a B+tree for F, S, Q, K, C,
L, H, T, V, W, M, R.
Sol ; The method for
constructing B+tree is similar to the building of B tree but the only
difference here is that, the parent nodes also appear in the leaf nodes. We
will build B+tree for order 5.
The
order 3 means at the most 2 keys are allowed.