MySQLインデックスの基礎となるデータ構造の詳細

1. インデックスの種類

1. B+ツリー

なぜ B ツリーではなく B+ ツリーなのでしょうか?

まず、B ツリーと B+ ツリーの構造上の違いを見てみましょう。

Bツリー構造:

B+ツリー:

以下が見られます:

• B ツリーでは各ノードにサテライト データ (データ テーブル内のデータ行) がありますが、B+ ツリーではリーフ ノードにのみサテライト データがあります。これは、同じサイズのディスクセクターの場合、B+ツリーはより多くのリーフノードを格納でき、必要なディスクIO時間が短くなることを意味します。また、B+ツリーの検索効率はより安定しており、Bツリーデータクエリの最速の時間計算量はO(1)であることを意味します。
• B ツリーの各ノードは 1 回だけ表示され、B+ ツリーのすべてのノードはリーフ ノードに表示されます。 B+ ツリーのすべてのリーフ ノードは昇順のリンク リストを形成します。これは間隔範囲の検索に適していますが、B ツリーは適していません。
  

2. MyISAM と InnoDB の B+ ツリー インデックス実装 (クラスター化インデックスと非クラスター化インデックス) の違いは何ですか?

まず、クラスター化インデックスと非クラスター化インデックスを理解する必要があります。

クラスター化インデックス:

クラスター化インデックスでは、リーフ ページに行のすべてのデータが含まれ、ノード ページにはインデックス列が含まれます。 InnoDB は主キーによってデータをクラスター化します。主キーが定義されていない場合は、代わりに一意の空でないインデックス列が選択されます。そのようなインデックスがない場合、InnoDB は暗黙的に主キーをクラスター化インデックスとして定義します。

クラスター化インデックスのデータ分布:

クラスター化インデックスには、主キー インデックスに加えて、セカンダリ インデックスもあります。セカンダリ インデックスのリーフ ノードには、「行ポインタ」ではなく、行への「ポインタ」として使用される主キー値が格納されます。つまり、セカンダリ インデックスを通じて行を検索する場合、ストレージ エンジンはセカンダリ インデックスのリーフ ノードを見つけて対応するプライマリ キー値を取得し、この値に基づいてクラスター化インデックス内の対応する行を検索する必要があります。これは、「テーブルに戻る」とも呼ばれます。もちろん、カバーリング インデックスやInnoDBのアダプティブ インデックスを使用してテーブルの繰り返しを回避し、このような繰り返し作業を減らすこともできます。

注: クラスター化インデックスの各リーフ ノードには、完全なデータ行だけでなく、トランザクション ID、トランザクションのロールバック ポインター、および MVCC も含まれます。

3. 非クラスター化インデックス

非クラスター化インデックスの主キー インデックスとセカンダリ インデックスは構造に違いはなく、どちらもリーフ ノード上のデータの物理アドレスを指す「行ポインター」を格納します。

クラスター化インデックスの主キー インデックスとセカンダリ インデックス:

非クラスター化インデックスの主キー インデックスとセカンダリ インデックス:

4. クラスター化インデックスの利点と欠点

アドバンテージ：

関連データをまとめて保存します（たとえば、すべてのユーザーのメールをユーザーIDごとにグループ化します）。そうしないと、各データの読み取りでディスクIOが発生する可能性があります。
データ アクセスが高速化します。インデックスとデータを同じ B+ ツリーに格納します。通常、クラスター化インデックスからデータを取得する方が、非クラスター化インデックスからデータを取得するよりも高速です。カバーリング クエリを使用すると、ページ ノードの主キー値を直接使用できます。

欠点:

すべてのデータをメモリに格納できる場合、シーケンシャル アクセスは不要になり、クラスター化インデックスの利点はなくなります。挿入速度は挿入順序によって異なります。ランダム挿入はページ分割やページ ホールの原因になります。OPTIMIZE TABLE を使用してテーブルを再構築します。挿入、更新、削除のたびにインデックス変更のメンテナンスが必要になり、コストが非常に高くなります。参照行の主キー列がノードに含まれるため、セカンダリ インデックスが予想よりも大きくなる場合があります。

5. ハッシュインデックス

ハッシュ インデックスはハッシュ テーブルに基づいて実装されます。インデックスのすべての列と完全に一致するクエリのみが有効であるため、ハッシュ インデックスは等価値クエリに適しています。

具体的な実装:データの各行について、ストレージ エンジンはすべてのインデックス列のハッシュ コードを計算します。ハッシュ インデックスはすべてのハッシュ コードをインデックスに格納し、各データ行へのポインターをハッシュ テーブルに保存します。

MySQL では、 Memoryエンジンは B ツリー インデックスもサポートしていますが、ハッシュ インデックスを明示的にサポートしているのはMemoryエンジンだけです。

注:メモリ エンジンは、一意でないハッシュ インデックスをサポートします。競合を解決するには、同じハッシュ値を持つ複数のレコード ポインターをリンク リストの形式で保存します。

6. 適応ハッシュインデックス

InnoDB 、特定のインデックス値が非常に頻繁に使用されていることに気付くと、メモリ内に B+ ツリー インデックスに基づくハッシュ インデックスを作成します。これにより、B+ ツリー インデックスにも、高速なハッシュ検索など、ハッシュ インデックスのいくつかの利点が備わります。

MySQL インデックスの基礎となるデータ構造の詳細に関するこの記事はこれで終わりです。MySQL インデックスの基礎となるデータ構造の詳細については、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。