Zenn
🔖

B-Tree index入門

2024/03/03に公開
Database
#
rdbms
#
index
tech

B-tree インデックスについて基礎的な部分をまとめてみました。
勉強中な部分もあり、間違いがあれば指摘いただけると助かります。

インデックスとは

B-tree インデックスの説明の前にそもそもインデックスについて説明します。

インデックスとは翻訳すると「索引」という意味を持っているように、DB においても索引の役割を果たします。
本などを読んでいると最後ページあたりに索引があると思うのですが、その索引を使用すると、どのページで該当の単語が使われたのか確認することができます。
DB における索引も同じようなイメージで、どのデータがどれくらいの場所にあるのか、すぐ分かるような仕組みのことです。

フルスキャンとインデックススキャン

インデックスを使用する前によく使用する単語として、「フルスキャン」と「インデックススキャン」があります。

フルスキャンは、データベースの全レコードを順番に読み取る方法です。
インデックススキャンは、データベースの読み取り時にインデックスが使われる方法です。

データが少ない場合はフルスキャンでもデータ取得速度は変わらず、むしろフルスキャンの方がパフォーマンスが良い場合もあるのですが、基本的にはデータ量が増えた時にフルスキャンをするとパフォーマンスが悪くなっていきます。

なので基本的には、データ量が増えていく場合インデックスを貼り、インデックススキャンにしていく必要があります。

「そもそもなぜインデックスが必要なのか？」
という問いに関しては「データ取得を高速化するため」が大きな理由です。

インデックスの種類

インデックスの手法にもいくつか種類があります。

  • B-tree インデックス
  • B+tree インデックス
  • ハッシュインデックス
  • ビットマップインデックス

など、他にもいくつかあります。
今回説明をしていくインデックスの種類は「B-tree インデックス」についてです。

B-tree インデックス概要

B-Tree インデックスは、以下画像のよう平衡木(バランス木)の構造を持っています。

各データのことを「ノード」と呼び、一番上の元となるノードを「ルードノード」、一番末端にあるノードを「リーフノード」と呼びます。

各ノードは、探索したい値が「自分より大きいか小さいか」を判断します。
B-tree は大きい値を右下、小さい値を左下に置くので、値が大きければ右下に、小さければ左下に移動します。
ルートノードからリーフノードにかけて値の判定をしていき、最終的に同じ値に辿り着けば取得できるということです。

フルスキャンよりも圧倒的に探索スピードが早く、データ数が多いほどこの恩恵を受けることができます。

B-Tree インデックス動作確認

実際に B-tree インデックスの動きを確認してみます。
※1~15の数値がデータとして入っています。

動作確認には以下のサイトを使用してます。

取得

今回は9を取得します。

以下の動画を見ていただければわかるのですが、取得の流れとしては以下のようになってますね

  1. 9 → 8より大きいので右下に移動
  2. 9 → 12より小さいので左下に移動
  3. 9 → 10より小さいので左下に移動
  4. 9発見

削除

9を削除します。
探索の流れは取得と同じですが、値が削除された時に平衡木の調整がされます。

挿入

9を挿入
こちらも取得と同じ流れで探索を行い、該当の平衡木の箇所に挿入された後、平衡木の調整がされます。

インデックスの注意点

データの取得時には大きな力を発揮するインデックスですが、いくつか注意点もあります。

  • データ更新時のパフォーマンスが下がる
    • データ更新時にインデックスにも変更が入るので、データ量が多いと更新速度に影響が出る可能性があります。
  • 定期的なメンテナンスが必要
    • インデックスが更新され続けると、次第に構造が崩れていきパフォーマンスが落ちることがあるので、定期的にインデックスの再構築や見直しをする必要があります。
  • インデックスが効かないクエリがある
    • 演算や後方一致などのクエリではインデックスが効かずフルスキャンになってしまうことがあるので、RDBMS のドキュメントを確認したり、EXPLAINなどで実行クエリを確認する必要があります。
  • データの種類が多いカラムにインデックスを貼る
    • データの種類が多い（カーディナリティが高い）カラムの方がインデックスの力が発揮されやすいので、インデックスを貼る際には意識をする必要があります。

まとめ

サービスを大きくしていくにあたってインデックスの知識は必須ですよね。
DB 設計周りはまだ勉強中なので、時間があれば以下の内容もまとめれたらなと思ってます。

  • 単体インデックス / 複合インデックス
  • EXPLAINを使用したパフォーマンスチューニング

またこちらの zenn 本もとても分かりやすかったので、お時間ある方はこちら見てみても面白いかもです。

参考

Discussion