B Tree in Data Structure

This is an PPT of Data Structure. It include the following topic "B Tree in Data Structure ".

1. TOPIC – B TREE DIVYANSH PARMARTHI ROLL NO. :- MCA/25016/18 BIRLA INSTITUTE OF TECHNOLOGY

2. B- TREE A B-tree is an m -way tree. In a B- tree all leaves are on the same level. All non-leaf nodes except the root have at least  m / 2  children. The number m should always be odd. A leaf node contains no more than m – 1 keys

3. Constructing a B- tree Suppose we start with an empty B-tree and keys arrive in the following order:1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 We want to construct a B-tree of order 5 The first four items go into the root: To put the fifth item in the root would violate condition 1 2 8 12

4. Therefore, when 25 arrives, pick the middle key to make a new root 8 1 2 12 25

5. INSERTION Inserting 6, 14, 28 we get :- 8 1 2 6 12 14 25 28

6. Adding 17 the right leaf node would over-fill it, so we take the middle key, promote it (to the root) and split the leaf 8 17 12 14 25 28 1 2 6 Adding :- 7, 52, 16, 48 8 17 12 14 25 28 1 2 6 16 48 52 7

7. Adding 68 causes us to split the right most leaf, promoting 48 to the root, and adding 3- causes us to split the left most leaf, promoting 3 to the root adding - 26, 29, 53, 55 Adding 45 causes a split of and promoting 28 to the root then causes the root to split 3 8 17 48 52 53 55 68 25 26 28 29 1 2 6 7 12 14 16 25 26 28 29

8. B-Trees 8 17 3 8 28 48 1 2 6 7 12 14 16 52 53 55 68 25 26 29 45

9. 12 8 2 3 13 27 10 11 Deleting 8 – It might force us to move another key up from one of the children. It could either be the 3 from the 1st child or the 10 from the second child. However, neither child has more than the minimum number of children (3), so the two nodes will have to be merged. Nothing moves up. DELETION

10. 2 3 12 13 27 10 11

11. ADVANTAGES It is a self balancing tree. It not a ling tree all the leaf nodes are at same level.

12. DISADVANTAGES Insertion and deletion are complex in B-tree .

13. REFERENCES https://courses.cs.washington.edu/courses/cse373/05wi http://cecs.wright.edu/~tkprasad/courses/cs707/L04-X-B-Trees

14. THANK YOU