B+ Tree

B++ Trees concept and usage of B+Tree in Data Structure

1. Topic B+ TREES Presented by: Mujahid Hussain Jalbanee ( Student of Software Engineering)

2. Tree: Tree is collection of nodes. Nodes have data and pointers. Pointers can be dynamic and can be thousands. Files are just like leaves. 1 st node called Root. Sibling nodes have same parent node. Path means to go towards particular node.

3. B+ Trees: Every node has pointers to other nodes and key values. If there are N pointers then there can be N-1 number of key values. Key values are repeated from root node to leaf node because data pointers are located at leaf nodes.

4. B+ Trees Structure. A B Values < A Values >=A && <B Values >= B

5. B+ Tree Insertion: Lets take the following elements 2, 5, 7, 10, 13, 16, 20, 22, 23, 24…. Let be number of pointer, indirectly, 3 key values can be there in a node at a maximum case…. Insert 2,5,7…. Now insert 10…. 2 5 7

6. Continue…….. When we insert 10 then node will be break down into two.. After inserting 10.. There should be a parent to look after when there nodes > 1, so copy 7 into parent node…. 2 5 7 10

7. Lets see…. Insert 13, 16….. Node again breaks 7 2 5 7 10 Continue……

8. After inserting 13 and 16… . Nodes over flows…. After insertion…. 7 10 13 16 2 5 13 16 7 13 7 10 Continue…..

9. Insert 20 and 22 Violation… above 3 keys… again break up… 13 and 16 in one 20 and 22 will be in another new node… and then should copy in the parent node…. 13 16 20 22 2 5 7 10 13 16 20 22 7 13 20

10. Now lets insert 23 and 24… we can directly insert 23…. 7 13 20 2 5 7 10 13 16 20 22 23

11. Now insert 24…. Node over flows… So, we should break up and copy 23 to the parent.. But this time parent node is over flows.. Now break down parent node and move the smallest element from second partition to newly created parent node… 20 22 23 24

12. After inserting 24…. 13 7 20 23 2 5 23 24 20 22 13 16 7 10

13. When number of search-key values < (n/2)-1 LEAF NODE Redistribute to sibling Right node not less than left node Replace the between-value in parent by their smallest value of right node… Merge (contain too few entries) Move all values, pointer to left node Remove the between-value in parent… B+ Trees Deletion

14. 13 18 9 13 13 14 16 9 10 14 16 14 18 Now delete 10…. After Deletion…..

15. Now delete 10…. After deletion…. 9 10 13 14 18 22 13 18 22 9 13 14

16. Non-Leaf Node.. Redistribute to sibling Though parent Right node not less than left node Merge(contain too few entries) Bring down parent Move all values, pointers to left node Delete the right node, and pointers in parent….

17. 5 20 8 3 3 1 Some sub tree Now delete 3, where n=3….

18. After deletion 3…. 20 5 8 1 Some sub tree

19. Advantages : Automatically adjust the nodes to fit the new records. It re-organizes the nodes in the case of delete. Good space utilization nodes contain only to the pointers to the records and leaf nodes contain records. It is suitable for partial and range search too.

20. Disadvantages : There is no 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.