Name: DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!
Uploaded: 2025-02-10T03:54:47.000Z
Duration: 14 min 16 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Adverbs of degree

Today we're going to do a really quick high-level overview on database indexing.

And so this is going to include talking about what is an index?

Adverbs of manner

What problem does an index actually solve?

What are the most common indexes and when should you use them?

Now as I said it will be high-level and for much more detail please head over to the Hello Interview website and we have a deep dive on database indexing.

I'll be sure to link that in the description.

All right, so before we start talking about indexing, let's understand the problem that indexing solves.

So data is arranged in a database in pages.

And so when you want to find a particular item in your database and you're not using indexing, what happens is that we pull a page into RAM, into memory, we scan through all roughly 100 rows or items looking for the item that we're after, and if we don't find it we put that page back, pull in the next one, put that one back, pull in the next one until we eventually find it.

And so as you're starting to realize this is a slow process.

To illustrate this, if we had 100 million users in our user table, and each page as I said has maybe about 100 rows, then that's a million of these pages.

Now each round trip from SSD to RAM is about 100 microseconds, and so that's 100 seconds in the worst case for us to find the item that we're looking for.

Now it's worth noting that in reality there's prefetching and there's other database optimizations that would probably actually get this down closer to three to five seconds.

But the point stands, this is far longer than a user wants to wait in order to get a query for some data for a given input ID.

So how do indexes solve this problem for us?

Well indexes are just data structures that are stored on disks and act as a map to tell us where items or on which page items exist in the database.

And so when a new query comes in for a particular item, we first pull that index into memory, check which page that index tells us the resource or the item lives on, and then we pull only that particular page.

And so as opposed to reading up to a million pages as was the case with our sequential or our table scan, now we use the index to just tell us exactly which page we should look at.

So now naturally the question becomes, well, what types of indexes are there, and when should I use them?

Let's start by first explaining what is by far the most popular database index, which is the B-tree.

And so B-trees are just basic tree structures, just like what you've learned in data structures and algorithms, where each node in the tree is a sorted list of values with pointers to another page in disk, either a child node, as the case here, or an actual data page, like here.

And so let's illustrate this with an example.

So let's say that we had a query like this where we want to select all users, whether age is exactly 51.

And in our user table, to do this, we built an index on age.

These are all the different ages of our users in our users table.

And so the first thing that we would do is we would pull in our root node into memory.

So if we go back up to our example up here, that root node itself, each one of these blue boxes is a page on disk.

We would look at it and we'd say we want 51, so it's greater than 50, less than 90.

So we're going to pull in this page next.

That would pull in a different index page.

And then we'd go in here and look at it and say, well, 51 is less than 55.

And so which page does that correspond to?

And so we come up here and we pull page 3 into memory.

And that's where all of the users that are age 51 exist.

Now what if we were to do something like this and we would change this from a direct value lookup to a range query?

Well, in this case, we're going to pull in our index, look at our root, and we're going to pull in both of these blocks into memory this time, this one and this one, because they're both greater than 50.

And now we're going to follow the pointers in each of these, so all seven of them.

And we're going to load all seven of those pages into memory because that's all of our users who are greater than 51.

The next index worth discussing is called a hash index.

And so a hash index is really straightforward.

And if you're looking for, for example, a user with a given email, you're going to pass that email into a hash function, and then you're going to have some hash map that maps that key, that hashed email, to a value where the value is just a pointer of where that data exists on disk.

And so for example, in this case, the data for John, his full row, exists on page four.

And so we're going to pull that into memory.

Now in reality, and this is important, hash indexes are rarely actually used in production databases.

So while they offer OV1 lookups, which is great, B-trees perform nearly just as well for exact matches, but they also support those range queries and sorting that we were looking at just a moment ago.

And so the only places you'll commonly see these hash indexes are for in-memory stores, things like Redis, where disk IO patterns aren't really that relevant.

So it's good to know from a historical context perspective, it's useful for caching and other things, but typically in an actual database, you're going to opt for a B-tree, not a hash index.

B-trees rock, and they're great for the majority of use cases.

But where instances, especially in a system design interview, where you wouldn't want to use a B-tree?

Well, the first place is anytime that you have geospatial data, specifically if you're trying to search within regions on latitude and longitude.

So think of a system design interview like Design Yell or Find My Nearby Friends or something.

You want everybody within a given radius of something.

And so let's talk about why B-trees don't work really well in this case.

So if I had a query that was something like this, I want all of the locations that have a latitude greater than 100, less than 400, and a longitude greater than 20, less than 200.

So B-trees really excel at one-dimensional data, but not two-dimensional data like this.

And the reason is really easy to illustrate.

And so if we look at this diagram here, that query would give us all of this data for latitude, all of this data for longitude.

And then we're going to load both of those things into memory and then do a fairly expensive merge until we get this middle area, which is what we actually care about.

And so we still needed to get each of these long strips, pull them into memory and do the merge.

Is there a more efficient way to do that?

There are specialized indexes or sometimes just algorithms before the indexing called geospatial indexing.

And the three most popular and the three best to know for system design interviews are one geohashing, two quadtrees, and three R-trees.

And we're going to really briefly go over each of these.

With geohashing, you take the map of the world, imagine that's what this is, and we split it into four parts.

We label the top left zero, then one, then two, then three.

Now we can then recursively split each of those cells and do the same thing, such that this one is now 2, 0, 2, 1, 2, 2, 2, 3.

And by continuing to do this, we get increasing levels of precision, such that maybe the New Mexico area is 31, but Albuquerque specifically is 310.

Now the nice thing is once you've converted latitude and longitude into these one-dimensional strings here, then now all nearby locations share a similar prefix.

And so this is Chihuahua, I guess, if we want to find everything near Chihuahua at this degree of precision, then we just get the geohashes near it, 321, 331, 312, and 332, and they all share similar prefixes.

And so what we do is we actually create the geohashes and then just build a B-tree on top of the hashes themselves, which allow us to easily do these range queries and these O of 1 or nearly O of 1 lookups on precise areas.

Now it's worth noting that I did this as just simple numbers for the illustration.

And so for example, Los Angeles, where I'm at, is this.

It's pretty similar to geohashing in that we split the world recursively, but there are a couple of subtle differences.

The first is that we map this recursive splitting actually to a tree, not a one-dimensional string, and we only need to go deeper in this tree in the places where we have high density.

Imagine this was a map of the world and each dot is a location in our database.

And so we split the world into four grids.

We thus create a tree where the tree has four children and that points to all of the businesses within that grid.

So all of the red businesses, all the green businesses is this node, blue and yellow respectively.

Now you'll notice there's a lot of density in the blue cell here.

And so with quadtrees, you specify a K value, which is basically saying that if any cell has greater than K value items, then recursively split.

Subtitles ListPlay Video

DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!

sort

situation

specifically

split