MySQLの仕組み
インデックスの仕様の仕組み
- インデックスは特定の行を素早く見つけるために使われる。
- インデックスがあることで、全てのデータを調べることなく、データファイルの途中のシークする位置を特定できる
- ほとんどのMySQLインデックス（PRIMARY KEY UNIQUE INDES FULLTEXT）はBツリーに格納される
- 例外：空間データ型のインデックスはRツリーを使用
B-tree
B-treeとは、1つのノードがm個 (m>=2) の子ノードを持つことができる平衡木構造のことです. ブロックの読み取り回数は木の深さになります。 AVL木の場合、log n 回なのに対して、B-treeの場合、log n / log m 回 (※計算は省略) になります。そのためmが大きくなるほど、処理時間に差が出てきます。 このことから、MySQLではインデックスのデータ構造にB-treeが採用されているようです。
ヘッダブロックでは大まかな値の範囲を保持しており、ブランチブロックではさらに細かい範囲を保持 リーフブロックでは実際の値と行への物理的な位置を保持しています。 INDEXが作成されている事で並び替えが速くなるのは、MySQLがこのINDEX順にレコードを表示すれば良いだけなので、 わざわざクイックソートで並び替えを行う事が無くなるため処理が高速になります。