B+ Tree...

Examples for Insertion of data in to a B+ Tree

B+ tree is a rooted tree that consist of a root,internal nodes and leaves.In a B+ tree of order ( or branching factor) n should satisfy the following properties.

• From root to leaf all the path's length should be same.

• Each node that is not a root or a leaf has between (n/2) and n children. 

• A leaf node has between ((n-1)/2) and n-1 values. 

• If the root is not a leaf it has at least 2 children .

• If the root is a leaf (there are no other nodes in the tree) it can have and 0 and (n-1) values.

Example 01-Enter numbers in to a B+ Tree

Branching factor-5
Number Sequence-5,10,15,20,25,30,35,40,50,55,65,70,75,80,90,95

Not a root or leaf has children between = (n/2) , n

                                                                  

                                                                   =(5/2), 5

             

                                                                   = 3,5

Leaf node has values between                =((n-1)/2) , (n-1)

                                                                  =(4/2), 4

                                                                  =2,4 

Example 02-Enter Strings to a B+ Tree

When you entering strings to a B+ tree you should consider the alphabetical order.

Branching factor=3

Colombo,Kandy,Galle,Badulla,Gampaha,Kottawa,Kalutara

Not a root or leaf has children between = (n/2) , n

                                                                   = 2, 3

Leaf node has values between                =((n-1)/2) , (n-1)

                                                                   = 1 , 2

Advantages of B+ Tree

• Insertion, Deletion, Update does not affect to the performance since it is a balance tree structure.

• Searching data is becomes more easy since all records are stored only in the leaf node.

• Minimizing disk accesses by lowering the tree height due to large node fanout.

• Keys are used for Indexing.

Disadvantages of B+ Tree

• This method is less efficient for static tables.

By : Pramodi Samaratunga      -  University Of Moratuwa 

       Madhusanka Edirimanna  -  University Of Moratuwa