MySQL インデックスのデータ構造とアルゴリズム: インデックスの実装

MyISAM インデックスの実装

MyISAM エンジンはインデックス構造として B+Tree を使用し、リーフノードのデータフィールドにデータレコードのアドレスを格納します。次の図は、MyISAM インデックスの概略図です。

図8

ここでは、テーブルに合計 3 つの列があると仮定します。Col1 が主キーであると仮定すると、図 8 は MyISAM テーブルのプライマリインデックス (主キー) の図になります。 MyISAM インデックスファイルには、データレコードのアドレスのみが保存されていることがわかります。 MyISAM では、プライマリインデックスとセカンダリインデックス (セカンダリキー) の間に構造上の違いはありませんが、プライマリインデックスではキーが一意である必要があるのに対し、セカンダリインデックスキーは繰り返すことができます。 Col2 にセカンダリインデックスを作成すると、このインデックスの構造は次のようになります。

図9

これも B+ ツリーであり、データフィールドにはデータレコードのアドレスが格納されます。したがって、 MyISAM のインデックス検索アルゴリズムは、まず B+Tree 検索アルゴリズムに従ってインデックスを検索します。指定されたキーが存在する場合は、そのデータフィールドの値が取り出され、次にデータフィールドの値をアドレスとして使用して対応するデータレコードが読み取られます。

MyISAM インデックス方式は「非クラスター化」とも呼ばれ、InnoDB のクラスター化インデックスと区別するためにこのように呼ばれています。

#p#

InnoDB インデックスの実装

InnoDB もインデックス構造として B+Tree を使用しますが、その具体的な実装は MyISAM とはまったく異なります。

最初の大きな違いは、InnoDB のデータファイル自体がインデックスファイルであることです。上記から、MyISAM インデックスファイルとデータファイルは別々であり、インデックスファイルにはデータレコードのアドレスのみが保存されることがわかります。 InnoDB では、テーブルデータファイル自体が B+ ツリーとして編成されたインデックス構造であり、このツリーのリーフノードデータフィールドに完全なデータレコードが格納されます。このインデックスのキーはデータテーブルの主キーであるため、InnoDB テーブルデータファイル自体が主インデックスになります。

図10

図 10 は、InnoDB プライマリインデックス (データファイルでもある) の概略図です。リーフノードには完全なデータレコードが含まれていることがわかります。このタイプのインデックスはクラスター化インデックスと呼ばれます。 InnoDB のデータファイル自体は主キーによってクラスター化されているため、InnoDB ではテーブルに主キーが必要です (MyISAM には主キーがない場合があります)。明示的に指定されていない場合、MySQL システムはデータレコードを一意に識別できる列を主キーとして自動的に選択します。そのような列が存在しない場合、MySQL は InnoDB テーブルの暗黙的なフィールドを主キーとして自動的に生成します。このフィールドは 6 バイト長で、長整数型です。

MyISAM インデックスとの 2 番目の違いは、InnoDB 補助インデックスデータフィールドに、アドレスではなく、対応するレコードの主キーの値が格納されることです。つまり、InnoDB のすべてのセカンダリインデックスは、データフィールドとしてプライマリキーを参照します。たとえば、図 11 は Col3 に定義された補助インデックスを示しています。

図11

ここでは、英語文字の ASCII コードを比較基準として使用します。クラスター化インデックスの実装により、主キーによる検索は非常に効率的になりますが、補助インデックス検索には 2 つのインデックス検索が必要です。最初に補助インデックスを検索して主キーを取得し、次に主キーを使用して主インデックスからレコードを取得します。

さまざまなストレージエンジンのインデックス実装方法を理解することは、インデックスを正しく使用して最適化するのに非常に役立ちます。たとえば、InnoDB のインデックス実装を理解すれば、長すぎるフィールドを主キーとして使用することが推奨されない理由を簡単に理解できます。これは、すべてのセカンダリインデックスがプライマリインデックスを参照し、プライマリインデックスが長すぎるとセカンダリインデックスが大きくなりすぎるためです。別の例として、InnoDB データファイル自体が B+Tree であるため、InnoDB の主キーとして非単調フィールドを使用することはお勧めできません。非単調な主キーでは、B+Tree の特性を維持するために、新しいレコードを挿入するときにデータファイルが頻繁に分割および調整されるため、非常に非効率的です。自動増分フィールドを主キーとして使用するのは良い選択です。

次の章では、これらのインデックス関連の最適化戦略について詳しく説明します。

オリジナルリンク: http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html

【編集者のおすすめ】