MySQLの仕組み

mysql, インフラ, データベース, 開発B-tree, index, 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順にレコードを表示すれば良いだけなので、 わざわざクイックソートで並び替えを行う事が無くなるため処理が高速になります。