B-treeインデックスによるインデックス設計

## はじめに
インデックスとはSQLのパフォーマンスを向上させる重要な機能であり、多くのデータベース設計に組み込まれています。

しかし、インデックスとは何かよくわからないまま使うと、その恩恵を得ることができません。
本記事では、インデックスの中で最も使用頻度の高いB-treeインデックスに焦点を当てて、インデックス設計を解説します。

### 備考
- 本記事はMySQLを例に説明しますが、他のDBMSでもB-treeインデックスは利用可能です。
- 本記事は「達人に学ぶDB設計 徹底指南書」の6章データベースとパフォーマンスの章を参考に記述しています。

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

## B-treeインデックスとは
B-treeインデックスはその名の通り、木構造を用いてデータを索引する方式です。
B-treeインデックスは、他のインデックスタイプに比べて汎用性が高く、データベースに用いるほとんどのインデックスはB-treeインデックスと言われています。

### B-treeインデックスの長所
B-treeインデックスが選ばれるのは、どの使い方をしても平均的にパフォーマンスを上げられれるためです。

その長所を３つ紹介します。

#### データ量の増加に比例してパフォーマンスが低下しにくい
B-treeインデックスは、パフォーマンス劣化が非常に緩やかです。
インデックスはデータの挿入、更新、削除の増加に伴い、探索の速度にばらつきが出始めます。
しかしB-treeインデックスは、データ量が増えても検索速度があまり変わらないため、長期運用に適しています。

なぜパフォーマンス劣化が緩やかなのかは、B-treeインデックスの構造にあります。
B-treeインデックスは平べったい木構造をしています。

![スクリーンショット 2023-12-03 16.53.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1650886/ce6be3ec-9282-6f04-2553-caba89b3ce5e.png)

一番上のルートから一番下のリーフまで、高さは3～5ほどです。
これは、データ量が何百万、何千万行となっても変わりません。

このように、背が低い木はルートからリーフまでの高さが低いため、データ量が増加しても検索速度は早いままでいることができます。

#### 等価（=）の他に、不等号（>, <, =>, <=）を使ってもそこそこ早い
B-treeは、構築されるとき必ずキー値をソートします⁠。
そのため、等号（=）だけでなく、範囲検索でもある程度パフォーマンスを上げることが可能です。

例えば、WHERE句で「3以下」という条件を指定した場合、「４以上」の値は検索対象になりません。
![スクリーンショット 2023-12-03 20.55.24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1650886/2f226d3c-666c-3f1e-ba84-0cc13b0d3f57.png)


これにより、B-treeは、等号だけでなく、不等号やBETWEENを使った条件に対しても高速な検索が可能です⁠。
これは、ハッシュインデックスにはない利点です。

```sql
-- 不等号（>, <, =>, <=）を使える
SELECT * FROM test
 WHERE indexed_col > 100;

-- BETWEENも使える
SELECT * FROM test
 WHERE indexed_col BETWEEN 10 AND 100;
```

ただ、やはり等号（=）を使った方が不等号より早いです。
また、否定条件（<>、!=）に対しては、B-treeインデックスは使えないため注意が必要です。

#### ソートを使う処理（GROUP BY,ORDER BY）で高速化できる
遅いSQL文によくありがちなパターンとして、巨大なソートをしている場合があります。
次のような処理をSELECT文やUPDATE文に記述したとき、暗黙的にソートが行われています。

- 集約関数（COUNT、SUM、AVG、MAX、MIN）
- ORDER BY句
- 集合演算（UNION、INTERSECT、EXCEPT）

ソートはかなりコストの高い演算です。
データ量が膨大でメモリ上には収まりきらない場合、データベースは一時的に、ディスクへデータを書き出すディスクソートを行います。
ディスクソートが発生すると、I／O負荷（データの出し入れによる負荷）が発生し、ガクンとSQLのパフォーマンスが落ちます。

![スクリーンショット 2023-12-03 18.20.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1650886/32846f11-3eea-7ba7-c125-c5c5f065c856.png)

上記にもありますが、B-treeは、構築されるとき必ずキー値をソートします⁠。
そのため、B-treeインデックスの存在する列をソートする際は、すでにソートし終えている状態のため、負荷を軽減することができます。

これは複合インデックスの場合にも当てはまります。

## B-Treeインデックスはどのカラムに作るのがよいか？
B-Treeインデックスはやみくもに作ればいいわけではなく、適切な使い方があります。
代表的な使い方を以下に並べます。

- 大規模なテーブル
- カーディナリティが高いカラム
- WHERE句の選択条件、結合条件に使われるカラム

順に説明していきます。

### 大規模なテーブル
インデックスがない場合の検索はすべてのレコードを検索するフルスキャンです。
レコード数が少ない場合、インデックスをつけても、つけなくても、検索する量が少ないため速度はあまり変わりません。

その場合、わざわざB-Treeインデックスをつける必要もありません。
逆に、レコード数が多いテーブルはインデックスはつけるべきです。

どの程度がデータ量が多い、に該当するかはサーバーの性能によって変わりますが、大体１万レコード以上の場合はB-Treeインデックスありの方が早いとされています。

### カーディナリティが高いカラム
カーディナリティは組になっている要素の数を表します。
「性別」の要素を考えた時「男性」「女性」「不明」の３つがあるとします。
この時、カーディナリティは３です。
これは非常に小さなカーディナリティになります。

カーディナリティが高い例として「商品の売上日」「ユーザーID」などが挙げられます。
売上日は毎日売れれば、１年で365カーディナリティが増えますし、ユーザーIDはユーザー数が増えるほど大きくなります。

### WHERE句の選択条件、結合条件に使われるカラム
当たり前の話ですが、インデックスが効果を発揮するのは、検索・結合に使うカラムのみです。

ただしB-treeインデックスを使う際、いくつかNG例が存在するため、一部紹介します。

#### NG例１：インデックス列に演算を行っている
インデックスのあるカラムをSQLで問い合わせる時は、「裸」の状態で使用してください。
下の例だと、検索を行うカラムはあくまで、「index_col」であって、「index_col　* 2」ではないためです。

```sql
-- NG例
SELECT　* FROM table WHERE index_col * 2 > 100;

-- OK例
SELECT　* FROM table WHERE index_col > 100　/ 2;
```

#### NG例２：IS NULLを使う
B-treeインデックスではNULLはデータ値とみなされず、インデックスに保存されません。
そのため、`IS NULL`、`IS NOT NULL`はソートの対象となりません。

```sql
-- NG例
SELECT　* FROM table WHERE index_col　IS NULL
```


#### NG例3：前方一致以外のLIKE句
LIKE句を使う場合、基本的に前方一致の場合のみインデックスが適用されます。

```sql
-- NG例：中間一致を使用している
SELECT * FROM table WHERE index_col LIKE '%Patrick%';

-- NG例：後方一致を使用している
SELECT * FROM table WHERE index_col LIKE LIKE '%Patrick';
```

### 売上テーブルを例に検証
やってみる方が早い！ということで、インデックスをつけたバージョンと付けないバージョンでどれほど速度が変わるのか検証してみましょう。
次の売上テーブルを作成し、１万件のデータを入れてみます。
B-treeインデックスは売上日`sales_date`につけました。

```sql
-- CREATE文
CREATE TABLE sales_index (
    sales_id INT AUTO_INCREMENT PRIMARY KEY,
    product_name VARCHAR(255) NOT NULL,
    category VARCHAR(100) NOT NULL,
    price DECIMAL(10, 2) NOT NULL,
    sales_date DATE NOT NULL,
);
-- INDEXの追加
create index sales_date_index on sales_index(sales_date);
```

使用したダミーデータ生成サイト
https://filldb.info/

#### 測定に使うクエリ
B-treeインデックスは集合関数にも使えるということで、売上日ごとの売上個数を検索するクエリで測定してみました。

```sql
SELECT
    sales_date,
    COUNT(sales_date) as 日毎の売上個数
FROM
    sales_index
GROUP BY
    sales_date
ORDER BY
    sales_date
;
```

#### 結果
結果は、インデックスなしが「0.0244秒」、インデックスありが「0.0084秒」とインデックスありの方が格段に早いことが見て取れます。
１万件のレコードでこの速度の違いのため、レコード数が増えればさらにパフォーマンスに如実に現れそうですね！


|     -             |   クエリにかかった時間       |
| ---------------- | -------- | 
| インデックスなし | 0.0244秒 | 
| インデックスあり | 0.0084秒 |


速度計測クエリのこちらのブログを参考にさせていただきました。
https://collapse-natsu.com/post/mysql_query_speed

```sql
-- 測定クエリ
SELECT
    EVENT_ID,
    TRUNCATE(TIMER_WAIT / 1000000000000, 6) AS Duration,
    SQL_TEXT
FROM
    performance_schema.events_statements_history_long
WHERE
    SQL_TEXT LIKE "%SELECT sales_date ,COUNT(sales_date) as 日毎の売上個数 FROM sales_index GROUP BY sales_date ORDER BY sales_date%"
;
```

#### おまけ：インデックスの高さを確認する
検索で使用したクエリの頭に`EXPLAIN`をつけると、クエリの実行状況を表示してくれます。
その中の「key_len」がインデックスの高さになります。
今回は高さが「３」となっていました。

```sql
EXPLAIN SELECT ,sales_date ,COUNT(sales_date) as 日毎の売上個数 FROM sales_index GROUP BY sales_date ORDER BY sales_date;
-- key_len: 3
```

## まとめ

B-treeインデックスとはなにか？また、その使い方を解説しました。
新人研修などではさらっと流される部分ではありますが、SQLクエリチューニングにおいて重要な役割を持っているので、どんどん使いこなしていきたいですね。

### 参考

https://gihyo.jp/dev/serial/01/sql_academy2/000701#sec2_h3

B ツリーインデックスの特性
https://dev.mysql.com/doc/refman/8.0/ja/index-btree-hash.html#btree-index-characteristics