MySQL 学習 (VII): Innodb ストレージエンジンインデックスの実装原理の詳細説明

概要

データベースでは、ツリーディレクトリと同様に、インデックスを使用してデータ検索を高速化します。SQL クエリ操作では、インデックスを使用して、要件を満たさないデータをすばやく除外し、要件を満たすデータを検索できるため、必要なデータを取得するためにテーブル全体をスキャンする必要がなくなります。

InnoDB ストレージエンジンでは、インデックスは主に B+ ツリーに基づいています。インデックスキーワードは非リーフノードに格納され、データレコードまたは主キーインデックス (またはクラスター化インデックス) 内の主キー値はリーフノードに格納されます。すべてのデータレコードは同じレイヤーにあり、リーフノード、つまりデータレコードはポインターによって直接接続されて双方向リンクリストを形成し、すべてのデータレコードまたは一定範囲のデータレコードを簡単にトラバースできます。

B ツリー、B+ ツリー

B ツリーと B+ ツリーはどちらも多方向バランス検索ツリーであり、各ノードにより多くのキーワードを格納し、回転と分割操作を通じてツリーのバランスを維持することでツリーの高さを削減し、データ取得のためのディスクアクセスの量を削減します。

B+ ツリーと B ツリーの主な違いは、B+ のリーフノードがポインター、具体的には二重リンクリストを介して前後に接続されているため、範囲検索を実行するのに非常に適していることです。詳細については以下を参照してください。

データ構造 - ツリー (III): 多方向検索ツリー B ツリー、B+ ツリー

InnoDB ストレージエンジンのクラスター化インデックスと非クラスター化インデックスは、B+ ツリーに基づいて実装されています。
主キーインデックス

InnoDB ストレージエンジンは、主キーインデックスをテーブルのクラスター化インデックスとして使用します。クラスター化インデックスの特徴は、非リーフノードが主キーを検索キーワードとして保存し、リーフノードが実際のデータレコード自体 (データページとも呼ばれます) を保存することです。データレコードは、キーワードの順序で左から右に保存されます。したがって、クラスター化インデックスは、実際にはデータを保存する方法です。したがって、各テーブルには 1 つのクラスター化インデックスしか設定できません。InnoDB ストレージエンジンのデータテーブルは、インデックス構成テーブルとも呼ばれます。構造は次のとおりです: (画像は「MySQL Technology Insider: Innodb Storage Engine」より)

クエリでは、主キーでデータを検索する場合、つまり、Explain Analysis SQL キーが PRIMARY を示している場合、リーフノードがデータレコード自体を格納するため、非クラスター化インデックスのようにデータレコードを取得するための追加のテーブルクエリ (主キーインデックス内) を必要とせず、直接返すことができるため、検索効率が最も高くなります。

次に、ORDER BYソート操作の場合、ASCかDESCかに関係なく、ORDER BY列が主キーであれば、主キーインデックスに対応するB+ツリーが順序付けられるため、ストレージエンジンから返されるデータはすでに主キーに従って順序付けられており、MySQLサーバーレベルでソートする必要がなく、パフォーマンスが向上します。explainを通じてSQLを分析し、extraがfilesortを使用していると表示された場合、それはMySQLサーバーレベルでソートが必要であることを意味します。このとき、一時テーブルまたは外部ファイルソートを使用する必要があるかもしれません。この場合、一般的には最適化する方法を見つける必要があります。

主キーに基づく範囲検索では、クラスター化インデックスのリーフノードが主キーの順序に従って双方向リンクリストで接続されるため、特定の範囲のデータレコードを素早く見つけることができます。

補助索引

補助インデックスはセカンダリインデックスとも呼ばれ、非クラスター化インデックスであり、通常は特定のクエリの効率を向上させるために設計されています。つまり、インデックス列を使用してクエリを実行する場合、補助インデックスは完全なテーブルスキャンを回避するために使用されます。補助インデックスはクラスター化インデックスではないため、各テーブルには次の構造を持つ複数の補助インデックスを含めることができます。

補助インデックスの非リーフノードにはインデックス列のキーワードが格納され、リーフノードには対応するクラスター化インデックス（または主キーインデックス）の主キー値が格納されます。つまり、補助インデックスを通じて必要なデータを検索した後、必要な列がインデックスでカバーできない場合、つまり、クエリに必要なすべてのデータ列を補助インデックス列を通じて取得するには、対応するクラスター化インデックスの主キー値を通じてクラスター化インデックス内の主キーを検索し、次に主キー値を通じてクラスター化インデックス内の対応するリーフページを見つけて、対応するデータレコードを取得する必要があります。したがって、全体のプロセスには、最初に補助インデックスを検索し、次にクラスター化インデックス (つまり、主キーインデックス) を検索するという 2 つのプロセスが含まれます (バックテーブルクエリ)。

例えば：

補助インデックスに対応する B+ ツリーの高さは 3 なので、リーフノードを見つけるには 3 回のディスク IO が必要です。リーフノードには、対応するクラスター化インデックスの主キー値が含まれます。
次に、リーフノードの対応するクラスター化インデックスの主キー値を通じて、クラスター化インデックス内の対応するデータレコードが検索されます。つまり、クラスター化インデックスに対応する B+ ツリーの高さも 3 の場合、クラスター化インデックスのリーフページを見つけて、リーフページの実際のデータレコードを取得するには、3 回のディスク IO も必要になります。

上記のプロセスには合計 6 つのディスク IO が必要です。したがって、クエリする必要があるデータの行数が多い場合、必要なディスク IO は指数関数的に増加し、クエリのパフォーマンスが低下します。したがって、フィルタリング度の高い列、つまり重複データの少ない列に補助インデックスを作成する必要があります。

カーディナリティ: インデックス列のデータの重複

上記の分析から、補助インデックスを介してクエリを実行する場合、テーブルをクエリして戻す必要があり、クエリするデータの行数が多いと、データを取得するために大量のディスク IO が必要になることがわかります。そのため、このインデックスはクエリのパフォーマンスを向上させるだけでなく、クエリのパフォーマンスを低下させます。さらに、MySQL オプティマイザが多数のデータ行を返す必要がある場合、インデックスの使用をあきらめて、直接フルテーブルスキャンを実行します。したがって、補助インデックスによって選択される列は重複の少ない列である必要があります。つまり、一般的なクエリの後に返される必要があるのは 1 行または 2 行のデータのみです。この列に重複する値が多すぎる場合は、この列にセカンダリインデックスを作成することをあきらめることを検討する必要があります。

具体的には、SHOW INDEX FROM を使用してカーディナリティ値を決定できます。

mysql> store_order からインデックスを表示します。
+---------------+-------------+-------------+--------------+--------------+-------------+-----------+---------+----------+----------+----------+---------------+
| テーブル | 非一意 | キー名 | インデックス内のシーケンス | 列名 | 照合 | カーディナリティ | サブパート | パック | Null | インデックス タイプ | コメント | インデックス コメント |
+---------------+-------------+-------------+--------------+--------------+-------------+-----------+---------+----------+----------+----------+---------------+
| store_order | 0 | PRIMARY | 1 | store_id | A | 201 | NULL | NULL | | BTREE | | |
| store_order | 1 | idx_expire | 1 | expire_date | A | 68 | NULL | NULL | YES | BTREE | | |
| store_order | 1 | idx_ul | 1 | ul | A | 22 | NULL | NULL | はい | BTREE | | |
+---------------+-------------+-------------+--------------+--------------+-------------+-----------+---------+----------+----------+----------+---------------+
セット内の 3 行 (0.01 秒)

カーディナリティは、インデックス列内の一意の値の推定数を示します。データ行数に近い場合、列内の重複値が少なく、列のフィルタリング性能が優れていることを意味します。差が大きすぎる場合、つまり、カーディナリティ/データ行の合計数の値が小さすぎる場合、たとえば、性別列に「男性」と「女性」の 2 つの値しか含まれていない場合は、列に多数の重複値があることを意味し、インデックスを削除するかどうかを検討する必要があります。

カバーインデックス

テーブルを返すクエリのオーバーヘッドは大きいため、テーブルを返すクエリの数を減らすために、結合インデックスを使用するなど、クエリに必要なすべての列を補助インデックスに追加することができます。このようにして、クエリに必要なすべてのデータを補助インデックスから取得できます（補助インデックスのリーフページには主キー値が含まれているため、インデックスに主キー値がなくても、主キー値とインデックス列のみを返す必要がある場合は、カバーリングインデックスが使用されます）。完全なデータ行をクエリするためにテーブルに戻る必要がないため、パフォーマンスが向上します。このメカニズムはカバーリングインデックスと呼ばれます。
explain を使用してクエリ SQL を分析する場合、extra に using index と表示される場合は、カバーリングインデックスを使用してデータが返され、クエリのパフォーマンスが高いことを意味します。
インデックスが存在すると、データ更新のオーバーヘッドが増加するため、つまり、データ行の追加や削除などのデータ更新を行う際には、対応する補助インデックスを更新する必要があります。そのため、具体的な設計では、両者の妥協点を見つける必要があります。

ジョイントインデックスは、一番左の前のスタンプと一致します

結合インデックスは、(a,b,c) などの複数の列をインデックスとして使用します。つまり、列 a、b、c がインデックスとして使用されます。B+ ツリーの特性により、インデックスは左端のフォワードシグマと一致する必要があるため、実際には 3 つのインデックス a、(a,b)、(a,b,c) を確立するのと同じです。
したがって、結合インデックスを設計するときは、カバーリングインデックスに最適化できるかどうかを考慮するだけでなく、複数の列の順序も考慮する必要があります。一般的な経験では、クエリ頻度が最も高く、フィルタリング能力が最も高い (重複値が少ない) 列が前、つまり左側に配置されます。

複合インデックス最適化ソート順

さらに、MySQL サーバーレベルでのソートを減らすために、ジョイントインデックスの使用を検討することもできます。たとえば、ユーザー注文テーブルには、ジョイントインデックス (user_id、buy_date) と単一列インデックス (user_id) が含まれています。(これはジョイントインデックスのデモンストレーションのみを目的としていることに注意してください。実際のプロジェクトでは、ジョイントインデックスのみが必要です。前述のように、(a,b) は 2 つのインデックス a と (a,b) に相当します。)

キー `idx_user_id` (`user_id`)、
キー `idx_user_id_buy_date` (`user_id`,`buy_date`)

ユーザーの注文をクエリするだけの場合、InnoDB は次のように user_id インデックスを使用します。

mysql> explain select user_id, order_id from t_order where user_id = 1;
+----+-------------+----------+-----------+---------+----------------------------------+------------+---------+-----------+------------+-------------+
| id | select_type | テーブル | パーティション | タイプ | 可能なキー | キー | キー長 | ref | 行 | フィルター済み | 追加 |
+----+-------------+----------+-----------+---------+----------------------------------+------------+---------+-----------+------------+-------------+
| 1 | SIMPLE | t_order | NULL | ref | idx_user_id、idx_user_id_buy_date | idx_user_id | 4 | const | 4 | 100.00 | インデックスを使用 |
+----+-------------+----------+-----------+---------+----------------------------------+------------+---------+-----------+------------+-------------+
セットに 1 行、警告 1 件 (0.00 秒)

ただし、購入日 buy_date に基づいてソートし、過去 3 日間のユーザーの購入記録を取得する必要がある場合は、単一列インデックス user_id と結合インデックス (user_id、buy_date) の両方を使用できます。buy_date はすでに結合インデックスでソートされているため、InnoDB は結合インデックスの使用を選択します。そのため、MySQL サーバーレベルで再度ソートする必要がなく、次のようにパフォーマンスが向上します。

mysql> explain select user_id, order_id from t_order where user_id = 1 order by buy_date limit 3;
+----+-------------+----------+-----------+--------+----------------------------------+------------------------+--------+--------+----------+---------------------------+
| id | select_type | テーブル | パーティション | タイプ | 可能なキー | キー | キー長 | ref | 行 | フィルター済み | 追加 |
+----+-------------+----------+-----------+--------+----------------------------------+------------------------+--------+--------+----------+---------------------------+
| 1 | SIMPLE | t_order | NULL | ref | idx_user_id、idx_user_id_buy_date | idx_user_id_buy_date | 4 | const | 4 | 100.00 | where を使用; index を使用 |
+----+-------------+----------+-----------+--------+----------------------------------+------------------------+--------+--------+----------+---------------------------+
セットに 1 行、警告 1 回 (0.01 秒)

結合インデックス idx_user_id_buy_date が削除されると、「Using filesort」が表示されます。

mysql> テーブル t_order を変更し、インデックス idx_user_id_buy_date を削除します。
クエリは正常、影響を受けた行は 0 行 (0.02 秒)
レコード: 0 重複: 0 警告: 0

mysql> explain select user_id, order_id from t_order where user_id = 1 order by buy_date limit 3;
+----+-------------+----------+-----------+--------+-------+-------+--------+---------+-----------------------------+-----+-------+---------+----------+-----------------------------+
| id | select_type | テーブル | パーティション | タイプ | 可能なキー | キー | キー長 | ref | 行 | フィルター済み | 追加 |
+----+-------------+----------+-----------+--------+-------+-------+--------+---------+-----------------------------+-----+-------+---------+----------+-----------------------------+
| 1 | SIMPLE | t_order | NULL | ALL | idx_user_id | NULL | NULL | NULL | 4 | 100.00 | where を使用; filesort を使用 |
+----+-------------+----------+-----------+--------+-------+-------+--------+---------+-----------------------------+-----+-------+---------+----------+-----------------------------+
セットに 1 行、警告 1 件 (0.00 秒)

上記は、編集者が紹介したInnodbストレージエンジンインデックスの実装の詳細な説明と統合です。皆様のお役に立てれば幸いです。ご質問がある場合は、メッセージを残してください。編集者がすぐに返信します。また、123WORDPRESS.COM ウェブサイトをサポートしてくださっている皆様にも感謝申し上げます。

以下もご興味があるかもしれません: