MySQL インデックス物理構造

はじめに

MySQLでは、インデックスは B+Tree というアルゴリズムで構築されており、これによって効率的な検索が可能になっています。
この記事では、このインデックスの構造を上図をもとに詳述することを目的にします。

全体像

MySQLのインデックスはツリー構造で表現され、リーフノード、ノン・リーフノードからなります。

リーフノードには、このインデックスを用いた検索の結果取得したいデータが格納されており、またノン・リーフノードからリンクされています。図では下段が該当します。

これに対してノン・リーフノードにはデータが格納されておらず、リーフノードに中継する役割を果たします。図では上段が該当します。

図には2段しかありませんが、一般には多段構成のツリー上となっており、また、同レイヤーのノード間は互いに対するリンクを持ちます。これによって「隣のノード」へのアクセスを簡易にし、範囲検索の高速化が可能になっています。

インデックスを用いた検索がされる際には、ルートとなる最上段のノードのインデックス値と、検索したいキーとの比較が演算され、そのノードから出ているいずれかの枝が選択されます。そして次に選択されたノードでも同様の演算がなされ、最終的に行データが獲得されます。

インデックスがもつ情報

ここからは、インデックス構造の詳細を説明します。

ROW_ID

テーブルの行を示すユニークIDで、データ挿入時に生成され、単調増加していきます。

TRX_ID

該当行を挿入・更新したトランザクションのIDが格納されます。
分散レベルが Repeatable Read でもファントムリードを防ぐためのしくみ MVCC を実現するため、Undo ログとともに用いられます。

トランザクションが作られるたびに（おそらく）単調増加する値であるため、値の大きいほうが小さいほうより新しいトランザクションであることがわかります。
これがタイムスタンプのような役割をはたすことで、MVCC の実現を可能にします。

ROLL_PTR

これも TRX_ID と同じく MVCC で用いられます。
これには、以下の情報が含まれています。

• その行が挿入された行かどうか
• rollback segment（Undoログが格納されるテーブルスペース）の場所
• 該当するUndoログの、rollback segment 内のオフセット

Undo ログというのは、「更新前データ」を保持するしくみであり、これには rollback segment という専用のテーブルスペースが割り当てられています。

Undo ログは**「どのトランザクション」が更新したのかという情報を示す TRX_ID を、「更新前はどういうデータだったか」** という情報とともに保持され、Undoログ同士もチェーンのようにリンクされています。

これにより、複数世代の更新前データを保持しています。

そして、十分古くなったUndoログは、ガベージコレクションによって破棄されます。

KEY

このインデックスが対象としているカラムの名前やカラムタイプ

HEAP_NUMBER

該当のインデックス値が存在するヒープ番号

※ インデックスは各ノードが1ページになるため、各ノード16KBとなります。各ノードにはいくつかインデックスが含まれますが、それらの場所を示す番号のようです。1ページでおさまらないときにどうするのかはよくわかりません。

TYPE

クラスタ化インデックスか、セカンダリインデックスかなど、インデックスの種類を示す模様。

DELETED

削除処理がおこなわれた際にフラグが立ちます。

更新処理とおなじく、削除処理も処理前のデータを保持するしくみがあります。
削除処理をおこなっても物理削除はされず、インデックス上値は残ります。そして、削除処理をおこなったトランザクションIDを TRX_ID に書き込みます。

あるトランザクションがこのインデックス値を読み込もうとしたとき、その値の DELETED フラグがたっていて、かつ、自身のほうが新しいトランザクションであった（TRX_IDが大きかった）なら、その削除処理はそのトランザクションより過去におこなわれたものであるため、削除されたものとしてあつかいます。

逆に 削除処理をおこなったトランザクションのほうが、このインデックス値を読み込もうとしたトランザクションよりも新しかったのなら、DELETED フラグがたっていても、削除されたとはあつかわず、まだ rows 領域に削除されず残されているデータを読み込みます。

これによって、**「他トランザクションによる挿入・削除の影響を受ける」**というファントムが防止できます。

NEXT

次のインデックス値へのリンクです。

参考

https://dev.mysql.com/doc/refman/8.0/ja/innodb-undo-logs.html
https://dev.mysql.com/doc/refman/8.0/ja/optimizing-innodb-transaction-management.html
https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/
https://blog.jcole.us/2014/04/16/the-basics-of-the-innodb-undo-logging-and-history-system/