Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu. So, all right. Um So, this is a 2-3 tree. So, as you can see, uh every node has So, the 2-3 is either two children or three children. Every node can have either one key or two keys. And this is the correlation is that every uh for So, if there are n keys in a node, it has n + 1 children. So, the way that works is well, it's a similar similar to binary search tree, right?

So, if you have value here, the two children surrounding it, so this side is less, this side is more. So, it's essentially in sorted order going in an in-order traversal. So, left left child, root, right child. So, in order, it's sorted. So, generally, a B-tree will have some nodes. Uh so, let's say n and n + 1 children. And if you take anything in the middle, look at the two children, all the keys in this subtree are smaller than the key here, and all the C-trees keys in this subtree are larger than the key here. So, that's the general node. Okay. So, uh before we go into more details of the properties and everything.

So, the question is why use B-trees? So, let's like if we do a quick uh depth analysis, we can see that the depth is still log n, right? Is that clear to everyone? Sort of why the depth is log n? Because you have you have branching just in B-trees like in binary search trees. In fact, you have more branching. But, in any case, the depth is still log n. But, why use B-trees over uh binary search trees? Any of you have a reason? Why would prefer to use B-trees and not So, like all the operations still log n. Any guesses? Done? Okay. Well, okay. The reason is well, memory hierarchy. So, in normally in algorithms, we just assume that the computer has access to like memory and you can just like pick up things from disk in constant time and do your operations with it and you don't worry about caches and everything.

But, that's not how computers work, right? So, in a computer, you have So, those of you have taken like some computer architecture class, 6.004 or something, you will know sort of that it's hierarchy. So, there's a CPU. So, let's write somewhere. Uh So, you have your CPU. And near your CPU, you have some registers. You have your caches, L1, L2, L3, whatever. You have your RAM. You have disk after that. So, disk is the slowest. Then you have your I don't know, your cloud and whatever. So, like each level, your memory size grows and your access time grows as well. So, in the basic memory hierarchy model, we have just two levels of hierarchy, let's say.

So, you have cache connected by a high-bandwidth channel to the CPU. And you have a low-bandwidth channel to disk. So, the difference is So, essentially, you can consider that cache to have like infinite speed. Cache just like you whatever you can take it You don't have any cost for bringing in stuff from cache. So, but it it but it's finite size. So, the way cache works is it has a bunch of words. It has a finite finite number of words. So, let's say each each word has size uh size B. And let's say you have m words. However, hard disk is just let's say infinite memory, but it has a some some cost associated to a accessing things.

Okay. Also, when you access things from hard disk, you copy them into cache. And you copy a block of size B. You take it up from the hard disk and you try like you take a block and you put it into cache. And you have to get rid of something because it's finite. So, what you want to do is you want to utilize those that that B block efficiently. You you you don't you don't just want to like bring a B block every time you want to access a new node. In a binary search tree, like normal operations are what? You start at the root, go to a node. So, but that's not very easily correlated with this, right?

So, if you want to utilize the entire block, you would want something like a block which sort of goes down the tree. But, that's but that's not how binaries are stored. Binaries are stored this way. So, that's the nice thing about B-tree B-trees. So, since you can make So, this is just a 2-3 tree. This is not a general B-tree. A general B-tree will have a bunch of nodes. And we'll come to that number. But, generally, you want to make that number of nodes something like the uh cache What is the cache the word size in the cache? So, once you do that, you can get an entire node from disk, like work on that, and then like get another entire node.

So, like your height is reduced. And you can do your operation much quicker because you don't are not accessing accessing disk every time you're going down a level. I mean, you are actually You are accessing disk every time you go down a level, but you're get like you're utilizing the whole block when you're accessing disk. Good? Sort of makes sense? Okay. So, let's write down the specifications for a B-tree for B-trees now. Mm. All right. So, it's good. So, So, number of children. So, okay. First of all, a B-tree has something called uh branching factor. So, in the 2-3 tree, the branching factor is two.

So, what that means is simply it's a it's just bound to number of children. So, the number of children has to be greater than equal to two. Other than the root node, the root node can have less than B children. It's fine. Also, it's upper bounded by 2B + 1 2B. Uh notice that this is a strict upper bound. So, you can have at most 2B - 1 keys in the children from a node. Also, remember that the number of keys The number of keys is one There's just one less than the number of children. Therefore, these inequalities That's that's not right. There we go. Uh these inequalities just get reduced by one.

So, you have 1 - 1 and you have 2B - 1. So, number of keys can be between B - 1 and 2B - 2. The rationale for that will become clear up Is B the height of the tree? No, B is the branching So, B B is the branching factor. So, that is number of children. Like it's not a number of children, but it's it's on the number of children. So, like in the 2-3 tree, so B is equal to two. And this is a 2-3 tree. So, the two refers to you can have either two children or you can have three children. So, and so the here the the upper bound on children is 2B - 1, right? 2B - 1 is equal to three. So, you can have either two or three children.

And correspondingly, you can have either one or two keys in a node. Makes sense? Cool. Okay. So, coming back to this. So, the root does not have the have the lower bound. The root can have one child in any tree. So, you have a B equal to five tree, the root can still have one child. Sorry, not one child. One key element, two children. All right. It's good. Also, it's completely balanced. So, all the leaves are the same depth. So, like you can So, you can see it here, right? So, all the So, you don't you you can't have like a dangling dangling node here. This is not allowed. You have to have a leaf.

You have to have something going down, and everything ends at the same level. All right. So, that's the thing. So, Also, the leaves obviously don't have children. So, the this this condition is uh violated by a leaf. Okay. All right. So, So, that's the basic structure of a B-tree. Uh now, so the first operation we'll consider on B-trees is searching. So, that should be relatively straightforward, right? So, remember how searching is done in the binary search tree. You bring in a value x, compare it to the key. Let's say x is less than k. You go down this path. Let's say x is greater than k. You go down this path.

So, similarly in a B-tree. So, let's say you bring in a value. Let's say you are looking for 20. So, you bring in 20. Compare it to this. 20 is less than 30. So, you go down here. Now, you have three values Sorry, two values. So, where does 20 fit in here? Not here, not here. It fits here. Okay, go down this tree. You find 20. That's it. So, in general, you bring in a key key k. You look at this node. And you go through all the values. So, uh something I forgot to mention. So, which should be clear, all the all the keys in a node, they're sorted one after the other. So, your values go like this.

So, they're increasing in this way. Makes sense? Okay. So, So, you bring in a key, look at all the keys in the node you're looking at, pick the one pick the place where K fits in. Unless it's already in the node, then you're done. You you found it. Otherwise, let's say the K fits in between these two these two guys. So, you go down this child and continue. So, searching is log n, similar to BSTs. Okay. Okay, so searching is not very interesting. So, okay. So, next is insertion. So, insertion is less more interesting than searching. So, what you do in insertion is you Oh. Okay. Well, I guess we start start run again.

Okay. Uh should we move back to the original room? Okay. Let's let's do that. So, before we resume, does anyone have any questions about the structure of B-trees? We rushed through that quite a lot quite fast. So, about how B-trees are structured. Everyone good with that? Okay. Also, any questions about searching in a B-tree? Or a BST? Go ahead. So, the random question is so the 38 there it can only have two children. Yep. So, one value two children. So, like So, like whatever is So, you have some node in the B-tree and whatever is below it is split into parts by the elements. So, if you have n elements, it splits splits it up into n n + 1 segments.

Okay. All right. You said that the root didn't have to follow the rule. No. Why? Well, you'll see when we do insertion and deletion why that's necessary. But, like essentially like you can consider that it's an invariant and all we have to do is preserve that invariant. So, yeah. The root can has to it has still have less than two it it still has to have the upper bound. But, it it doesn't need to have a lower bound. Okay. Yeah. Mhm. Uh with Well, the whole interval is the cache size. So, something something with that. So, like you probably want to be to be about your cache size. So, you can get the whole block in one go.

I don't I've never implemented a B-tree. So, I I I don't know how it's actually done in practice, but that is the reason. So, I'm assuming it's something to do with the cache line. Mhm. Like the 14, is it a child of both 10 and 17? Well, it's not a child of either. It's a child of this node. So, this node has two elements. So, it's being divided dividing the interval up into three three parts. So, it's a child it's it's in between 10 and 17 is the pointer. So, this this node has has five children. Uh sorry? Uh no, it has three children. So, don't think of every key as a node. Think of like the whole the whole unit as a node.

Okay. So, like it's not a So, in the binary search tree you have one element, but here here every node has multiple elements. That's the point of it. Okay. Anyone else? Okay. Let's start with searching. So, leave this here. Oh. Well. Well, you have the formulas up there. So, that's good. Okay. So, insertion. Let's start with insertion. We already did searching. Okay. So, insertion is you bring in a new key K. And you want to insert it in the tree. So, what's the problem that could happen? You can find the location where you want to insert it just like searching, right? You just go down the tree and find where it should be placed.

But, once you do place it, you'll have a problem. What is the problem? The problem is that one of your nodes will become overflow. And that's not what you like whatever. It'll overflow and that's not what you want. So, you want some you want some way so you can manage this. How do you manage this? So, I have this lovely prop here which I can now hope to demonstrate. That's all. Okay. So, So, here we have B equal to four. So, let's first figure out the number of keys. So, what is the minimum number of keys anyone? For B equal to four. Three. Precisely. So, what is the maximum number of keys? Three 4 into 2 minus 3.

Yeah, correct. 24. But, it's not seven. There's a strictly less than sign somewhere. Yes. And you'll see why it's not seven in a bit. Oh, well. Hypocritical of me. Okay. Um all right. So, as you can see on the three four five six seven. So, some insertion happened. Are the Is the writing clear? Can everyone read the numbers? Good. Okay. 49 looks a little Anyway, essentially these are all sorted. This is the parent node. Doesn't matter what's over here. All that matters is 8 56 and and whatever is in between. Okay. Now, so what we do when we have an overflow node is what something that's called a split operation.

So, split. And there's something which is called a merge which we'll come to later when we're doing deletion. But, now so split is very very intuitively it splits the node into two parts. So, what this does is when you have an overflow node, the number of elements here is what? 2B minus 1 which is just one over the max. So, what you do is you take the middle element and remove it. And now you split the node into two parts. Observe that there are three here and three here which is perfect. And now what you do with the middle node So, now you have actually disrupted the structure of the tree because there was one pointer going in.

There was one child and now you have two children. So, somehow you need to adjust the parent node because the parent node had only one child. Well, at least like the other children are off to the side. But, here it only had only one child and now it's split apart. So, you do something very simple. You just insert this guy in here. And then you say, oh, this points here and this points here. Make sense? I'm going to get rid of these two. Okay. So, and like you can convince yourself that this preserves all the nice properties. So, your children have have been have nicely fallen back into their interval.

Your sequence is completely correct because this was the middle element of this. So, this divides this interval properly. This is also between 8 and 56 because this was in this node. So, all the properties. But, there's one property that is a problem. So, you have just increased the size of the parent node by one. So, now it's possible that the parent node has overflowed. So, what do you do? You split it again. And you split it again. And if you if at any point you're fine, you look you look at the parent node and go, oh, okay, that's fine. That's that's in the range. But, every time it overflows, you can keep going.

And how many times can you do this? You can do this all the way up to the root. And when you reach the root, you either it's fine or the root is too big. It's reached to 2B minus 1. And then you split the root and you get one singleton up there. So, that in answer to your question. That is why you need that property in some sense. Not a very convincing argument, but sort of friendly. But, anyway. So, let's actually do an insertion in this tree we have here. So, we are going to insert 16. Okay. So, 16 comes in here. It's less than 30. Goes to the left. It's between 10 and 17. Goes in the middle.

16. And it's greater than 14. So, we add 16 here. Oh, wait. No. Don't worry. Sorry. One second. No, that's good. Yeah. All right. That seems good. All the properties fine. This is still has two elements which is the maximum, but it's it's good. It doesn't overflow. Okay. Let's insert something else. Let's insert two. So, two goes to 30. Goes down. Goes down. And we have a problem because two has overflowed this node. So, we split. And the way we split is we take the middle element. So, we split the node here. Good. And three goes up to the parent. So, three goes here. And all good? Except for the parent has overflowed.

So, what do we do with the parent? We split the parent again. Let's now split it down the middle. The 10 goes up. So, okay. Let's get rid of this. So, now that it's split the parent, the 10 goes up here. And you're good. It's a bit cluttered, so let me reposition the 17. Okay. Did those two operations make sense? Questions? If you're representing a number as like Yeah, so just pick just pick the First of all, okay. If the way we are doing it, when your node is overflowing, you're inserting only one thing at a time, right? So, if your node is overflowing, it'll be 2t - 1. Which is an odd number always.

There are There might be a case where you get an even number if you do something weird. Maybe you have it like There are like different ways to do B-trees, but if it does, you can probably pick the one like any either of them and then that's a little similar. I'm not sure about that. I'll look into it. But, in general, if you're doing it this way, it's it's always odd. So, you don't have to worry about that. Anything else? If we If we did reach all the way to the root and then went one more up Yeah, so what you would do is would have That would have two children, one one element and two children, which is fine because we didn't put that restriction on the root.

Okay, that's good. How are we doing on time? Okay, we have some time. All right, let's jump into deletion unless anyone else has questions. Uh So, so what Oh, yeah, that's good. Thank you. So, you are going down to the leaves at most like at most of the leaves once and you're going back up once. So, it's like log n plus log n and you're good. Okay. Good. Okay, let's do deletion. Okay. So, deletion is more complicated, so the reason is I'll be clear. So, what the problem with deletion will be remove a node and a node is now underful, so it's it has less than B - 1 uh keys in it suddenly. So, let's turn this around.

There we go. Is that good? Okay, good. So, again, B equal to 4. This node is the problem. Only two things in it. So, what do we do? Okay. So, before we go into that, let's make this assumption that Okay, this So, there are two steps to deletion. The first step is making the deletion at a leaf. How do you do that? The way you make a deletion at a leaf is, let's say, you have have a key, you come down your binary you know B-tree and you're at a node. Now, this node you guys Oh, this key needs to be deleted. But, it's not a leaf. So, what do you do? So, you essentially, what you do is you look at these two subtrees, right?

So, it might have only one subtree. If it's at the end, it'll have only one. Actually, no, that's not Never mind. Ignore that. If it's not a leaf, it has two subtrees. So, either take the rightmost element in this subtree, which is a leaf because you can always keep going down right right right right till you get to a leaf, or the leftmost element in this subtree. So, that is just the next element after this guy. So, you delete this and you bring this up to here. We'll do an example of this and you it'll be clearer. But, you So, you take either the rightmost element in the left subtree or the leftmost element in the right subtree and bring it up here.

So, you sort of like move the deletion to the leaf. And now it's easier to deal with. So, we'll come to that. Also, just uh just a just note that this is not what is done in the rest of the This This algorithm for deletion, I think, is not done in the rest of the notes. This is a different thing which I'll send out a link for later, but I believe it works because I got it from the I'll tell you the reference. Okay. So, once you move to the leaf So, now let's let's look at this. So, this is a node that is underful. And you want to fix it. So, how do you fix it? So, what you do is you look at its siblings.

So, in this case, it has one sibling. It can have up to two siblings. It can have a left or a right. Okay. So, what you do is you look at a sibling and this sibling is actually one over the minimum. And if it's one over the minimum, then you're then you're it's really easy. All you have to do is take the leftmost thing here or if the sibling is on this side, take the rightmost thing here. You and look and look at its parent. So, you bring the parent down Oop. and you move the sibling up. And there we go. So, you basically like tra So, you are rotating the thing into place. So, you move the parent down into the underful node and you replace the parent by the leftmost thing here.

Everyone see why that preserves everything? Okay. And also, okay, yeah, and the And the child is also shifted. Make sure you see that. So, like the child which was in this subtree is now in this subtree. All right. But, then you can have the situation where you don't have a nice sibling to take care of your problems. So, in the like this scenario, the sibling is like barely full. It has three things in it and it can't donate anything to you. So, what do you do in that case? So, then you do something which is a parallel of the split operation. You do a merge. So, what do you have? So, here you have B - 2 and here you have uh B - 1.

And you get 2B - 3. Well, you get another element. You also take the parent. So, how you do the merge? I'm just going to show you the merge first. The way you do it is you move the parent down and you merge these two. Oop. Seems okay? So, you move parent node down, merge these two. And well, now this comes together and this points into the new node. Sort of clear what's going on? Questions? Yes. So, now the parent Well, so you have disc Yeah, exactly. So, you're you have decreased the size of the parent. So, it might not be underful. So, you propagate. Anything else? I saw these all different like in the explanation.

So, there are two cases, right? So, either you have a sibling which has extra nodes to donate to you or you don't. If you don't, then you have to do this. What about the case What about that case? Or is that just like No, that That is moving it down to the leaf. Oh, okay. Once you move the deletion down to the leaf, so here you have have something now. And now you move it all the way back up. Okay. So, there are two cases, so rotation So, let's do an example. That will make it clearer. How are we doing on time? 5 minutes. Sorry. Okay. So, we are going to delete 38. 38 is gone. So, but we want to move it down to the leaf.

So, let's take an element. Let's say we take 41. So, we take 41 and move it up here. 41 is the leftmost thing in the right subtree. So, this vacancy doesn't really affect anything because this node is still has the right number of things because it still got one thing in it, which is good. So, we're fine. This is now 40 Yes, 48. Okay. Let's say we now delete 41. So, 41 is gone. So, now that 41 is gone, what do you replace 40 What do you replace this blank spot with? Either this or this, right? Just doesn't matter. So, let's just do this one for consistency. So, you have 48 here. And now you have a problem because you have a blank box.

Okay. So, can you rotate? Yes, no? No, right? Because sibling has is is barely full. So, what can you do? So, well, you merge. And how do you merge? You move the 48 down and you combine everything. So, you have So, this is this is kind of hard to understand, but this is like a zero element node. The So, you when you merge, you have 32, 48 and nothing. So, it's just 31 48. So, what do you do is So, this seems weird, but this is just another empty node. You just like propagated the emptiness upwards. Now, you take this empty node and you look for its siblings. Again, its sibling is well, it has it's it's almost it's barely full.

So, what do you do again? You bring the 30 down and you merge this. So, let's do that. So, 30 comes down and there we go. All the prob Looks fine? Does that tree look good? Questions about the operation? Yeah, I'm sure it was not clear, but Anything? Makes sense? Okay, let's let's do a deletion where we can actually do a rotation. So, let's go ahead and delete 20. So, you do your searching, go down the tree, you find the 20, and delete it. It's gone now. Okay. So, you're left with just a Actually, never mind. We'll do another one. So, this this do anything. You You lost the 20 and you lost the 24.

It's fine. So, now you do the 24. Now that you got rid of the 24, you have a bank box here now. But, its sibling is not barely full. It has something to donate. So, what do they do? So, anyone, which which which elements are going to rotate? 16 17, right? Okay. Cool. So, 16 goes up. 17 goes down. And you're done. You're consistent again. Okay. So, that was deletion. So, those those are the two cases for deletion. Uh does that make sense? Everyone? Any questions? Okay. So, that's all the topics we were supposed to cover today. Uh any questions about any of the operations, any of the other topics, lecture, anything?