B-Trees

[00:00:00]
>> And so, this is where the idea of a B-tree comes into play, all right? Why do they call them B-trees? I actually don't know why it's called specifically a B-tree. I didn't look it up, never really read about it, or I don't remember. Not really sure why.

[00:00:14]
People say they have really great applications in database indexing. It used to be for disk clap hairs when he has to look up stuff, and so that's why when you looked up stuff, you could have the minimal amount of disk reading. i know we don't do disk reading a lot of Zoomers are not even sure what a disk is, it used to happen all the time, all right?

[00:00:32]
It was a real thing. We had a disk when we were young. So it is, all right? So There's a couple rules to a B-tree. Now I've heard people specify it in two different ways, the minimum order or the order. I did not spell order right upstairs. There we go.

[00:00:51]
We're not gonna do the minimum order, we're gonna just do the order. I think it's probably easier to think of it in the minimum order, but think for the most part, most content I've ever seen has always specified it as order. So we're gonna stay there. So this is called an order of the tree.

[00:01:07]
So an order of the tree is the maxed number of children that can exist in a tree. So if we have an order of 5, that means our child max is 5, which means our key max is 4. Cuz remember, actually, as you very observantly pointed out, there's always plus 1 children for x keys.

[00:01:32]
So this is true, but there's also a minimum requirement in a B-tree. A minimum requirement, the Kmin is going to be the ceiling of your order divided by 2 -1. So that would be 3 -1 or 2. Every node must have 2 keys, which means the child minimum must be 3, all right?

[00:01:59]
Because there's always a plus one for your amount of keys. So these are the four rules. Now, there is one node that gets to break this rule, which is, okay, someone got confused by this. Here, hold on. I'll just make sure we're not confused by this. K minimum is your order divided by 2 ceiling.

[00:02:19]
Ceiling simply means that if it's 3.1, the answer is 4, all right? So it's integer division, the other direction. So that would be 2.5, the ceiling of 2.5, which is 3, then you minus the 1, which is 2. So that means your children min is going to be 3.

[00:02:37]
I used to chat to help me with this. It's very good to know when people get confused on these little things. Because sometimes it's easy to breeze by little details and then you just ruin it for everybody for the rest of the time, so this is a very important thing to remember.

[00:02:52]
So I'm just gonna put a little two right here. So there you go. If you have an order 4 it would slightly change everything. The key minimum would be 1, because of course the ceiling of 4 divided by 2 is 2. Then you got a -1, you'd have 1.

[00:03:08]
That means our children minimum would be a 2. That means our children max would be a 3, or I mean, our key max would be a 3, and our children max would be a 4, which means that we would have a 2, a 3 or a 4 amount of children at any one node.

[00:03:22]
And this is a special tree called a 2, 3, 4 tree. You've probably seen or heard that term at some point. That's where the name comes from. It's the amount of potential children that can be had. It's not minimum, max key, max children. It's just the amount of children you can have.

[00:03:37]
Okay, good times. So we'll stick with order 5 for now. So I'll just, yeah, get rid of those. Again, 5 max children which is gonna be 5-1 max keys, which is gonna be 3 children which is gonna of course be 3-1 keys or how did I arrive to that?

[00:03:53]
Again, 5/ 2-1 ceiling of that it is [SOUND] 2. Okay, now that we got that. A unique property about B-trees is that they grow upwards. Okay, it's the only tree in computer science that grows up. The rest of them, they all grow downwards. But this one, we grow upwards, which just makes it more exciting.

[00:04:14]
And one more rule, I think I said this already, just verbally, I just want to write it down. The root can have one child. It can have one key, or no sorry, the root can have one key. It's the only one that can break the lower bound rule because it makes sense, all right?

[00:04:29]
If I were to insert 10 into an empty tree, there's just 10. The root has to be able to violate the minimum key rule or else you could not construct. All right, everyone feels good about that? We're feeling good?
>> I have a question. Wouldn't the ceiling division -1 basically be the same as a floor division?

[00:04:52]
>> No. So if we did a floor division instead, 5/2, or really this is called integer division, you would actually get 2, all right? So then 2- 1 means that our minimum key would be 1 instead of 2.
>> All right, but taking away the -1,
>> Taking away the -1?

[00:05:11]
Also no, because then if you did an even number, the floor on that one is 2, and the ceiling on that one is 2.
>> Okay.
>> Because there's no remainder at that point. So without any remainder, so even numbers, the floor and the seal are the same thing.

[00:05:30]
I usually call it a seal. And in my head I hear [SOUND] I just think it's funny. So the seal is that way. I don't know why I'm telling anybody that. It's how I live my life. Okay, 2 there we go.