B+ Tree Insertion | B+ Tree Creation Step-by-Step | Data Structure Tutorial

[00:00:00]If order is given of a tree then maximum children would be same as the order given m minimum children would be mx2 ceiling maximum keys would be m minus one and minimum keys would be mx2 ceiling minus one right so here I'm going to take this example order is four so here maximum children can be four right minimum children can be two maximum keys can be three and minimum keys can be one except root node These rules are not applied on root node. Root node can have uh maybe two children.

[00:00:35]Root node can have zero child. Root node can have one key like that. Now the one main important property of B+ tree is what? In B+ tree the data see this given data this data is stored only in leaf nodes right and in B tree data is stored in leaf node as well as in internal nodes but here the data is stored only in leaf node. Now what is stored in internal nodes in B+ tree only the pointers or you can say the indexes fine indexes to the data which is stored in the leaf node those indexes are stored in internal nodes and second important point is the data which is present in leaf node those data is present in a form a link list right all the leaves are connected with a link with each other I'll show you how when we are creating a B+ tree with this example right so these are the two main differences is I'm going to make a proper video on B+ 3 properties and how B+ 3 are different from B3. In this video, I'm going to tell you how data is to be inserted in B plus tree. Right?

[00:01:47]See, and B plus tree, see B tree is what it was a generalization of BST, binary search tree. So data in parent node, right? So the data to the left of parent is always less than parent and data to the right of parent is always the greater than that parent. So that property is always that property is also followed in B3 as well as in B+ 3. So now let us start. See here order is four. So initially no is there tree is empty. So we are going to construct a node you can say right and that node can have maximum how many keys? Three keys.

[00:02:25]So that node can have maximum 1 2 three keys and maximum children can be 1 2 see 1 2 3 and four. So in between these four links only three keys are possible.

[00:02:39]Right? So now see first first number is one insert one. So we can insert one right. So next next is four. Now where four is to be inserted? Four is here only one node is there. Right? So four is greater than this one. So four is to be inserted to the right of this one. So here we will insert four. Next is seven.

[00:03:01]7 is greater than one also greater than four also. Here we will insert seven.

[00:03:06]Next is 10. Now where we can insert 10 after this seven here but it is not possible. You cannot insert 10 in this node. Why so? Because it is overflow condition. Maximum keys in a node can be only three here. Fine in this case. So now what should be done? Now this node should be splitted.

[00:03:29]Now B3 and B +2 also always grow towards root root upward direction not to the towards leaf direction. Right? So we are going to find how how this node is to be splitted. Now find out the middle element. Now here we have four nodes. Right? See don't do this mistake that 10 you are supposed to insert. We cannot insert 10 here. So remaining elements are 1 2 and three. Find out the middle of this one. Four. Four would go up and one is to the left of four and seven is to the right of four. No, you are pretend you have to pretend that that you have inserted this 10. And now we are going to split this node, right?

[00:04:12]But actually we haven't inserted because we cannot insert maximum limit is only three keys. So now the middle element can be this one and this one because we are having even factor four. Right? So if you if you consider this as a middle element and you will split from this node you will split from this data then the tree would be left biased and if you consider seven as a med middle element and you split from this node then you the tree would be right biased. So it's up to you. You can take four also. You can take seven also. But in starting if you if you construct the left bias tree then during the completion of the complete tree you are supposed to follow that rule also. to the left biased tree and if here you selected the tree as right biased then in the all the complete tree you are going to follow that rule that right biased rule right so here I'm taking seven as middle element I'm going to construct right biased tree right you can construct left biased also and so your answer would be different from my answer but that is also correct right so now seven suppose seven is middle element so I'm going to split from this data now how splitting would be done seven would go one level up or you can say to its parent. Now here we don't have any parent so seven would go up and that seven would become parent. Now the tree would be something like this. See seven would go up.

[00:05:38]So create another node. The maximum capacity is three keys to the left of seven. To the left of seven we have one and four. One and four.

[00:05:50]Right here also we can insert one more data. And to the right of seven, to the right of seven, what we can insert?

[00:05:57]Maximum capacity is three. To the right of seven, we have 10. Right? Plus in B + 3, what you will insert? You will insert this seven also in this node. 7 and 10.

[00:06:10]Why? So, because see, I have told you in B+ the data, all the data, this data should be present in leaf node, right?

[00:06:19]So if you do not insert seven here. So this is the leaf node and seven is not present in the leaf node. So data should be present in leaf node. Now why you are inserting seven to the right of this this seven. Why can't you insert seven here?

[00:06:34]So another rule is that to the left of this one all the data should be strictly less than this node. Right? And to the right of this node to the right of this node from where you are going to split to the right of that node the data can be either greater than or equal to this node. So seven is equal to this seven.

[00:06:56]So we we are going to insert seven to the to this right side of this seven to the right child of this seven.

[00:07:04]Right? Now see this seven is only for the index value or you can say just pointer to this leaf node. actual data is present here. Right? Another thing I have told you all the leaf node are connected with a link. The data is stored in the form of a link list. So this this leaf node is also connected with this one using a link with this leaf node. Right? Now next we are going to insert is this 17. Now where 17 can be inserted? Always data is to be inserted in the leaf node that you have to take care. Now 17 is greater than seven. So go to go for this link. 17 greater than 7 greater than se this 10.

[00:07:49]So here you will insert 17. Next is 21.

[00:07:53]Where 21 can insert? 21 is greater than 7 greater than 7 10 and 21. So here you can insert 21.

[00:08:00]But actually we cannot insert overflow condition is there. Now you have to split this node. Now horse plating is to be done. The middle take the middle element and that middle element would go one level up. Right? So now I'm constructing the right bias tree. So here I'm going to take 17 as middle element. So 17 would go to its parent node or you can say one level up. So here you can insert 17 because two spaces are still free. So now the tree would be 7 and 17 and here still we have one space left. Same here we have one and four right and 17 would go up. So to the left of 17 7 and 10 to the left of the 17 we have 7 and 10. Right? Node is maximum capacity of node is three. So one space is free. And to the right of 17 to the right of 17 the data would be 17 and 21.

[00:09:01]Right?

[00:09:02]because the data should be present in leaf node. Fine. So now next is 31. Now where you can insert 31 greater than 7 greater than 17. So go to this link greater than 21. So we'll insert 31 here only. Now next is 25. Where you can insert 25? 25 is greater than 7 greater than 17. So go to this link. Greater than 17 greater than 21 and less than 31. So where you can insert 25? here after 21 before 31 right because uh it is uh BST also you have to follow the property of BST fine now this cannot be done overflow condition is there now splitting would be done now splitting is what find the middle element so I'm going to construct the right bias tree so middle element out from this 17 21 and 31 is 25 so 25 would go one level up so 25 would go here only fine Now I'm going to update this this tree only. So 25 would go here. So still we have one space left. So we can insert 25 here.

[00:10:07]And if you're splitting from this node then to the left of 25 we have 17 and 21. Fine. To the left of this we have 17 and 21. And to the right of 25 what would have? 25 and 31. So to the right of 25 you will have 25 and 31 and one node is still free and here also one node is still free. Now next is 19 where you can insert 19. 19 is greater than 17 but less than 25. So go to this link 19 greater than 17 but less than 21 less than 21. So here you will insert 19 and 21 would go here.

[00:10:48]Next is 20. Where you can insert 20?

[00:10:52]Greater than 17, less than 25, greater than 17, greater than 20, and less than 21. So you can insert 20 at this place.

[00:11:01]17 here. You'll write 17, 19, 20 and 21. Right? This node would be something like this. But you cannot insert 21. Here you have to split this node. From where you are going to split, middle element is 20. So 20 would go up.

[00:11:18]Fine. And here also now you cannot insert 20 because this node is also full. Now you'll repeat the same step of splitting. You'll split this node also.

[00:11:30]Fine. And that that node that from where you are going to split that element would go one level up. Fine. So I'm going to uh first of all do one splitting from this node only. Fine. So if this node is splitted then 20 would go one level up. So now now this tree would be something like this 7 17. So now if 20 would go one level up. So in this node where 20 can go after this 17.

[00:11:58]Here you will write 20 and here you will write 25.

[00:12:03]Right? And to the left of seven we have 1 and 4.

[00:12:08]To the left of 17 we have 7 and 10. To the right of 17. Now from here splitting is done. 20 would go up. So to the left of 20 we have 17 and 19. To the left of 20 we have 17 and 19. And to the right of 20 we will have 20 and 21. So here you will have 20 and 21. And to the right of 25 you will have 25 and 31. But this is the intermediate stage.

[00:12:37]We are not done. That is why I'm drawing this something like this. Now again this is not al this is not possible. You have to split this node also. Now from here middle element is 20. 20 would go one level up. So after that after that after this splitting tree would be something like this. See 20 would go one level up one another node would be created having maximum space of three keys. To the left of 20 we have 7 and 17. 7 and 17. at this level right to the right of 20 according to the rule what should be the keys 20 and 25. So to the right of 20 we should have 20 and 25 right and as it is these elements would be 1 and four.

[00:13:32]To the right of this we have 7 and 10. To the right of 17 we have 17 19 right? Now these are leaf nodes right and this is internal node and this is also internal node. So now the rule is these keys this cannot be repeated in internal nodes. So here you have written just 20. So here you cannot write this 20. you are going to cross 20 from here because what actual data is in leaf node and in internal nodes we just have indexes. So what is the point to repeat the same index again and again? We just need one index and using that index or using that pointer only we can reach to the actual data. Now right so that is why in this internal nodes we are not going to repeat the same data. So here we have written 20. So we are not going to write 20 here.

[00:14:37]Fine. So here you will just write 25.

[00:14:41]So now here 20 is not there. To the left of to the left of this 25 the data is to the left of 25.

[00:14:51]The data is what? 20 and 21. See to to the left of 25 we have 20 and 21. 20 and 21.

[00:15:01]Fine. And to the right of 25 we have 25 and 31.

[00:15:11]So this is from this stage the tree would be something like this. So I'm going to rub this intermediate stage.

[00:15:20]Fine. Now here 20 is not present. So here we don't have any element. 20 is not there.

[00:15:28]Fine. You just have 25. Now next next is 28. Now where 28 can go? 28 is greater than 20. Yes, greater than 25. Go to the right side of 25. Go to this link.

[00:15:40]Greater than 25 but less than 31. So here you will insert 28.

[00:15:45]Here you will write 31. Next is 42. 42 can go to right of 301. So here you can insert 42. But actually you cannot insert this is overflow condition. Again splitting would be done and middle element is 31. 31 would go one level up here only. We have a two space left. So that is fine. 31 can go here. So after this the tree would be something like this. We have 20.

[00:16:09]Here we have 7 and 17.

[00:16:13]To the right of 20 we have 25 and and 31. 31 would go one level up. So here here we have 31.

[00:16:25]Right? These elements would be same 1 and four. Here you'll write 7 and 10.

[00:16:30]Here you will write 17 and 19. Fine. To the left of 25 would be 20 and 21.

[00:16:37]Right? And now to the right of 25 would be see 31 would go up. So to the left of 31 the data is 25 and 28. To the left of 31 the data is 25 and 28. And to the right of 31 31 and 42.

[00:16:56]Fine. And yeah, I forgot one more thing.

[00:16:58]See this link, this link will all the present in all the between all the leaf nodes. From this leaf node to this one, from this to this, from this to this, from this to this, from this to this. So this link would be present in all the leaf nodes like this. You have to insert this link also. And from here to here, something like this. Right? This is the final B plus 3. Here also you are having that space of the node is having space of three keys. So here I have shortage of space that is why I have just made a little bit mashed up. Fine. So I hope you are getting this is the tree. Fine.

[00:17:35]These nodes are having space of three keys right? Maximum you can insert three keys. Now see as you can see this this data this data is present in the leaf node. All the data you can check fine and in these internal nodes we are having just the indexes fine or you can say pointers as well as these these leaf nodes are also linked with each other. So when you are going to access a data that is why see that is why in B+ searching is very easy because the data is present in the leaf node.

[00:18:07]You have to just fetch the root block this block and only one leaf one leaf node because one this this leaf node is having the pointer to this leaf node then this then this then this and something like this fine so searching is very easy when data is stored in the form of B+ tree. I'm going to discuss with you all the properties of B+ 3 in uh next video and in next video we are also going to discuss how to delete a data from B+. Fine. So till then, bye-bye. Take