通常MySQLのインデックスはB+木と呼ばれる構造に格納される。

インデックスには、クラスタインデックスと呼ばれる特別なものと、それ以外のセカンダリインデックスがある。

クラスタインデックスはMySQLのデータ構造そのもので、リーフノードにはテーブルの実データが格納される。
セカンダリインデックスはリーフノードにクラスタインデックスを参照するためのキーが格納される。

B+木

2分探索木の1種で、ルートノードから、データが格納されるリーフノードまでの距離が等しくなる。
リーフノード内のデータはキーで整列しており、リーフノード同士もリンクで連結されている。

クラスタインデックス

テーブルに必ず一つ作成される。リーフノードにはテーブルの実データが格納される。

通常 Primary key がクラスタインデックスになる。Primary key がテーブルに作成されない場合、Unique key (全てのカラムがNOT NULLである必要がある), それも無い場合は非表示の行IDを格納するカラムの値を使ってクラスタインデックスが作成される。

末端のノード (リーフノード) はページと呼ばれ、既定で16KBの固定長サイズの領域で、テーブルの実データが格納される。

クラスタインデックス以外の通常のインデックス。

セカンダリインデックスは任意のカラムを使って構築出来る。クラスタインデックスと同様にB+木の構造に格納されるが、指定された任意のカラムの値を使ってツリー構造が作成される。
また、セカンダリインデックスのリーフノードには、クラスタインデックスを検索するためのキー (通常はPK) が格納される。