DB初心者がインデックスについてまとめてみた

# はじめに

こんにちはtomokiです。
DBのインデックスってわかりづらいですよね。

私もDB初心者でわからないことが多く、書籍や技術記事等で勉強中です。

- DBのインデックスについて調べたけどよくわからない
- DBのインデックスの設計についてよくわからない

といった悩みをあなたはもっていないでしょうか。
今回はインデックスについてわかりやすくまとめてみたいと思います。

# インデックスとは

本の索引のような概念です。インデックスを使うことで検索や更新を高速に行うことができます。
- 書籍の索引では単語とページが書かれており、単語を全ページから調べなくてもすぐに調べたい単語のページを見つけることができます。

# インデックス設計

- アプリケーションに影響を与えない

→インデックスを使うかどうかはDBMSが自動的に判断するのでアプリケーションコードに影響を与えません

- テーブルのデータに影響を与えない

→インデックスを作成することによるテーブルのデータの変更は必要はありません。

- それでいて性能改善の効果が大きい

→インデックスを作成することによりデータ量に対して緩やかにしかDBパフォーマンスが低下しません

# B-treeインデックスとは

![スクリーンショット 2022-11-20 14.47.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/712442/312f4dc7-5fd8-2c9f-9f3f-38af50bc9910.png)

インデックスにもいくつか種類があり、それぞれにメリットやデメリットがあります。中でもB-treeインデックスはもっともポピュラーでB-treeインデックスしか使わない場面が多くあります。

B-treeインデックスは木構造でデータを持ち、最上位からノードを探索し、最下位へとデータの探索を行っていきます。最下位ではデータに変換するポインタを持っており、リーフからデータを探索します。

# B-treeインデックス構造

B-treeインデックスの特徴は以下です

- 均一性

→B-treeは平行木です。平行木とはどのノードから辿ってもデータまでの距離が一定になります。そのため、探索をどのデータでも同じ計算量で行うことができます

- 持続性
![スクリーンショット 2022-11-20 15.04.18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/712442/d21d9199-705e-dac8-a5b5-8809089519e5.png)
→データ量に対して緩やかにしかDBパフォーマンスが低下しません。なぜなら、平行木は平たく、データ量が増えたとしても探索をほぼ同じ計算量で行うことができるからです。

- 処理汎用性

→挿入、更新、削除も検索と同様に処理されるため、汎用性があります。

- 非等値性

→等号(=)、不等号(<, >, ≤, ≥)やBETWEENといった範囲検索では高速化が可能となります。なぜなら、B-treeインデックスは構築時にソートされるため、平行木で特定のノードよりも左か右かで探索範囲を絞ることができるからです。逆に否定条件(<>, !=)は特定の値以外の全てのノードを探索する必要があるためB-treeインデックスによる絞り込みができません。

- 親ソート性
GROUP BY、ORDER BY、COUNT、MAXなどのソートを高速に行うことができます。

# B-treeインデックスの設計方針

インデックスを闇雲に作成しても効果があるということではありません。インデックスの効果を発揮するには以下のような設計方針が必要になります。

- 大規模なテーブルに対して作成する
- カーディナリティーの高い列に作成する
- SQLでWHERE句の選択条件、または結合条件に使用されている列に作成する

## テーブルの規模

![スクリーンショット 2022-11-20 15.04.18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/712442/0c86d46e-9252-2442-49a5-67e0f3010cbf.png)

先ほどB-treeスキャンはデータ量に対して緩やかにしか探索時間が延長しないと述べました。グラフでも分かるとおり、フルスキャンの方が、高速に探索することができるデータ量の範囲があります。具体的な閾値はレコード1万件以下と言われています。  
そのためよりレコードの多いtableの列に対してインデックスを作成するとより効果を発揮しやすくなります。

## カーディナリティー

カーディナリティーとは特定の列のレコードの種類がどのくらいあるのかということです。例えばあるテーブルのスポーツの列でサッカー、バスケという２種類のレコードが登録されている場合はこのカーディナリティーは２つということになります。

このカーディナリティーが高い列を選ぶことが基本です。目安として全体の5%以下しか絞り込めないカーディナリティーであることです。先ほどのスポーツの列でバスケを絞り込むためには2つのうちの1つになるため、1 / 2 * 100で50%になります。

別の例で日付の列では1年は365日あるのでカーディナリティーは365あります。そのうち1つ絞り込むためには1 / 365 * 100の四捨五入で0.3%の絞り込みです。

# SQL

インデックスを作成した列に対してインデックスを使用できないSQLがあります。以下はインデックスを使用できません

## インデックス列に演算を行なっている

```bash
SELECT * FROM ExampleTable WHERE col_1 * 1.1 > 100;
```

インデックスを作成してSQLでは裸で用いるのが条件です。

インデックス内で保持されているデータはcol_1のためcol_1 * 1.1をWHERE句で絞り込んでもインデックスを使用することができません。

## 索引列に対してSQL関数を適用している

```bash
SELECT * FROM ExampleTable WHERE SUBSTR(col_1, 1, 1) > 100;
```

このSQLも同様でインデックス内で保持されているデータはcol_1のためSUBSTR(col_1, 1, 1)をインデックスで使用することはできません。

## IS NULLを使っている

```bash
SELECT * FROM ExampleTable WHERE col_1　IS NULL;
```

NULLはデータ値としてみなされないため、インデックスを保持していません。そのため、IS NULLで絞り込んだとしてもインデックスが存在しないということになります。

## 否定系を用いている

```bash
SELECT * FROM ExampleTable WHERE SUBSTR col_1 <> 100;
```

先程も説明しましたが、否定形を利用すると全てのノードに対して探索してしまうのでインデックスの効果を発揮することができません

## ORを用いる

```bash
SELECT * FROM ExampleTable WHERE SUBSTR col_1 10 OR 100;
```

インデックスにORは使用できないためINを使用します。

```bash
SELECT * FROM ExampleTable WHERE SUBSTR col_1 IN(10, 100);
```

## 後方一致、または中間一致のLIKE述語を用いている

```bash
❌ SELECT * FROM ExampleTable WHERE　col_1 LIKE '%m';
```

```bash
❌ SELECT * FROM ExampleTable WHERE　col_1 LIKE '%m';
```

```bash
🟢 SELECT * FROM ExampleTable WHERE col_1 LIKE 'm%';
```

## 暗黙の型変換を行なっている

文字列型であるcol_1に対してのSQLで以下のようにすると

```bash
❌ SELECT * FROM ExampleTable WHERE col_1 = 10;
```

```bash
🟢 SELECT * FROM ExampleTable WHERE SUBSTR col_1 = '10';
```

DBMSでは型定義と異なる型が指定された場合は型変換を行なって絞り込まれますが、インデックスは使用されなくなります。

# B-treeインデックスは高性能を劣化させる

インデックスはテーブルとは別のオブジェクトとしてDBMS内部に保持されます。そのため、インデックスが作成されているテーブルの列の値を変更するとインデックス内の値も変更が必要になります。例えば列の型を数値型から文字列型に変更する場合はインデックスで保持されている値を全て数値型から文字列型に変更する必要があります。

# 参考

達人に学ぶDB設計 徹底指南書 ～初級者で終わりたくないあなたへ

https://www.shoeisha.co.jp/book/detail/9784798124704

# 最後に

間違っている箇所やわかりずらい箇所がありましたらご指摘いただけるとありがたいです。