🌲

B-Treeについてなんとなく理解してみた

に公開
MySQL
DB
tech

DBのIndexとは?

最近、DBのパフォーマンスチューニングを行っているのですが、Prismaにこんな構文があることを知りました。@@index
このindexをつけることによって、DBの検索パフォーマンスが向上するらしいです。
ここら辺の知見がないので、Indexについて調べてまとめてみたいと思います。

Indexをつけると何が起きるか？

Indexをつけると以下のメリットがあるみたいです。

  • 検索の高速化: WHERE句で頻繁に指定するカラムに設定すると、読み取り速度が劇的に上がる。
  • 並べ替えの効率化: ORDER BYでよく使うカラムに設定すると、ソート処理が軽くなる。
  • 結合の最適化: リレーションシップで繋がっているカラムに設定することで、データの紐付けがスムーズになる。

多くのデータベースでは、インデックスをB-Treeというツリー状の構造で保持しています。

B-Treeとは？

インデックスがない状態では1ページ目から順にめくって探すしかありませんでしたが、B-treeがあると、目的のデータがどのあたりにあるかを数回のステップで絞り込めるようになります。

B-treeによる14の検索プロセス

  1. スタート地点：ルートノード、まず一番上のノードを見ます。ここには12という数字があります。

  2. 探している14は、12よりも大きいです。
    B-treeは、この比較結果に基づいて右のノードへ進むと判断し、次の階層へ移動します。

  3. 次の中間ノードへ 右に進んだ先のノードには15という数字があります。
    今度は、探している14は15よりも小さいです。
    B-treeは、再びこの比較結果に基づいて左のノードへ進むと判断し、さらに下の階層へ移動します。

  4. 目的地：葉（リーフ）ノードに到着⭕️ 左に進んだ先のノード（緑色の箱）を見ると、左に進んだ先のノード（緑色の箱）には14が含まれており、目的のデータを見つけることができました。

この一連の流れを見ていただくとわかるように、B-treeは無関係なデータを無視できます。
12と比較した時点で、その左側にある3、1、9といったノードは一切調べる必要がなくなります。
また、各ノードでの比較によって、探す範囲を大幅に絞り込んでいけます。

例えば？

Prismaの例

model Item {
  id    Int    @id @default(autoincrement())
  name  String
  price Int

  @@index([name]) // nameカラムにインデックスを作成
}

例えば、nameがりんごの商品を探すクエリを発行したとします。

インデックスがない場合（全件スキャン）は、テーブルの1行目から順に**これは『りんご』かな？**と最後まで確認します。100万件データがあれば、100万回チェックする可能性があります。🏃♂️💨

インデックスがある場合（B-tree探索）は、先ほどの図のように、五十音順（あいうえお順）に並んだ木を辿ります。

『さ』より前か後ろか？→前だ（左へ）、『か』より前か後ろか？→後ろだ（右へ） というように、わずか数回のステップでりんごの場所にたどり着きます。

注意点

  • 書き込みが遅くなる
    データを1つ追加するたびに、データベースは本体への書き込みだけでなくインデックスへの追加も必要になります。インデックスが多いほど更新箇所が増えるため、書き込みが多いテーブルにインデックスをかけすぎると逆に遅くなることがあります。

  • インデックスの断片化・肥大化
    削除や更新が繰り返されると、インデックスのページ内に空きスペースができたり、不要なエントリが残ったりして、検索効率が低下することがあるらしいです。この場合は定期的なメンテナンスが必要になるみたいです。

Discussion