Hey, everyone, welcome back. In this video, part four of topic seven in our database class, I'm going to discuss B-tree indexes. Let's get started. We've been thinking about a database table, and different tables, and they have columns that represent their attributes, their properties, or so on. But we've been thinking of these as these kind of two-dimensional structures like a spreadsheet where you have columns, and you have rows, columns or the attributes. Each row represents an instance of that entity, whatever it may be. An employee, customer, product, et cetera, et cetera. So we've been thinking of tables like this. However, and most modern enterprises of level databases, tables are not actually stored this way. Instead, they are stored in the form of a B-tree. And that's what we're going to learn about next. We'll see by the end of our time together today, that there's a very good reason that we use these things. So what we're talking about here is the actual type of data structure that is used to implement indexes. And by far, the most common of these data structures is called a B-tree. And some people, I know it's not technically the truth, but if it helps you, you can think of this as a balanced tree. It's also, some people will call it like a B-tree, because it has that little dash there. And there's also another version of this called a B-plus tree. So whatever, we're just going to talk about the general form and understand that there are several versions of this data structure that vary in some ways. But the general idea here is that we're going to have some sort of data structure that we're going to implement that will actually be an index for us. And it's going to use pointers and nodes in order to allow us to quickly locate whatever data we're interested in. Now, there are different layers of nodes that exist in these trees. So we start at the top, and the top is the root node. And what's interesting is, I call it a tree, but it's like an inverted tree. It's sort of like if you took a tree and flipped it upside down. At the top, you're going to have the root node. And then in the middle, you're going to have one or more intermediate nodes, layers in there. And at the very bottom, you're going to have leaf nodes. And this is where the data are actually stored, at the leaf node level. Now, as you can see, as we move from root to leaf, we're becoming more and more granular. That is finer green. There's more and more detail. As we move in the opposite direction, from leaf in the direction of the root of the tree, we're becoming less and less granular. That is where these higher levels we're encompassing a greater and greater proportion of the data. So ultimately, again, our data values are going to be stored here at the leaf nodes. And there'll be some levels above that, like one or more layers of intermediate nodes. And they are going to fold or refer to several leaf nodes. And then we may have another intermediate layer on top of that that refers to several groups of intermediate nodes. And ultimately, we end up at the root node, which typically is just one node. So how things are actually happening inside the database when you submit a query then, is that you type up your SQL Select query. And if that query, in some way, involves an index, or I should put that differently, I should say, if the database looks at your query and says, you know what, I can solve this query most efficiently by relying on an index, then what it's going to do is it will use that index or several indexes, as the case may be, to try to answer your query as quickly as possible. And it begins by looking at the root node. So it's going to look at the root node of this tree index. And that will tell it where to look next. So it looks at the root node first. And as soon as it looks there, it knows where to look next. So you'll look next at some group of intermediate nodes. And after looking there, you'll know exactly where to look next. And eventually, we'll get down to a leaf node. And the previous layer above would have told us precisely where to look so we can quickly locate the information that we want. And again, remember the actual data are stored at the leaf level. So that is how these databases use the B3 indexes. And that doesn't make much sense when you see it in text. But it does make sense when you see it in the form of a picture. So let's look at a picture. Now what we have here is a B3 index. And it's showing much of the same information that we worked on earlier. So remember we had these data here. We had 22 different, I don't know, same employees, our last names, and the row positions in the underlying table. In this case, we have most of them here. I think I only put 16 of them in here, or something like that to try to save a little space and improve clarity. But it's the same problem, essentially. All right, so let's point out a few salient features of this. And then we'll look at it the way that the DBMS does when it's trying to solve a query. So here's our root node, right here. That the top of the tree. And that's followed by, in this case, a layer of intermediate nodes. To remember that there can be several layers of intermediate nodes. In this case, we don't have very many individual values. So we just have one layer of intermediate nodes. And this worked well for illustration purposes. And then at the bottom of the tree, we have the leaf nodes. And these leaf nodes down here are where the actual data are stored. So again, here we can see that, so we've got these last names in here, because we had built our index. If you recall, our index was built on these last names. So index is over here on the left. And that's what we've got this here. Here's the data. Alpha betized. Right. Alpha beticle order. And then we have our row positions, which are the pointers. Remember these tell us where to look in the underlying table. So if I find, I don't know, fam, this tells us you've got to look in row number 20 of the underlying table, which is over here. So then I can get here. And this is the actual row of data. There might be additional information in here, first name, email address, et cetera. So as soon as I'm able to find that row of data, I have basically instantaneous access to any other columns that are a part of this underlying table. So I can search, in this case, very quickly, by last name. And once I've found the last name or names that I'm looking for, I can quickly locate their rows in the underlying table and can find the additional information that's there. Just if you use the index at the back of a textbook, it'll tell you, look on page 247 for whatever. And you go there, and then you can consume all of the additional information that's there. So with that in mind, let's see how this kind of works. And I think what you'll discover is it's basically the same idea as the binary search, sort of divide and conquer approach that we talked about last time. So what we have then is, let's imagine we have a query, and we're trying to find some last name as quickly as possible. Over the database, we're going to start at the root level. We start here. And you can see that in this case, note that these are names, right? So it's text, and that's why we have text in the root nodes. But if these were numbers, then the root nodes and the intermediate nodes would have numbers in them. So in this case, it's just that the actual data on which the index is built are text. So this is what we're using as text. Now, what happens here, how these nodes work, is that this is just a simple test. And that test is, is the value I'm looking for less than this. So whenever I'm looking at one of these nodes, I just look at the box, and this one has a letter S in it. And I say, is the value I'm looking for less than this? If the answer is yes, then I go this way. The answer is no, then I go this way. So let's say as an example here, pick, I don't know, one of these names is our target, just so that we have an illustration to work with. So our target will be, I don't know, I guess it doesn't really matter. Let's pick this one. Fun, fun, okay. This will be our target, right? Now we don't know in advance where this is located. All we know is this is what the person searched for, okay? So somebody typed in, I'm gonna find this employee with this last name of fun. So again, the question that's asked when we're at any of these nodes is simply, is the name I'm looking for less than that? And it could be a number, it could be text, it could be a date, anything, right? So let's see how this works then. Come in, our name is fun. That's what our user has typed in that they're searching for, last name. We asked ourselves a question is fun. In this case, alphabetically, less than the letter S. The answer is yes. So we go this way, okay? Now we then start over here on the left and we say, is fun, alphabetically less than the letter F? And then the answer is no, it's not, right? Because F by itself is alphabetically smaller than fun, which has four characters in it, okay? So we then look at the next node. And this says, okay, is fun, alphabetically less than the letter G. And the answer is yes. So we follow this path then. If it had been, if we had been looking for, I don't know, Bina, right? We would have arrived on this node and said, is Bina less than F? Yes, so we would have followed this path. Instead, we move to the next possibility at this node, which is, is the name we're looking for less than G. In this case, we're looking for fun. So the answer is yes, it is less than G. So we follow this path. If it were a different name, let's say it were, I don't know, Misha, then the answer here would be no. And since we have no other boxes to look in at this node, we would know we have to follow this path to the right. Okay. But instead, we follow this one and we arrive first at Flores. And we would say, is this fun? Nope. So then we move to the next one. Is this fun? Yes. Or if we have more than just a couple of nodes out here, we could do a binary search, right? I could start in the middle value and then split and split. But in this case, I only have two or three in each node, each leaf level node. So it's not a big deal. I just say, is this the one I'm looking for? Nope. How about this one? Sure. So I found what I was looking for. Now again, last time we talked about this idea of search time in the form of number of search operations. That is, how many search operations do I need to perform to find some randomly chosen item in this case, a last name? So let's apply that concept to this lovely B-tree index that we have here. So we started the root node and we're going to say, hey, is fun less than S, right? The answer is yes. So that's one search operation and we go over here. Now look what's happened. This is how we can draw a connection between this and everything we've done before. I've done one search operation and I've eliminated all of this. Right? After one search operation, I know the answer is over here somewhere on this left side of the tree. I see how this is very, very conceptually similar to the binary search that we were talking about earlier. Right? So let's continue with our little example. So that's one search operation complete. Now we arrive here and we say, OK, is the name we're looking for fun? Is that less than the letter F? No. That's two search operations complete. I'm able to eliminate this. So now I know the answer must be here. So we then ask a third question is what we're looking for less than G. Yes, that's our third operation. And so now we know that we have to follow this path. And by extension, we know that our answer is not in here. So after three search operations, we're down to these two possibilities. And then in this case, I might look here and say, is this what I'm looking for? No. So that's four. Is this what I'm looking for? Yes, five. So I found what I was looking for after five little search operations there. All right, let's do another example. So in this case, so let's say that we want to find, I don't know, of the name Salihian. All right. So our new target will be this name here. So again, we start at the root node. Is Salihian less than alphabetically less than the letter S? The answer is no. So we go over in this direction. Again, that means we've eliminated all of this already. We then ask another question is Salihian alphabetically less than Sp. So this is an example where we have not just a single letter that's being used, but two letters, right? So we have lots of S names, as you can see, lots of S names here. So we're not just splitting on that. We're splitting on Sp this time. So is Salihian less than this? Yes. So I go over here and I arrive at my very, let me eliminate some things. By doing that, I've eliminated all these. And then we look in that first location. Is this what I'm looking for? Yes. So three search operations to find what I want. And I think if you take a look at this and you pick any random name and you follow this set of steps, you'll see that it is extremely efficient. You can find whatever you want, just a couple of search operations. Just like with that binary search, it's a slightly, very slightly different in the sense that we can have, we're not always just splitting things into twos. So sometimes I split things into threes and so on, like this level, a couple of different paths I can take. So I can take this path or this path, this path. But the basic idea is to, with these threes, is that we want to have leaf nodes that are of approximately the same size. There's approximately the same number of data items in each one. In this case, you see we have either two or three in every one of them. So it's pretty balanced. Hence they common, although some would say incorrect use of balanced tree for this. So and you can just scale that up. So again, each of these has an approximately equal number of data values at the leaf node level. If we go up another level to the intermediate nodes, we would say these two groups of data values as organized into intermediate nodes are of approximately the same size. In this case, we have eight data items on each side. So that's pretty balanced. And if we had additional layers of intermediate nodes and so on, we could continue seeing that. But these are some basic properties of these threes. So this is how Beatrice implemented and it has some other really nice advantages. It's easy to add and remove things without having to do too much additional work. Okay, so I spoke last time about if you recall the necessity of having to keep the index up to date. All right, so if I have the example I used last time was I'm going to hire some new employee. So we hire a new employee. We put them in the data table here. Row number 23. Dan. And then I have to update my index as well. So remember the index is alphabetically ordered. So I need to find out where does Dan go. Put a row in sort of row in here conceptually in sort of row. Nice. But what we can do with our Beatrice is we can use exactly the same strategy to figure out very quickly where the new row needs to be inserted. So in this case, what I might do is I would say, okay, I want to insert Dan into here. So is Dan less than this? Yep. Is Dan less than that? Yep. So I know Dan has to be inserted on this side somewhere. And then I potentially could use the binary search, whatever, find it. And I know that Dan has to go in here. But at this point, I might recognize that, hey, my tree is starting to become a little unbalanced. All right. So if I added a new one out here, remember I'm inserting a new one here. So that alphabetically ordered. And my old one has to be shifted down. So let's say that we do that. And this one would be Dozhi, which was previously located above Dozhi. And then my new record, which was Dan, would go here where the other one previously was. Dan. But you can see this kind of makes my tree unbalanced. So at some point, I have to decide if I want to keep it like this or if I want to rebuild it a little bit. And if I wanted to rebalance the tree after inserting this new record, all I would have to do is just move this to the next node over. We just go there. So then we'd have a balanced tree again with a approximately equal number of rows on each side. So this is how we enter a new piece of information into the index. So we don't have to shift all of the rows down as we would if we're using like a table. All right. So remember back here when we had our table, thinking that this way, like if I want to insert Dan, think of it like an Excel spreadsheet. All right. If I want to put Dan in here, then all of these other rows, at this point on have to be shifted down one. Okay. So that's a lot of tasks. I have to do a shift for each one of them. It's a lot of work, but if I compare that to what's going on over here, you can see it's a little more efficient to do it in a tree form. I think I can just add a new record in there and then maybe I have to rebalance my tree by moving one additional thing. So yeah, I do two quick changes rather than maybe dozens of changes. And the same thing happens if we want to delete a record. Okay. So let's say we have this lovely balanced tree and that we decide that we want to delete something out of it. So how does that work? Let's say we want to delete, I don't know, what's to delete, Flora's. So what we would do is, again, we would start here, we would say, is Flora's less than this? Yep. Is Flora's less than that? Nope. Is Flora's less than this? Yep. So I know it's down this path. I say here's Flora's. All right. So I've got to delete Flora's out of there. Flora's is gone, which basically would yield just one node here. And we would say, well, our tree is now unbalanced again. So we could again correct that if we chose to buy, like, just moving that one over to this node. And then of course, we would have to update our intermediate node as well. Change that so that we direct people down the right path. Or actually in this case, yeah, in this case, we would have to do that. So we would have to change that. I don't know. The DO, I guess. That way we could send anyone looking for doe sheet down this middle path rather than to the left. So again, pretty easy to delete things out of here. We just have to make a couple little tinkering changes to it, rather than doing a major shift of all these different rows. So compare it in your minds to something like an Excel spreadsheet. Right. So yeah, a bunch of rows in your spreadsheet and you delete one of them. So all of the rows below that have to shift up. And they have to shift toward the top in order for that row to be deleted. But in a tree, we don't have to do that. We just have to make a couple little minor tinkers with it here or there. So it's faster to update. Now these of course are extremely popular because of all these great features that they have. Right. They're easy to add, edit, delete. So you can maintain the index with as little computational overhead as possible. And there is still some work as we saw, but it's comparatively minimal, which is what we want. And so these enterprise level databases use these all the time. Let's see, what else did I want to tell you about this? So yeah, this is a simple version of this, a classic B tree. But there are some modified versions of this that can be useful. And it's hard to illustrate the usefulness of the modifications here. But it's basically in situations where we would have, like maybe we're looking for multiple rows. Right. So let's say, for example, that's what we're looking for. Anyone whose name starts with V or later. So you can imagine I'm doing some search for anybody whose name is like greater than or equal to V. So we can see out here visually that would include this row. And these three. Right. So these are all to draw this. Kind of let's say that our, how these SQL queries are, we can use like a right. Remember that that has been a while, but we would type in something where it's aware. I don't last named like something like this wild card search. I'm sorry, I messed that up. Let's do it this way. Greater than or equal to the, the path. So in this case, anybody whose name starts with V or greater should be included as part of the results. So looking out here, we know that we, we can visually see that we have these four rows. Is our, but it's a little inefficient or it's comparatively inefficient because what would happen is I'd have to be from the database. I'd be looking over here. I would say, okay, is this less than V? No. I look over here. I would say is this less than V? Or I should say is V less than this? No. V less than this. Yes. So I go down this middle path. And I would find one of my answers, but then I would have to go back up and follow this other path over here. Right. And continue looking for answers here, here and here. So I've got to do this kind of back tracing up to the intermediate level, and then go back down to the leaf level. With this sort of a design, if I'm looking for something like this, right? So a modified version of this, and this is the type that SQL server uses, is there'll be a pointer at the last item in the leaf node to the first item in the next leaf node. Okay. So if it's alphabetically ordered like this, on what I would do is I would, let me leave that arrow in there, is I would find the first item in my search results, VU. Right. And then it would tell me, hey, follow, just look right here for the next one. And I would, then I could say, okay, is this a record that I want? Yes, is this a record that I want? Yes, is this a record that I want? Yes. So I can quickly assemble the list of results to a query that looks like that, without having to backtrack through the tree. Okay. So I don't have to, I never have to go back up to the intermediate level, and then follow another path over here. So it just saves me a couple of additional steps. It's a little more computational efficient. And you can then kind of imagine how we would have these pointers throughout the tree. Right. At the leaf node level. So if we're ever trying to just get a series of values, we never have to travel back up the tree to the intermediate level. And we can always just go to the next one over. And of course, it works in the other direction as well. Right. So if we need to, we can search in the opposite direction, kind of a clever. So if you find this kind of stuff interesting, then you can appreciate what computer scientists do, because that's a area of research that tries to figure these things out. Like how can I quickly and efficiently organize information where I can find it, update it, search it, all this kind of stuff.