Name: システム設計におけるDBインデクシング インタビュー - B-tree、Geospatial、Inverted Indexなど！ (DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!)
Uploaded: 2025-02-10T03:55:06.000Z
Duration: 14 min 16 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

程度の副詞

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.

そのため、データはページ単位でデータベースに配置される。

ページは通常8キロバイトのデータである。

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行程度だとしたら、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.

SSDからRAMへの各ラウンドトリップは約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.

実際には、プリフェッチやその他のデータベースの最適化によって、3秒から5秒近く短縮できるだろう。

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.

そして、特定のアイテムに対する新しいクエリーが来ると、まずそのインデックスをメモリに取り込み、そのインデックスが示すリソースやアイテムがどのページにあるかをチェックし、その特定のページだけを取り込む。

この場合は1ページ目だったかもしれない。

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.

そして、シーケンシャル・スキャンやテーブル・スキャンのように100万ページも読み込むのではなく、インデックスを使ってどのページを見るべきかを正確に指示する。

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.

私たちはそれを見て、50以上90未満の51が欲しいと言う。

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.

そして、そこに51歳のすべてのユーザーが存在する。

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.

そして、これからそれぞれのポインタに従って、7つすべてのポインタに従うことになる。

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.

そして、51歳以上の全ユーザーのために、これらの7ページすべてをメモリにロードする。

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.

例えば、あるEメールを持つユーザーを探す場合、そのEメールをハッシュ関数に渡し、そのキー、ハッシュ化されたEメールを値にマッピングするハッシュ・マップを持つことになる。

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

例えば、この場合、ジョンのデータは4ページ目に存在する。

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.

だから、デザインエールとか、近くの友達を探すとか、そういうシステムデザインのインタビューを考えてみてほしい。

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-treeは1次元のデータを得意とするが、このような2次元のデータは苦手なのだ。

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.

そして、最もポピュラーで、システム設計の面接のために知っておくべきベスト3は、1つのジオハッシュ、2つのクワッドツリー、3つのRツリーである。

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.

ジオハッシングでは、世界地図を4つに分割する。

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

左上にゼロ、次に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, 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.

これにより、範囲クエリや、正確なエリアに関するO/1またはほぼO/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.

再帰的に世界を分割するという点ではジオハッシュとよく似ているが、微妙な違いがいくつかある。

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.

そして、世界を4つのグリッドに分けた。

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

こうして、ツリーが4つの子を持ち、そのグリッド内のすべてのビジネスを指すツリーを作成する。

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.

4分木の場合、K値を指定する。これは基本的に、どのセルにもK値以上の項目があれば、再帰的に分割するということだ。

システム設計におけるDBインデクシング インタビュー - B-tree、Geospatial、Inverted Indexなど！ (DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!)

字幕リスト動画再生

システム設計におけるDBインデクシングインタビュー - B-tree、Geospatial、Inverted Indexなど！ (DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more!)

sort

situation

specifically

split