B-Tree Insertions

[00:00:00]
>> We now have all the beautiful parts here, and now we're gonna go through and we should start inserting and create a beautiful b-tree. Is everyone ready? All right, fantastic. So let's start by inserting 10. All right, we got a 10. We're looking good, okay. We're looking much better already, aren't we?

[00:00:21]
No, we're looking the same. Okay, it was the same thing last time. Come on people. All right, let's do number 4. Let's do, sorry 4, 20. We're gonna do 4, 20, what? We're gonna do 20 again, we inserted in. Are we looking better? No, it's the same thing, right?

[00:00:34]
Our order is 5, which means we can have a maximum of four keys, so keep that in your brain. Now, let's do 30. 30 goes in, awesome. Let's do 40. 40 goes in, awesome. Let's do 50, shoot. What do we do here? 50 can't go in, the rules, can't break the rules.

[00:00:54]
Anybody know?
>> Make it a child.
>> We make it a child. No, remember the tree grows upwards, okay? So this is where things get real wild. I'm gonna go like this and I'm gonna draw this and then I'm gonna take out the median. If we happen to have a tree in which only has, say like if we were to do an order 4, we would have something that would look like this, 10, 20, 30, 40.

[00:01:20]
And that would be our max where we have to do something and split it off, which means that we'd either have to be left bias or right bias. Meaning that we have more keys on one side than the other, but since we're doing an order 5, we have the same number of keys on both sides.

[00:01:33]
And you'll notice that there's two keys on each side, which happens to be what number? The minimum required number. So we know we can create nodes at this point. So, we've now inserted 50. 30 goes upwards. 30, it's now the root, and I don't know why I rolled the tongue on that one.

[00:01:51]
It just felt right in the moment. That means this side, this side, we now have this tree right here. We are growing upwards, okay. How fantastic is this? So let's insert another number. Let's insert 69, nice. We're gonna go 69, greater than, 69. Yes, right here. Get in there, awesome.

[00:02:10]
Now we're gonna do 70 again. We're gonna go all the way out to here. Now if we were to insert one more, something's gonna happen, right? Well, let's do it. Well, let's just say we're gonna insert 71. So now we hit the situation, we need to do something here.

[00:02:25]
We're gonna do what we did last time. We're going to split and promote. So 69, put it up here, create two subtrees, and add another one. So how does that work? Well remember, the 69 was in-between, which means that everything on this side was less than, which means that if it shares these two keys, it will be able to maintain the property of distinct, the most important part of the entire course so far.

[00:02:50]
So therefore we are able to maintain that, and on this side, we still maintain it cuz it's dead, it's on the Y side, it's on the greater side, so it actually works out. And so you just keep doing this over and over and over and over again. It's just, that's it.

[00:03:03]
That's insertion. And look at it, it's maintained order, it's not too complicated, it's actually a really simple insertion. I'm shocked at how easy it is to grow the tree. The shrinking of the tree on the other hand, is a little bit more complicated, okay? Wait, first off, is everyone tracking with insertion?

[00:03:22]
>> Yeah.
>> Good, cuz we should actually keep on going. You know why we should keep on going? Cuz I realized something really important. What happens if we keep going to the point where we need to expand this? Have we seen this? How do we divide the children out?

[00:03:34]
How do we do all that? I wanna make sure everyone's feeling ready, excited, they wanna know how to do that. So let's just keep on going and get it all the way to that spot to happen. So I'm just gonna just erase all that for a quick second, and let's go to order 4 cuz it's a little bit easier.

[00:03:50]
So that means our key minimum is gonna go to 1, our child minimum is gonna go to 2, our key max is gonna go to 3, and our child max is gonna go to 4, right? Everyone's tracking, awesome. So let's do that. I'm gonna reinsert these so we can just kinda grow this tree quickly.

[00:04:04]
So that means we're gonna go 10, 20, 30, we just hit our key max. We do 40, promote, I'm gonna do left biasing meaning that I want my left side to be larger than my right side. So this will become a tree, this will become a tree, 30 will be right there, goes upwards, awesome.

[00:04:22]
So now let's insert 50, 69, nice, 50, 69. And now, if we insert 70, we have to do the exact same thing. Again, we've already covered this. Again, left bias, 69 goes up, links are now right here, and we complete the list right here. Again, let's insert some other ones, let's do 5 and 3.

[00:04:45]
So we insert 5 and then let's do 3. 3 breaks the rule. Again, we do the exact same thing. 10 goes up, up to here. It works out because we knew everything on the other side of 10 was larger than 10, and everything on this side of 30 was smaller than 30, so this actually keeps on working out.

[00:05:06]
We do this, now we're looking good. So now let's just do one last item cuz the moment we do this one last item, we will break it at a larger level. Okay, so let's do a 2. Man, here we go. We're gonna insert A 1, so 1 gets inserted, bam, we just do the exact same thing.

[00:05:23]
Don't be clever, okay? Never be clever with algorithms. Just be clever enough with algorithms. All right, so, again, left bias. Put that 3 up here. I believe that was the one. It was a 4 or 3? It was a 3. It was a 3. All right, so now we have that, no, this one is now in violation.

[00:05:44]
What do we do?
>> We go another level up.
>> Boom, we go another level up. So what I'm gonna do is I'm gonna just erase all of that, and I'm gonna go like this. A, B, C, D, E. Okay, we're just gonna put them as letters, cuz sometimes it's easier just to look at something small.

[00:06:01]
Actually, hold on, let me just first move everything down. Cuz I realize I'm just running into stuff. All right, so we're currently violating at this level. Everyone has children A, B, I like X, Y, and Z. I didn't mean to rhyme but it was fantastic that it worked out.

[00:06:19]
So we need to simply break this and do it again. So left bias, take 30, put 30 up here. So we've maintained the properties right here, but this is all kind of goofy potentially. I just happen to actually draw this really, really nicely such that it maintained all the properties, right?

[00:06:41]
Cuz this would be greater than 10 and less than 30. And so that link maintains. This link maintains. This link maintains. This one maintains. This one maintains. And so that would be the growing up and it just keeps on going. You don't have to do too much other than you have to know how to move these things around.

[00:07:02]
Feels good, everyone's excited? Okay, so that's B tree insertion, very fun. I don't know, I think it's great times. All right, get rid of all this stuff.