5.31 B+ Tree Insertion | Create B+ Tree of Order 5 | Data Structures Tutorials

That is why I'm going to take order five and the these are the elements and we are going to create a B + 3. So if order is five, maximum children can be five, minimum children can be three, maximum keys can be four and minimum keys can be two. I hope you know the formula how to find out the minimum and maximum child and all. And these property this minimum property minimum children can be three right and here minimum keys can be two but this property of minimum children and minimum key this would not be followed by the root uh element if only one node we have and that is root and that is the leaf node only because we have only one node. So in that case that property would not be followed right this minimum children and minimum key because root can have minimum zero uh child and root can also have two children that is also possible and root can have only one key also that is also possible but maximum key should be four in root also right so how to insert how to create a B+ tree first data is seven right so we don't have any tree so first of all we are going to create a node and in this node in this node how many keys can be there? Four. 1 2 3 four. Right? And see you can also draw something like this. These are pointers. Five pointers. Why so? Because five children. Maximum children can be 1 2 3 4 and five. Now this is the pointer for this children. This is the pointer for this children. Like this. Right? and starting these pointers are null. So, but here I'm going to create a simple node without showing the pointers. Right? So, this is the node 1 2 3 4 keys can be there. First key is seven. Insert seven. Next is 10. See this this will also follow follow the property of BST binary search tree. Right? So, this 10 would be greater than this seven. So, it would be to the right of this seven. Fine. One. Now one is less than seven. So this that is why one would be to the left of seven. So the tree would be something like this. Here we will write one. Here we will write 7 and here we will write 10. These are going to be shift. Next is 23. 23 is greater than all of these. So here you can write 23. Fine. Next is five. Now where you can insert this five? Here. Five is greater than one but less than seven. So here you can insert five right according to the rule. But here on maximum keys can be four and this is overflow condition. Now what what you will do? You have to split the node and splitting will also be done from the middle element only and B + 3 and B3 always grow towards the root. So find out the middle element out of these. Middle element is this seven. Right? After inserting we are going to you are pretending that we have inserted this five and after that we are going to find out the median element. It's not like don't insert five and now find out the median element and split the node. No seven would go one level up. Another node would be created having maximum capacity 1 2 3 4. Right? And to the left of seven we have 1 and five. To the left of seven we have 1 and five. Capacity of this node is also 1 2 3 4 keys. And to the right of seven to the right of seven what we will have. To the right of seven we have 10 and 23. But the property of B + 3 is what? The data. This data should be present in leaf node. The data is present in leaf node only. Right? So we are going to put seven here 10 and 23. I'm going to follow the rule that to the left of this node to the parent left of this parent the data would be strictly less than this node and to the right of this we can uh write down either greater value or equal value. So 7 is equal to 7. So that is why we are writing seven to the right child of this one. Right? So see this is now the internal node and these are leaf node. See in internal nodes only the indexes are there. Now next is 15. Now where you can insert 15? Data would be inserted only in leaf node. 15 is greater than 7. Greater than 7 greater than 10 but less than 23. So here you will write 15 and here you will write 23. 17. Where you can insert 17? To the right of 15 and to the left of 17. So here you can insert 17. But this is not possible. This is overflow condition because maximum keys can be four. Now split this node from the median element. Median element is what? 15. 15 would go one level up. So we can can we insert 15 here? Yes. Because still we have three spaces left. So I'm going to update this tree only. 15 would go one level up. Right? And this node would be splitted. To the left of 15 we will write 7 and 10. Right? And to the right of 15 what you will write? 15 17 and 23. So to the right of 15 you will write 15 17 and 23. Next is 9. Greater than seven but less than 17. Go to this one. Greater than seven less than this 10. So here you can insert 9. Right? So the node would be 7 9 and 10 and still space of one element. Next is 11. Where you can insert 11? Greater than 7 less than 15 greater than 11. Here you can insert 11. Next 39. Here you can insert 39. 35. Now where you can insert 35 after 23 and before 39. So here you can insert 35. But this is overflow condition. Splitting would be done from the median element. So the middle element is 23. So 23 would go one level up here. Can we insert 23 here? Yes, we have still space. So I'm going to update this tree only. Here you will write 23. After 15 because 23 is greater than 15. And to the left of 23, we have 15 and 17. And to the right of 23, we will have 23, 35, and 39. So to the right of 23 you will write 23 35 and 39. So now next is 8. Where you can insert 8? 8 is greater than 7 less than 15 go to the side. Greater than 7 less than 8 9. So here you can insert 8. After seven and before 9 but this is overflow condition. So you are going to split now. Right? Splitting would be done from the middle element. The middle element is this nine. Nine would go one level up. So here you are going to insert nine. So in this node where you can insert nine after 7 and before 15. Right? So now the tree would be something like this. 7 9 15 and 23. Now this node is also full. To the left of seven we have 1 and five. So now here to the left of 9 and right of seven we are going to split this node. Huh? So 9 would go up. So to the left of nine we have 7 and 8. Here you will have 7 and 8. Right? And to the right of 9, 9, 10 and 11. 9 10 and 11. These are still same. 15 and 17. And to the right of 23 we have 23, 35 and 39. So now next is 40. Where to insert this 40? Here you can insert after 39 right. Next is 25. 25 is greater than 23 greater than all these 23. So go to this link. Now 23 25 is greater than 23 but less than 35. So here you can insert 25. But this is overflow condition. Again splitting would be done. Middle element is 35. 35 would go one level up here. But we cannot insert 35 here because this node is full. Now repeat the same step of splitting. Now here on see here also you will do splitting. So middle element from this is 15 15 would go one level up. Fine. So I'm going to do this splitting first of all. Right? After that we are going to split this node. So after this splitting I'm going to update in this case only. 35 would go here. 35 would go here. 35 is greater than 23. So we will insert here only. Right? To the left of 35, we have 23 and 25. 23 and 25. Right? And to the right of this one, we will have 35, 39 and 40. To the right, we will have 35, 39 and 40. But this is just a just the intermediate stage because we are going to split this node also. This is also full. This is also overflow condition. So middle element of this is 15. 15 would go one level up. So final the tree would be 15 would go one level up. To the left of 15 we have 7 and 9. 7 and 9. To the right of 15 what you should have 15 23 and 35. Right? So if you will write here 15 23 and 35. 15 is here also here also and 15 is also in the leaf node. Right? So leaf node data should be present in leaf node. That is fine. But these are internal nodes. Now this is also internal node. This is also internal node. So no need to repeat the data in internal nodes because the here only the indexes are there. So what's the point to repeat the data in the indexes only one index is enough to reach till the data. So here you will not write 15. This you have to take care. Fine. To the left of seven we have 1 and five. This one we have 7 and 8. To the right of 9 we will have 9 10 and 11. Now now see to the right of 15 we have 15 and 17. Right? So to the right of 15 we will have 15 and 17. But this would be to the left of this 23. 15 and 17. And after 23 after 23 you will have 23 25. And after 35 you will have 35 39 40. 35 39 and 40. So you can draw this tree something like this. Just just make this as a node having space of four. And one more important point about this B tree is what? See these leaf node are also connected with a link like this. Right? The data in the leaf node is present as a form of link list. So these are also connected like this like this like this like this. Fine. So finally if you have this tree so this leaf node would be connected to this then this then this then this then this all the leaf node are connected with a link. So here you can say in the root node we are having only one key but according to the rule minimum key should be two. See here children also minimum children can be three but here children are only two. So root node will would not follow the property of this minimum children and minimum key. So this is how we are going to create a B+ tree when odd value of this order is given. Fine. So I'll see you in the next video. Till then bye-bye.