インデックス
インデックスとは
インデックス（索引）は、データベースの性能を向上させる方法の１つ。
インデックスが設定されていない場合、テーブルの最初から順番に１件ずつ探すため、時間がかかる。
インデックス設定が悪いと却って検索速度の低下を招いてします恐れがある為、一般的には下図のような場合にインデックスを設定する。
参考: データベース性能を向上させる「インデックス」を理解する：「データベーススペシャリスト試験」戦略的学習のススメ（26） - ＠IT
インデックスのデータ構造
B-Tree+
最もオーソドックスな構造で基本的にはこれがデフォルトで使われるっぽい。
B-Tree+はルートノード (親要素を持たないブロック)、ブランチノード(親、子要素を持つブロック)、リーフノード(子要素を持たないブロック)の3つの階層から構成される。
ルートノードとブランチノードはキー値と子ノードへのポインタを持つ。リーフノードはキー値とレコードへのポインタを持つ。(つまり、レコードを持つのはリーフノードだけ)
参考: B木 - Wikipedia
検索
検索する際、ルートノードから出発し、ブランチノードへのポインタに沿ってリーフノードを探す。
検索値よりも大きな値のポインタが見つかったら、その左側のブランチノードへ移動する。検索値よりも大きな値は見つからない場合、キーの最大値の右側のブランチノードへ移動する。
ブランチノードでも同様のことを繰り返し、最終的に目的の値が存在しないと判断するか、リーフノードにたどり着く。
インデックスの生成
テーブルに既にデータが存在する状態でインデックスが生成されるケースです。
- インデックスに指定されたカラムの順序に沿って、値をソートする。
- ソートされた結果を
リーフノードに記録する。 - リーフノードがPCTFREE(Perfect free: 空き領域率)に到達し、新しいリーフノードを要求したら、ブランチノードを生成する。このブランチノードは
ルートノードとなる。 - 2と３の繰り返しが完了するまで行われる。
削除と更新
データを削除するとレコードは物理削除されるが、インデックスの行に対しては削除されたことを示す表示が追加されるだけ。
削除された場合
- ブランチノードに存在する、該当リーフノードを示す行に削除表示が挿入される。
更新された場合
- 上記の削除された場合の処理が実行される。
- 更新後のデータを格納する先にリーフ行の空きがない場合は、リーフ分割して格納される。
上記の処理のため、インデックス行数は変わらず、削除インデックス行が増加していくことになる。このため、修正が頻繁に発生しない列をインデックスで使用するのを心掛ける。
複合インデックス
複数のカラムを組み合わせたインデックスのこと。複合インデックスの構造は先頭のカラムから順にソートされる為、同じカラムの組み合わせでも順番によって作成されるインデックスの構造が異なるので注意する。
下記のサイトが分かりやすかった。
【図解】B-treeを理解し、複合インデックスの順番を正しく作る | Enjoy IT Life
