はじめに
はじめまして、私は2023年に新卒としてBIPROGY株式会社に入社した高畑です。
今回は自己啓発の一環として勉強したSQLのインデックスの種類についてまとめてみました。
インデックスとは
インデックス（直訳：索引）とは
索引（さくいん）とは、百科事典・学術書などにおいて、特定の項目を素早く参照できるよう、見出し語を特定の配列に並べ、その所在をまとめたもの。1
だそうです。書籍の最後の方に、何が何ページに書かれているか一覧になっているものがあると思います。
DBサーバーにおいても書籍と同様にインデックスを張ることができ、SQLの高速化を図ることができます。
なぜインデックスを張ると速くなるのか
なぜインデックスを張ると速くなるのかを示すために、今回は以下のUserテーブルを用いて考えます。
Userテーブル
| id | name | age |
|---|---|---|
| 1 | Tom | 25 |
| 2 | Sarah | 22 |
| 3 | John | 20 |
| 4 | Alice | 27 |
| 5 | David | 22 |
今、Userテーブルからageが25以上のレコードを取得しようと思います。クエリで表すならこうです。
SELECT * FROM User WHERE age >= 25
まずageについてインデックスを張っていない場合について考えます。インデックスを張っていない場合はテーブルの最初のレコードから順に見ていき、ageが25以上の場合は結果に入れていきます。それを最後の行まで繰り返し行い、最終的にageが25以上のレコードすべてを返却します。このようにテーブルの全部の行をスキャンすることを全表スキャンと言います2。
次にageについてインデックスを張った場合について考えます。今回はBツリーインデックス（後述）で考えます。
ageについてインデックスを張った場合
| age | 物理アドレス |
|---|---|
| 20 | 103 |
| 22 | 102 |
| 22 | 105 |
| 25 | 101 |
| 27 | 104 |
今回物理アドレスはid+100としています
このようにageについてインデックスを張った場合は
- インデックスを作成した列のデータ
- そのデータが含まれる行の物理アドレス（ポインタ）
が格納されています。また、インデックスはageの値でソートされていることも分かります。この性質によりageが25以上のところから探索を始めることができ、全表スキャンするよりも高速に結果を返すことができます。
インデックスの種類について
一言インデックスと言っても様々な種類のインデックスが存在しています。今回はDBスペシャリスト試験にもよく出てくる以下の
- B(+)ツリーインデックス
- ハッシュインデックス
について書いていこうと思います。
B(+)ツリーインデックス
B(+)ツリーインデックスは名前の通り木構造を用いたインデックスです。ノード中にキー値とデータへのポインタが含まれています。また、木構造を活用し、高速に数値の探索を行うことが可能です。
（参考：https://devblog.thebase.in/entry/2018/12/09/110000 ）
ここでBツリーインデックスとB+ツリーインデックスではデータへのポインタの付き方が異なってきます。
Bツリーインデックス
Bツリーインデックスでは実データへのポインタが、ルートノード・ブランチノード・リーフノードといったすべてのノードに付与されます。そのため、データの探索条件がルートノードに近いもの（今回の場合だとキー値が5,8,10のもの）には迅速にアクセスできます3。
B+ツリーインデックス
B+ツリーインデックスではBツリーインデックスとは違い、リーフノードのみ実データへのポインタが付与されます。また、各リーフノードには次リーフノードへのポインタが含まれています。そのため範囲検索においてはブランチノードやルートノードへ戻る必要がない分、Bツリーインデックスよりも探索効率がよいというメリットがあります3。そのため、現在では多くのDBMSにおいてBツリーインデックスではなくB+ツリーインデックスが採用されています4。また、これ以降の説明ではB+ツリーインデックスにおける説明をします。
B+ツリーインデックスが有効となる検索方法例
範囲検索
ageにB+ツリーインデックスを張った場合、以下のように定数値における範囲検索では有効に活用できます。理由としてはリーフノードがキー値でソートされるためです。
SELECT id FROM User WHERE age >= 25
前方一致検索
nameといった文字列にB+ツリーインデックスを張った場合、最初の文字から順にソートされます。そのため、前方一致の検索の場合のみ、B+ツリーインデックスが活用されます。
SELECT name FROM User WHERE name ='J%'
ハッシュインデックス
ハッシュインデックスは、ハッシュ関数（任意の長さのデータを一定の長さのデータに変換する関数5）を用い、検索に使用するキーとレコードを直接関係づけるインデックスです6。今回は例として以下のUserテーブルを例にして考えます。
Userテーブル
| id | name | age |
|---|---|---|
| 1 | Tom | 24 |
| 2 | Sarah | 22 |
| 3 | John | 20 |
| 4 | Alice | 28 |
| 5 | David | 32 |
今回ageカラムにハッシュインデックスを張ります。また、今回利用するハッシュ関数はage % 5とします。また、便宜上実レコードのポインタはidとします。
ageカラムのハッシュインデックス
| ハッシュキー | ポインタ |
|---|---|
| 0 | 3 |
| 1 | |
| 2 | 2,5 |
| 3 | 4 |
| 4 | 1 |
ここでageが22のレコードを取得しようと思います。クエリで表すなら以下のようになります。
SELECT * FROM User WHERE age = 22
まずage=22のハッシュ値を考えます。22 % 5なので2になります。そのためハッシュキーが2のところを探索します。そうするとポインタが2,5のレコードが該当します。ハッシュインデックスではインデックスを用いた検索の後、再度検索結果の正当性を確認する処理（リチェック処理）を行います7。リチェック処理を行った結果idが2のレコードが返却されます。以上の処理により高速にレコードを取得できます。
ハッシュインデックスのメリットとしては、ハッシュ関数によってうまくデータが分散されている場合、ほぼ定数時間 O(1) で検索できる点です6。しかし、うまくレコードが分散するハッシュ関数を用いないと衝突が発生し、効率が下がるというデメリットもあります。そのため、使用するハッシュ関数の選定は意識する必要があります。
また、ハッシュインデックスは一致検索にしか使えないというデメリットもあります。理由として、範囲検索などでは複数のハッシュキーを検索する必要があるため、あまり効率的ではないためです。
インデックスを張る際の注意点
ここまでインデックスを張ることに対するメリットを紹介してきました。しかし、インデックスを張ることでデメリットもあります。そのデメリットをここで何点か紹介しようと思います。
処理速度の低下
インデックスはデータを取得する際に有効ですが、インサートやアップデートなどの処理においては逆にボトルネックとなることがあります。その理由は、インサート・アップデートを行うことでインデックスの再構築が発生し、余計なコストとなってしまうためです8。
ストレージの圧迫
インデックスを張ることにより、データベースのストレージを消費します。よって、不必要な大量のインデックスを張ってしまうとストレージの容量不足の原因となってしまいます。そのため、必要なカラムにのみインデックスを張る必要があります9。
おわりに
一口にインデックスを張るといっても、様々な種類のインデックスがあります。また、それぞれのインデックスにおいてメリット・デメリットが存在しているため要件に合わせたインデックスを選択する必要があります。今回は、B(+)ツリーインデックス・ハッシュインデックスの紹介をしましたが他にも様々な種類のインデックスがあるので興味のある方は調べてみると面白いかもしれません。
We Are Hiring!
-
https://www.oracle.com/jp/a/tech/docs/technical-resources/index-tuning1.pdf ↩
-
https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees ↩ ↩2
-
https://www.jipdec.or.jp/project/research/why-e-signature/hash-function.html#:~:text=%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0%EF%BC%88Hash%20Function%EF%BC%89%E3%81%A8,%E9%96%A2%E6%95%B0%EF%BC%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%EF%BC%89%22%E3%81%A7%E3%81%99%E3%80%82 ↩
-
https://xtech.nikkei.com/it/article/COLUMN/20060113/227241/ ↩ ↩2