Database Indexes: What do they do? | Systems Design Interview: 0 to 1 with Google Software Engineer

0:00 hey everyone and welcome back this is my second shot at recording for this series uh apologies for the technical difficulties last time my iPad recording was getting turned off more frequently than my ex-girlfriend whenever I tried to make sexual advances uh but the great thing about this series is that I can really crank these out um I'm not going to finish that joke off uh because I have pretty much already made them all before so as you can see I'm making my second one of the day which is great so um you know if you recall from last time we started to get into the contextualization of the database problem how we want to actually organize our data that we can read fast write fast keep it persistent and so today what we're going to do is take a look at the actual internals of a database and how we want to put our data

0:47 on the disk in order to maximize performance all right welcome back everybody I have now gotten the iPad and I'm ready to do some work you may see this is a different day I'm just coming home from the office right now and I have to take a very badly so let's get this is done with relatively quickly so we established basically three facts about the data last video that we're first going to talk about number one is the following that we want the data to be stored persistently number two even more importantly is that we want to be doing this on a hard drive that kind of follows from persistence we know that RAM does not store data between computers shutting off and on so it's more durable on a hard drive the third thing is of course that the hard drive is in a database

1:33 or at least we're running database software on some computer and the actual data itself is being stored at that hard drive so before we go ahead and move further let's go ahead and look at our hard drive in more depth so I'm going to draw another picture of it this time a little bit bigger so hopefully that helps we've got basically some rectangle with a metallic disc and then some moving arm that goes to the proper place on disk in order to read or write data so generally the point of this is that because this little arm has to actually move around the metallic disc the closer that you put data together on disk the faster it is to access so for example you know if I have one piece of data here and the other here that's kind of bad instead it would be better if you know we had our first piece of data here again and the

2:19 second one right next to it we're more likely to get better read speeds okay so now let's actually go ahead and start thinking about you know the data is going to just look like an array on disk right we have all of our little bytes that we can write down and slots and so again you know the closer the data is to one another when we want to access it together the better so that's how I'm going to preface this entire lesson but we'll see this coming to play more and more so let me go ahead and scroll down a little bit so now let's imagine a website right where basically all it does is it stores a bunch of names of people and their shoe sizes and every time you load up the website it'll show you all those people and their shoe sizes so I'm now going to draw up an example database table for

3:04 this website so you can see we're going to have a few rows of people and their respective shoe size so the first person is going to be me Jordan uh and you know my shoe size is 18 because you know big shoes means quite a little bit about what else is going on in your body and we know that uh unpacking number two is going to be Donald for Trump he has small hands so he probably has small shoes as well we're gonna go ahead and throw him a seven and then we've got Shaq for Shaquille O'Neal that dude is massive probably has like a size 24. I can concede to Shaq so what is my point about this table well the first thing is let's say I want to find rows where name is Jordan

3:50 this is something you can do in most databases right in order for me to go ahead and do that I have to check each row individually I have to go here then row number two then row number three and what that means when you have to do proportional work to the number of rows in the actual table itself is that this is going to be an O of n time complexity right if there are n rows we have to do n amounts of work basically or work proportional to the N rows in order to actually find the row that we care about so in addition to that let's say I wanted to actually edit a size turns out Shaq is bigger than we thought his shoe size is actually going to be 26. so

4:35 again if we're going to write first what that means is that we have to actually find the proper row right we're going all the way through these rows again and then we're going and changing our existing Row from a 24 to a 26. so that means o of n time complexity for both reads and writes okay so let me quickly erase this 26 and throw back our 24 because what I'm now going to show is a slightly better design of a database table that would basically allow us to improve at least our right complexity so let's say this time instead of editing Shack I want to edit Donald so we knew normally that in order to make that edit we would actually have to find

5:21 the road Donald in the table and edit it but now what I'm proposing is instead of actually doing any physical edits what we do instead sorry I don't know how to use this iPad yet is we would go ahead and add a new row to the table where I would now just say Donald with the new shoe size let's say his foot is actually even smaller than we realized now it's a six and then every time we search for a row now we actually just go ahead and search from the bottom of the table up so in the case of Donald I would say oh it's got to be this row here not this one because this Donald is actually lower to the bottom and so now because we know that we're always going to be writing in the same place every time which is the bottom of the table we can basically keep a pointer to that

6:06 address and disk and that makes right times o of one uh however this does come on the trade-off of a worse read time the reason for that is that even though reads are still o of n it means that uh they're going to actually be more rows in the table overall so that n is going to be bigger obviously this isn't going to be acceptable as o of n reads are basically slower than Joe Biden trying to read from a teleprompter and he is a boomer so it's not ideal but the truth of the matter is actually in a lot of these problems or a lot of these big websites We Care a lot more about read speeds than write speeds and at least as far as I've just showed you those read speeds were pretty unacceptable o within is not good enough right we're going to cross that out just go ahead and say it right

6:53 there the reason o of n isn't good enough is because when we have hundreds of thousands or even millions or possibly more rows in our database we don't want to have to literally Loop through every single one in order to find the proper row that we want we need to make things faster than that think about Facebook for example all right this is the example I keep using if I have to go through every single Post in the database in order to go ahead and load our news feed that is going to be impractical and it simply doesn't make sense we need a better way of actually organizing our data and this is where the need for indexes come in so before I actually explain what an index is let's think about some things that an index or just a better way of

7:40 reading from databases in general could help us do well for one we care about finding rows with specific key values right so in the last example uh basically that was finding a row by a name sorry I can't write terrible handwriting in the last example it was finding a specific row with a name that matched the parameter that I provided but in another example you know maybe it could be names maybe we care about finding a row with a specific shoe size that could help as well and we want to be able to do this faster than just by linearly scanning through that whole table another possibility is performing something known as a range query so we gave some names before an example

8:27 of a range query would be show rows with names between A and B right so if they're you know Abraham Lincoln in there you know Alex Adams anyone like that you want to go ahead and return all those rows and this is a very common query if you think about it in something like a social media site maybe we want all posts from you know one hour ago until now right so it's basically any sort of range query where we have these kind of two delimiting parameters and we ultimately want to get every single thing in between so these are very common cases where we care about

9:12 optimizing them even if it means potentially taking a penalty in our write speeds right because at the end of the day if we're doing a lot more reading than writing something in the database that can help us improve our read speeds even if it makes writing more expensive is still going to be a big win in the average case for the user experience and so ultimately what we want is going to be called a database index a database index like I've started to hint at basically does the following basically does The Following the read speeds go up and the write speeds go down and this is for a specific key right so we can have a database index on

9:58 one field for example like names in that table but you know when you mention an index typically it is on one field at a time you can create multiple indexes where there is an index on both the name and the shoe size you could even potentially have an index on both the name and the shoe size but we'll kind of explain what all of that is in the next video where I am going to show you one example of how to implement an index and kind of the pitfalls and the benefits of that specific implementation which is going to be a hash index all right everybody thanks again for all the support on the first video of this series again I'm sorry about the flickering but uh hopefully we can get that fixed up this time around I am now going to go ahead and take a fat crap and I will see you in the next one