MySQL のインデックスを 1 つの記事で理解する

#インデックスとは

インデックスは、データ クエリの効率を向上させる機能を持つデータ構造です。 。よく使われる比喩は、本のカタログに喩えることです。目次を通じて、特定の章の内容が掲載されているページを正確に見つけることができます。

データ量が少ない場合にはインデックスを使用するのは実際には意味がありません。インデックスがなくても、データを 1 つずつ走査する必要がある場合でも、コンピュータにとってはそれほど時間はかかりません。データの量が大きくなると、通常の外部サービスを提供し、ユーザー エクスペリエンスを確保するために、インデックス作成が必要になります。

インデックス タイプ

インデックスはデータ構造であり、さまざまなシナリオに対処するために複数の実装があります。 MySQL では、主なものはハッシュ インデックスと B ツリーです。

ハッシュ インデックス

ハッシュ 誰もがよく知っていると思いますが、ハッシュはキーと値の形式のデータ構造です。実装は一般に配列連結リスト構造で、配列内のキーの位置をハッシュ関数で計算し、ハッシュ競合が発生した場合は連結リスト（ジッパー方式）で解決します。もちろん、ハッシュの競合を解決する他の方法もあります。ハッシュのデータ構造は非常に一般的に使用されており、たとえば、私たちのシステムはホットスポット データ キャッシュの構築に HashMap を使用しており、アクセス効率が非常に優れています。

ハッシュ構造にはデータが格納されます。まず、キーのハッシュ値が計算されて、配列内の位置が決定されます。競合がある場合は、配列の位置にリンク リストが構築されます。これには明らかにいくつかの問題があります。

同じ特性を持つキーの計算された位置であっても、遠く離れている可能性があり、連続的なクエリが非効率的になります。つまり、範囲クエリはサポートされていません。

ハッシュ インデックスには、計算されたハッシュ値と行ポインターが保存されますが、特定の行の値は保存されないため、ハッシュ インデックスを介してデータをクエリするには 2 つのクエリが必要です (最初に行の位置をクエリし、次に検索します)特定のデータ)

ハッシュ インデックス クエリ データの前提は、ハッシュ値を計算することです。そのためには、キーがデータの一部を正確に指すことができるキーである必要があるため、次のような一致クエリは実行されません。サポートされました。

つまり、ハッシュ インデックスはデータの特定の行をすばやく選択するのに適していることがわかります。

B ツリー構造

名前からして明らかにツリー構造で、大学ではデータ構造の教科書に必ず載っているツリー構造です。ツリー構造は、多くの場所で使用される特に重要なデータ構造です。

ハッシュ インデックスでは範囲クエリを実行できないと上で説明しましたが、ツリー構造には、順序付きクエリに便利な構造 (二分探索ツリー) もあります。二分探索ツリーの構造では、以下に示すように、親ノードの値が左の子ノードより大きく、右の子ノードより小さいことが必要です。上図のバイナリ ツリー クエリの時間計算量は O(log(n)) です。もちろん、O(log(n)) の時間計算量を確保するには、バイナリ ツリーのバランスが完全に保たれていることを確認する必要があります。回。

ツリー構造は MySQL インデックスでも使用されますが、バイナリ ツリーではありません。データベース内のデータは最終的にディスクに保存されるため、ツリーにノードが多すぎるとノード間の転送に時間がかかります。 MySQL の実装では、同じノードにより多くのコンテンツを配置し、同じノード上の操作をメモリに転送して、外部メモリ内のノード間の転送数を減らし、効率を向上させるという目的を達成します。これが B Tree ですが、B Tree の実装では、基本的に 3 層のツリー構造でほぼすべてのニーズを満たすことができます。

関連する推奨事項: 「

mysql データベースの知識の学習

」

B-Tree
まずは B Tree を理解するB ツリーを理解する必要があります。B ツリーはバランス ツリーです。ここでの B はバイナリではなくバランスを指します。より正確に言うと、B ツリーは多方向バランス検索ツリーです。

マルチパスバランス検索ツリーは次のとおりです。

これは 2 ～ 3 のツリーであり、各ノードが 2 つの値を格納することを意味します。同時に、ノードあたりのブランチの数は 3 です。上の図からわかるように、中間の構造はデータのクエリに非常に適しています。各ノードの左側のサブツリーの値は現在のノードの最小値より小さく、中央のサブツリーの値はすべて現在のノードの 2 つの値の中間にあり、右側のサブツリーはすべて現在のノードの最大値より大きくなります。

たとえば、値 24 を見つけたいとします。

(1) まず、ルート ノードから 24 がルート ノード (15, 25) の間にあると判断します。右側のサブツリーは除外され、中央から検索されます。

(2) 次に、中間サブツリーのルート ノード (18,22) を見つけます。比較すると、左側のサブツリーと中間サブツリーを除いたノードの最大値よりも 24 が大きいことがわかります。

(3) 正しいサブツリーを見つけ、ノードの最大値が 24 に正確に等しいと判断し、クエリは終了します。

上記のプロセスに基づいて、B ツリー検索を要約できます。

(1) ルート ノードから開始して、ノード内のキーワード (順序付けされた) シーケンスに対して二分検索を実行します。 。

(2) ヒットした場合は終了、そうでない場合はクエリキーワードが属する範囲の子ノードを入力します;

(3) 対応する子ノードが空になるか、すでに葉ノードになるまで上記のプロセスを繰り返します;

検索パフォーマンスは、キーワード セットで二分検索を実行するのと同等であることがわかります。ここからは、B ツリーには何の問題もないように見えますが、B ツリーの各ノードはインデックス キーとそれが表す特定の行データを格納することに注意する必要があります。 MySQL では、データベースのロード データはページ単位でロードされ、各ページのサイズは固定 (デフォルトは 16k) です。各ノードにすべての値が格納されている場合、ページに格納できるノードの数が非常に少なくなり、クエリによってメモリからデータが複数回読み込まれる可能性があり、パフォーマンスが低下します。

B ツリー

B ツリーは B ツリーのバリアントであり、外部ストレージ ファイルのインデックス作成により適しています。

両者の最大の違いは、B ツリーの各ノードがすべてのデータを格納するのに対し、B ツリーが格納する必要があるデータはすべてリーフ ノード上にあり、各ノードに順次アクセス ポインタが追加されることです。各ノードは、次に隣接するリーフ ノードを指すアドレスを持っています。この構造により、より多くのインデックス ノードを 1 つのメモリ ページに格納できるようになり、範囲クエリにより適しています。

インデックス

ストレージ エンジンはインデックスの実装を担当するため、次に説明するインデックスはすべて MySQL の InnoDB エンジンに基づいています。

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

クラスター化とは、データ行と隣接するキー値クラスターが一緒に格納されることを意味します。一部のデータベースでは、特定のインデックスをクラスター化インデックスとして選択できますが、InnoDB の実装では、主キー インデックスがクラスター化インデックスとして直接指定されます。主キーが定義されていない場合、InnoDB は主キー インデックスを置き換えるために一意の非 null インデックスを選択します。このようなインデックスが定義されていない場合、InnoDB は暗黙的に主キーをクラスター化インデックス (row_id) として定義します。

クラスター化インデックスの例を次の図に示します。

非クラスター化インデックスのインデックス

プライマリを除くInnoDB のキー インデックスを除いて、他のすべては非クラスター化インデックスであるため、非主キー インデックスとも呼ばれます。非主キー インデックスのリーフ ノードには、行の値ではなく、特定の行の主キー値が格納されます。クラスタリングの定義が満たされていません。

非クラスター化インデックスの例を図に示します。

クエリ時のクラスター化インデックスと非クラスター化インデックスの違い

上記の 2 つのインデックスの例の図から、クエリが主キー インデックスを介して行われる場合、データ行が直接クエリされて返されることがわかります。ただし、非主キー インデックスを通じてクエリを実行する場合は、まずインデックスを通じて主キーを決定し、次に取得した主キーを使用して主キー インデックスから特定の行のデータを検索する必要があります。取得した主キーを介して主キーインデックスからデータを取得することをテーブルに戻すといいます。

テーブルを返すプロセスでは、通常のインデックスを使用したクエリの方が主キー インデックスを使用したクエリよりも 1 段階手間がかかり、多くの場合、効率は比較的低くなります。したがって、クエリ プロセスで、主キーを通じてのみデータを特定できる場合は、主キーを使用して直接クエリを実行するのが最善です。

カバード インデックス

上記では、非主キー クエリを通じてテーブルを返すプロセスについて説明していますが、すべてのクエリにテーブルを返すプロセスがあるわけではないことに注意してください。まず、通常のインデックスの場合、そのリーフ ノードには主キーの値が格納されますが、現在必要なデータが主キーの値のみである場合はどうなるでしょうか?通常のインデックスで主キーの値を取得した後は、主キーインデックスで調べる必要がないため、テーブルに戻る処理がありません。

上記の例では、非主キー インデックスに必要な値がすでに含まれているため、このインデックスはカバー インデックスとも呼ばれます。カバー インデックスは固定構造ではありません。単一インデックス (1 つのフィールドのインデックス) または複合インデックスにすることができます。テーブルを返すプロセスを実行せずにクエリ結果を直接提供できるものはすべて、カバー インデックスと呼ぶことができます。

多くの場合、主キーだけでデータを判断することは不可能です。通常のインデックスを使用すると非効率につながる可能性があるため、インデックスをカバーすることは、日常の開発プロセスにおいて非常に一般的なパフォーマンス最適化方法でもあります。

もちろん、インデックス ページをカバーすることが常に良いことであるとは限りません。たとえば、ここではインデックス Index(a,b) を作成しました。 a と b の 2 つのフィールドを使用してインデックスを確立する利点は、ab フィールドをクエリするときにテーブルが返されないことですが、b フィールドのみを介してクエリを実行する場合、このインデックスは使用できません。作成されたインデックスのインデックス項目は、インデックス定義に出現するフィールドの順序に従ってソートされます。

左端の接頭辞の原則

インデックス インデックス (a, b) があると仮定します。a と b を介してクエリを実行すると、インデックスを適用できます。次を使用します。 a のみを使用してクエリをインデックスに適用することもできますが、b を単独でクエリに使用した場合、インデックスに適用することはできません。これは左端のプレフィックスの原則であり、インデックスを照合する場合、インデックスの左端の n フィールドが照合され、一致する場合はインデックスを適用できます。

左端の接頭辞の原則が存在するため、インデックスを構築する際にはさらに多くのことを考慮する必要がある場合があります。

まず第一に、インデックスはデータ構造であることを明確にする必要があります。インデックスを構築する際には、ストレージ領域が消費されます。したがって、インデックスの作成数が多ければ多いほど良いというわけではありません。代わりに、インデックスの数は多くなります。インデックスは、必要に応じて可能な限り削減する必要があります。

左端の接頭辞の原則の存在により、結合インデックスを複数のインデックスとして使用できます。もちろん、前提条件はインデックス内のフィールドの順序を設計することです (実際には、左端の接頭辞の原則はそうではありません) Union インデックスにのみ適用され、文字列インデックスにも使用されます。文字列インデックスの左端の n 文字は、Union インデックスの左端の n フィールドと同等です)。

たとえば、index(a,b) の場合、a に別のインデックスを作成する必要がないため、結合インデックスを設計するときは、通常、使用頻度の高いフィールドを最初に配置します。

次に、識別度の高いフィールドを前面に移動します。識別度は、フィールド内の値の繰り返し率です。繰り返し率が低いほど、識別度は高くなります。たとえば、性別はインデックスとしては適しておらず、区別性の高いフィールドでは 1 回のフィルターでさらに多くの行が除外される可能性があります。

次に、考慮する必要があるのはフィールドのサイズです。インデックスもスペースを占有する必要があるため、通常は小さいフィールドが選択されます。

参考資料

MySQL の運用とメンテナンスの内部リファレンス: MySQL、Galera、Inception の中心原則とベスト プラクティス

以上がMySQL のインデックスを 1 つの記事で理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。