Hey everyone, welcome back to part two of topic seven in our database class. And in this video, I'm going to provide an intuitive overview of database indexes. So, what we will do next is I'll walk through a conceptual example of an index. And we'll look at the standard approach, which is the non index approach. And then we will look at what happens if we implement a simple index, and we'll see what kind of performance increases we can get out of that. Okay, so let's begin then by considering this table of data. Now this table of data might be say it's a table of employees or something, and you can see we have about 22 of them. And they're not in any particular order. Okay, it's just, I don't know, maybe we just put them in there in the same order that we hired them. Right, so we, they're just in there by row position. So this is row number one in our table, row number two, row number three, row number four, etc. Right, now, what's the magic that we had the task of trying to locate any randomly chosen person's last name in this table. So the question then is, how would we do that? What sort of approach would we take? Knowing that these are in some random order, you know, what we would have to do. Let's take a name, let's say that we want to find, I don't know, we'll want to find about winter. So this is our person that we want to find. Now we don't know where winter is located in this table. So if we want to find what row winter is in, our strategy basically has to be to just look through the rows. Right, so it would be like, okay. Is this winter? Nope. Is this winter? Nope. Is this winter? Nope. Is this winter? Nope. Nope. Nope. Nope. Nope. Nope. Nope. Nope. Nope. Nope. Nope. Nope. Until 15 search operations later. I think one per row. This was one search operation, another one, third one, so on. We do 15 of those. And finally, oh, yes, it's winter. Hurrah. You found it we were after. Okay. So in this case, our search time to find winter. It's 15. And so we had to search through with a do 15 different search operations to find winter. Yeah. Now let's imagine that we wanted to search for some other randomly chosen name. Maybe I don't know. Voo. Okay. So we want to search for voo. And we repeat this process. We say, is this voo? Nope. Is this voo? Nope. Is this voo? Yes. So in this case, we were able to find what we were looking for after four search operation. Now, but these concepts in mind, let's take a look at some of these questions over here on the left side of the slide. So with this notion of just having to look through the rows to find what we want. If we did this over and over and over again, we just picked a name at random and searched for it. What would the average search time be? Well, the average search time, if we just did this process over and over and over, we just picked a name at random and search for it, would be the number of rows in the table over two. Right. Because on average, that's what it will take to find what we want. Sometimes we'll find what we want in the very first place. So if I randomly chose the name Schluter, I would find that the first time that I look in the table. If I randomly chose the name Misha, I would have to do two searches to find it three to find Sally on and so on. If I was very unlucky and I ran them, we chose Israel here as my name. I would have to look through the entire table before finding what I want. So you can imagine if we just repeat this over and over and over again, this one takes 10, this one takes 13, this one takes three. If we just add all those together and take the average, it will be the number of rows over two. That is put differently. On average, if we chose the name at random, we would have to look through half of the table to find that name. Right. So on average, I would have to look through 11 rows to find any randomly chosen name. And hopefully that makes sense, right, because 11 of those I would find during that search of the first 11 and the other 11 would be, I wouldn't find them yet. What this means then, if we want to write this down is that we can imagine that the search time is n over two, where n is the number of rows. So this is our average search time, right, this one here, do do do do do do that's our average search time. And over two. So with that in mind that what is the maximum search time. n, where n is the number of rows, because sometimes just by random chance, we'll be wanting to find this guy. So we'll have to look through the whole table, we'll look through the entire thing and we don't find them until the very, very last place. So in that case, it's n. So our maximum is n and our average is n over two. So let's take a look then at this table of data now over here on the right side. Now in this table of data. You can see we have the same information as before, right, the row position, which is the location of that employee in the table. And then we have the last names, but what we've done here is one additional thing. So we can see these last names are alphabetically ordered. So we all know the rules of how to alphabetize something. And that's what's going on here, right, they're in alphabetical order. Now with this one change. It's one single change that is there's an organizational structure on these data now that that they're in alphabetical order. And I will propose to you that I can find what I want almost instantly with very, very, very few search operation. So let's ponder how we might achieve that. Now if we have this alphabetically ordered table of names. And again, we have this task of wanting to find any random we chose a name as quickly as possible. That is with the fewest search operations possible. What is a reasonable strategy? Let me put it differently. Where should I look first? We would look in the middle rather than starting at the top and saying, Is this the name I'm looking for? Is this the name I'm looking for? Is this the name I'm looking for and so on? If I know that these names are all alphabetically ordered, the best place for me to look for any randomly chosen name is the middle. And in this case, we have 22 rows. So we don't have an exact middle. We could just do plus one or minus one from the middle. So let's say we pick this looks like it's approximately in the middle to me. So let's say that we pick this one. Okay. And here is where the power of these indexes comes in for the strategy of alphabetizing things. So let's say that I again am looking for the name winter. All right. So I'll highlight that. That was the name that we chose from previous one. And we saw previously that we had to do 15 search operations to find winter. Now with this alphabetical alphabetized list of data, we have just any random we chose a name. We'll start by looking in the middle. So let's say that we look at Misha. Now we look at this. We say, is this winter? And the answer is no. But this is the key point. Because the answer is no, I now can eliminate all of these possibilities. So I know actually I can pull the way down to Misha. So I know that the answer now, the location of the of the name I'm looking for is somewhere in this remaining set. So these no longer exist. Right. Because if the one that was looking for is if that's not it, it must be later in the table, right. Because it's alphabetized. So the answer that I'm searching for must be among these remaining sets. And you can see here we have what one two three four five six seven eight nine we've got 10 of them. So knowing now, this is one search operation. So with one search operation, I've been able to eliminate half of the possibilities of where our randomly chosen name is located. So after that one search operation, where do I look next? So we split them in half again. And in this case, it looks like we have about to 10 remaining. So again, we can't split them exactly in half can't look in row 5.5 or whatever that would be. So let's say that I don't know we just looks like it's approximately halfway. So we'll look here. And we'll say okay, is that winter? And of course the answer is no. So again, knowing that that's not what we're looking for. Well, we can now eliminate all of these possibilities because we know that the answer must still be below there somewhere. So with two search operations. I'm down to four possibilities. And I've eliminated 18 of the 22 possibilities just by looking in two places. So again, we would say where do we look next? I don't probably in the middle of what remains and we don't really have a middle of these four. So maybe I just pick this one. That's been my pattern. So in this case, I found what I want after three search operations. So that's pretty efficient. Otherwise, based on its row position, currently this one is in the 21st row in this table. So we have to do 21, but instead I could find it with three. So let's randomly pick another name. We'll walk through this one a little bit faster. So I don't know. Maybe we pick who. I'm going to find who will be our target this time. Hey, so what where do we begin? Well, just as before we look in the middle. We said, me sure was the middle. So we know that's not the one that we're looking for. So now we can eliminate all of these. We know the answer must be above there because they are alphabetically word. So what do I have here 12345678910? I've got 11. So that means I do have a middle location this time. I can look and row number six. Next 123456. So next I would look here. And I would say, is this the one I'm looking for? No, I'm looking for who and that one is gani. So we can eliminate. After two search operations. All of those. So I'm down to five. Where do I look next in the middle? So I search here. I say, is that the one I'm looking for? Nope. So I can eliminate all of these rows and now I'm down to two. Okay, so maybe I find it on my next look. So in that case, to before, I did four search operations, but hey, it's much better than scanning through the entire table. So what we're this strategy that we're looking at right now is called a binary search. And it's extraordinarily efficient for finding any randomly chosen thing. If we have that simple knowledge that organizational structure that the data through which we're looking are in some kind of order. In this case, it's an alphabetical order, but if we were looking for some specific number, it could be numerically ordered. If we were looking for dates, it could be sorted by date and so on. So as long as they're in order, we can find what we want. So just like the index in the back of a textbook. If the only way that it makes sense and that it speeds up your search is because it's in order, right? It's alphabetized and you know the rules of alphabetization. So you could easily skip to the section of the index that contains the information you want. And the same thing is happening here. However, we still have these. Row positions, right? So this one is like 14. This one is nine. This one is 11. And these are just like the page numbers in the index in a textbook. They tell me where to look in the underlying table. For the actual row of data. So in this case, this structure that we have here. Could be serving as an index on the last name column for our original data, which we're here. Okay, so if I can quickly locate what I want, let's say I'm looking for the last name who I find that very quickly. Maybe I have the capability in my app or something to search by the employees last name. So I can index that column. I can quickly locate any employee. And we can see that this tells me that who is in row 21 in the table. From which the index was built. Just like we could say the information about hydrogen is on page 720 in the textbook. Same thing, right? It's a pointer back to the original data. As we can see here back here on our original data table. Here's row 21, right? That's who. So if we had some additional employee information, which we almost certainly would, we might have like first name, email address, phone number, etc. We could then find any of that information very quickly as well. So by building an index on the last name, we can quickly, we can use this binary search strategy to quickly locate any randomly chosen employee by last name. And once we have located them, we have the knowledge of where that row is in the underlying table. So I can pick any name here. I can find it very quickly because they're alphabetical order. And once I know it's row location, I can get that row just by looking, you know, exactly where I need to look in the actual underlying table from which the index was built. So our first example, if I was looking for winter, I can find it in three search operations. If I have an index on the last name, and it tells me to just look right here and row 15 for the row, next will row of data. So this is pretty cool, but we have a little more to get through before we can move on. And that is, we want to compare this general binary search strategy that we illustrated here with our previous sort of naive approach, where we just scan through the table. So let's ask ourselves the same question that we asked before. If we take this binary search approach, what do you think the average search time will be, if we just do this over and over and over again with random we chose in names. So it's a little mathematical and we won't go into the math, but suffice it to say it's been demonstrated that the answer is log base two of n. So it's a binary search and it's the base of two for. So that's our average search time right this is the average. Now, what do you think the maximum search time is it's just log base two of n plus one so at most, we could have a billion rows of data in this table right on average will find something in log two of n. At most, it'll be log two of n plus one so we just have to do one more search operation to find what we want. And that is amazing and we may not appreciate it because maybe some of us have forgotten about some of these logarithmic exponential types of things. I think a very useful way of illustrating this would be just to demonstrate it so i'm going to load up Excel here and we will see comparatively speaking how much better this search strategy is than the naive approach all right. So here we have Excel and this will be i'll just put in some things here. Let's do I don't know number of rows was the number of rows in our table number of rows of data. And then we'll do say the average search time. For the naive approach. Sorry, I can't easily put in the cool tool dots over the eye there for how naive is felt. And then we'll compare that to the average search time. And this case we're using number of search operations as our time metric search using the binary approach. All right. So we know what these are we have our formulas this one is let's start with our example of 22 rows. And we know this one is n over two. This is our average search time would be to look in 11 rows. And here our average search time. We will be a log base two of the number of rows, so number of rows base two. So 4.45 now to clean this up a little bit. Let me just step now will give these some decimal points and I don't know center it. So with this simple little tool in place now. We can play around and really appreciate just how powerful this binary search is. So if we have a relatively small number of rows like 22 rows. We're not going to get to much of a gain right because remember computers are very, very fast so hey. I want to find do 11 search operations. I'm not going to notice that as a human versus 4.5. I do note this is already more than twice as efficient. So let's scale this up a little bit. What if we had 100 rows. 100 rows of data. I have to do 50 search operations with an naive approach, but only 6.6 with the binary. So that's amazing. What if we increase that by a factor of 10. So let's say that we have we'll just increase it by one order of magnitude. So. There we go. And then look at that. We have 10 times as much data as we did before. Okay. With the average search we have to do the naive search we have to do 10 times as much searching as we did before. But with the binary search we just go from 6.6 searches on average to 10. So less than 4 additional searches to search through 10 times as much data. So that's pretty impressive. Let's increase this by another order of magnitude. Say we have 10,000 rows of data. As you can see with our naive search we have to do 5,000 searches. But with our binary search we've gone from 10 to 13.3. Okay. So we've added 9,000 new rows of data to this tape. And we can find any of them randomly chosen with just an additional 3.3 search operation. That's amazing. So let's scale it up some more. What if it's 100,000 rows? Again, we added just an additional 3.3 search operations. Even though we now have 90,000 additional rows of data. Let's scale it up again. There's a million rows. There's 10 million rows. There's 100 million rows. Let's go crazy. Let's say we have a record for every human being on earth. Which would be 7.9 billion people. Right. So if we're looking through any randomly chosen person on earth. Look at that. Here we have to do almost 4 billion searches. But it's fewer than 33 on average for the binary search. So think about that with just 33 search operations using this binary approach. You could find any randomly chosen human. From the entire planet, almost 8 billion people. So I'm hoping how you're starting to see just how this vastly increases search performance. Right. I can find any randomly chosen human being by looking in 33 places in a table that contains nearly 8 billion rows. But if I wanted to do this, do the same thing with my naive search. I would have to scan through on average almost 4 billion of those rows before finding my person of interest. So this is pretty amazing stuff. Again, it really shows you that remember computers are fast. So 33 search operations is almost instantaneous. But 4 billion is still noticeable. Right. That's going to take a long time to scan through there. Just think about how this scales up and you can see how it's so key to finding what you want in the vast oceans of data that we have now. So this is indexing. And it reveals very plainly and obviously to us. Just how what sort of gains we get by using this over the naive search approach. So this is hopefully starting to give you some ideas about why indexing is useful. Okay. Again, it's not going to matter much if you have 22 rows of data like we see here, but if you have 22 billion rows of data you're going to get just vast improvements in performance. One other thing that I wanted to mention. Is that in this particular case, what we're seeing is all of the names are unique. How we know that oftentimes there can be repeated values in a table. Like maybe I have a reasonably large company. And I find that I have some people that have the same last name. So what effect does indexing have in that situation or that scenario. Well, I think you'll find that it works almost exactly as efficiently. So let's say, for example, that instead of these employees. So we'll pick a very common last name like fam and instead of these employees here. Let's say that we had some additional. Fams out here. So the question then is these are separate employees and I'm going to have to have some way of maybe identifying the set. So let's say that I want to identify the set of fams like all of the possible ones. How does this work with our binary search? Well, let's find out again we'll start by looking in the middle. We'll say is this fam. Nope. That's me sure. So we can then immediately eliminate. That row and everything above. And we kind of look in the middle of what remain ground row five somewhere look here. We'll say is this nope. So again, after two search operations, we've able to eliminate all of these options. We're down to a few possibilities remaining. And then we look in the middle again. And in this case, the middle will be right here. We'll say is this fam yes. So if we want to find the complete set. Well, all I have to do from this point is look up and look down. So I will start scanning up and I would say is this fam yes is this fam no. So I've identified these two rows already. And then from that center location again, I scanned down and I say is this fam yes is this fam no. So you can see very quickly, I'm able to locate my entire set of them. But just find those upper and lower boundaries. As soon as I found one, I just scan up and down from that location and find what I want. And in each case, I'll get the row pointers. So row 20 row three and row one. Now again, we can contrast this task of searching for a situation where we have multiple duplicate rows. We can compare that out here to the naive task and see how many search operations will need. Right. So we would have to scan through literally the entire table. Because this very last one might be fam and we won't know until we've searched through the entire table. If we have found all of them. That makes sense right if I know that there are duplicate values and I have no index in place, I literally have to scan through the entire table. Every time in order to try to find all of them, because the possibility exists that the very last row might be one of the records I'm looking for. So in that scenario, if it's not if these values in this case last name is not unique. And I'm going to try to find a set of them in that case the performance, the average search time is always going to be n right every single row. And I'm going to have to see the maximum because I have to look at every row in order to be sure that I've correctly answered the question. And as we saw a moment ago, that's not necessary when we have an index in place.