Name: 系統設計訪談中的 DB 索引 - B 樹、地理空間、反轉索引等！ (DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!)
Uploaded: 2025-02-10T03:55:05.000Z
Duration: 14 min 16 s

程度副詞

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?

是以，這將包括討論什麼是索引？

情態副詞

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.

現在，正如我所說的，這將是一個高層次的內容，要了解更多細節，請訪問 Hello Interview 網站，我們將深入探討數據庫索引。

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.

是以，當你想在數據庫中找到一個特定的項目，而你又沒有使用索引時，我們的做法是將一個頁面拉到 RAM（內存）中，然後掃描所有大約 100 行或項目，尋找我們要找的項目，如果沒有找到，我們就把這個頁面放回去，拉入下一個頁面，再放回去，再拉入下一個頁面，直到最終找到為止。

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.

為了說明這一點，如果我們的用戶表中有 1 億個用戶，而每個頁面如我所說可能有大約 100 行，那麼就是一百萬個這樣的頁面。

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.

現在，從固態硬盤到內存的每次往返時間約為 100 微秒，是以在最壞的情況下，我們需要 100 秒才能找到我們要找的項目。

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.

但問題是，這遠遠超出了用戶為查詢給定輸入 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.

首先，讓我們解釋一下迄今為止最流行的數據庫索引，即 B 樹。

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.

是以，B 樹只是一種基本的樹結構，就像你在數據結構和算法中學到的那樣，樹中的每個節點都是一個值的排序列表，帶有指向磁盤中另一個頁面的指針，要麼是子節點（如這裡），要麼是實際的數據頁面（如這裡）。

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.

是以，假設我們有這樣一個查詢，我們想選擇所有年齡是否正好是 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.

我們會看一下，然後說我們想要 51，所以它大於 50，小於 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.

然後，我們會到這裡來看看，然後說，好吧，51 比 55 少。

And so which page does that correspond to?

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

是以，我們來到這裡，將第 3 頁調入內存。

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.

在這種情況下，我們將調入索引，查看根目錄，這次我們將把這兩個數據塊調入內存，這一個和這一個，因為它們都大於 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.

我們將把所有 7 個頁面加載到內存中，因為這就是所有大於 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.

是以，雖然 B 樹提供了 OV1 查找功能（這非常好），但它在精確匹配方面的表現也幾乎一樣好，而且還支持我們剛才提到的範圍查詢和排序。

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.

是以，你通常只能在內存存儲（如 Redis）中看到這些散列索引，而磁盤 IO 模式在這些存儲中並不重要。

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 樹，而不是哈希索引。

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

B 樹非常適合大多數使用情況。

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

但是，在哪些情況下，尤其是在系統設計面試中，你不想使用 B 樹呢？

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.

是以，不妨考慮一下系統設計面試，比如設計 Yell 或查找我附近的朋友什麼的。

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.

是以，讓我們來談談為什麼 B 樹在這種情況下不能很好地發揮作用。

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.

是以，如果我的查詢是這樣的：我想要所有緯度大於 100、小於 400，經度大於 20、小於 200 的地點。

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

是以，B 樹真正擅長的是一維數據，而不是像這樣的二維數據。

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.

在系統設計訪談中，最受歡迎和最需要了解的三種情況是：一種是 geohashing，兩種是 quadtrees，三種是 R-trees。

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

首先，讓我們來看看 geohashing。

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

有了 geohashing，你就可以利用世界地圖，想象一下這就是地圖，然後我們把它抽成四個部分。

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

我們在左上角標上 0，然後是 1、2、3。

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.

現在，我們可以遞歸地拆分每個單元格，做同樣的事情，這樣，這個單元格現在就是 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.

繼續這樣做，我們就能獲得越來越高的精確度，比如新墨西哥地區可能是 31，但阿爾伯克基具體是 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.

我想，如果我們想以這樣的精確度找到奇瓦瓦附近的所有東西，那麼我們只需找到它附近的地理標誌，321、331、312 和 332，它們都有相似的前綴。

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.

是以，我們要做的就是創建地理散列，然後在散列本身的基礎上建立一棵 B 樹，這樣我們就能輕鬆地對精確區域進行範圍查詢和 O of 1 或接近 O of 1 的查找。

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

值得注意的是，我只是用簡單的數字來進行說明。

實際上，我們以 32 為基礎並對其進行編碼。

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.

它與 geohashing 非常相似，都是以遞歸方式分割世界，但也有一些微妙的區別。

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.

是以，在四叉樹中，你可以指定一個 K 值，基本上就是說，如果任何單元格中的項目大於 K 值，那麼就遞歸分割。

字幕列表影片播放

系統設計訪談中的 DB 索引 - B 樹、地理空間、反轉索引等！ (DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!)

sort

situation

specifically

split