データベースインデックスの役割

データベース インデックスの最大の役割は、クエリを高速化することです。これにより、スキャンする必要があるレコード行の数を根本的に減らすことができます。データベース インデックスは、データベースのデータ構造です。さらに、データ構造テーブル内の列のすべての値を保存します。つまり、インデックスはデータ テーブル内の列に基づいて作成されます。

データベース インデックスは、クエリ速度を向上させるためにテーブル フィールドに付加される識別子です。多くの人がインデックスの概念を機械的に理解し、インデックスを追加することはメリットだけで害はないと考えているのを見てきました。ここで、以前のインデックスの研究メモを要約したいと思います:

まず、インデックスによって速度が向上する理由を理解してください。DB が SQL ステートメントを実行するとき、デフォルトの方法は、検索に基づいてフル テーブル スキャンを実行することです。条件に一致し、一致する条件が見つかった場合に検索結果コレクションに追加されます。特定のフィールドにインデックスを追加すると、クエリを実行するときに、最初にインデックス リスト内の特定の値を持つ行の数が検索されます。これにより、走査される一致する行の数が大幅に減少するため、クエリの速度が大幅に向上します。それでは、いつでもインデックスを追加する必要があるのでしょうか?反例をいくつか示します。 1. 毎回すべてのテーブル レコードを取得する必要があり、とにかくテーブル全体のスキャンを実行する必要がある場合、インデックスを追加する意味はありません。 2. 「性別」など、多数の値が繰り返される一意でないフィールドの場合、インデックスを追加しても意味がありません。 3. レコードが比較的少ないテーブルの場合、インデックスを追加しても速度は最適化されず、ストレージ スペースが無駄になります。インデックスにはストレージ スペースが必要であり、更新/挿入/削除を実行するたびにフィールド「すべてのインデックス」が必要になるという致命的な欠点があります。更新のために再計算されます。

それでは、インデックスを追加するのはどのような場合が適切なのでしょうか? Mysql マニュアルに記載されている例を見てみましょう SQL ステートメントは次のとおりです:

SELECT c.companyID, c.companyName FROM Companies c, User u WHERE c.companyID = u.fk_companyID AND c.numEmployees > ; = 0 AND c.companyName LIKE '%i%' AND u.groupID IN (SELECT g.groupID FROM Groups g WHERE g.groupLabel = 'Executive')

このステートメントには 3 つのテーブルの結合が含まれます。サイズ比較やいいね一致などの検索条件も豊富です。 Mysql がインデックスなしで実行する必要があるスキャン行の数は 77721876 行です。 companyID フィールドと groupLabel フィールドにインデックスを追加すると、スキャンされた行の数は 134 行のみになります。 Mysql では、Explain Select を通じてスキャンの数を表示できます。このような結合テーブルと複雑な検索条件の場合、インデックスによってもたらされるパフォーマンスの向上は、インデックスが占有するディスク領域よりもはるかに重要であることがわかります。

それでは、インデックスはどのように実装されるのでしょうか?ほとんどの DB ベンダーは、データ構造 (B ツリー) に基づいてインデックスを実装しています。 B ツリーの特徴は、ディスクなどの直接記憶装置上で動的ルックアップ テーブルを編成するのに適しているためです。 B ツリーの定義は次のとおりです。 次数 m(m>=3) の B ツリーは、次の条件を満たす m 分ツリーです。

1. 各ノードには次のスコープが含まれます ( j, p0 , k1, p1, k2, p2, ... ki, pi) ここで、j はキーワードの数、p は子ポインター

2. すべてのリーフ ノードは同じレイヤー上にあり、層の数は木の高さに等しい h

3. 各非ルート ノードに含まれるキーワードの数は、[m/2-1]## 4. ツリーが空でない場合、ルートには少なくとも 1 つのキーワードがあります。ルートが葉ではない場合、少なくとも 2 つのサブツリー、最大で m 個のサブツリーがあります。

見てください。 B ツリーの例。26 個の英語文字を含む B ツリーの場合、次の構造で実行できます:

この B ツリーで英語の文字を検索する複雑さはわずか O(m) であることがわかり、データ量が比較的大きい場合、このような構造によりクエリ速度が大幅に向上します。ただし、B ツリーよりも高速にクエリを実行する別のデータ構造、ハッシュ テーブルがあります。ハッシュ テーブルの定義は次のとおりです。考えられるすべてのキーワードのセットを u とし、実際に格納されているキーワードを k で示し、|k| は |u| よりもはるかに小さくなります。ハッシュ方法は、ハッシュ関数 h を介して u をテーブル T[0,m-1] の添字にマップすることで、u 内のキーワードが変数になり、h との関数演算の結果がストレージ アドレスになります。対応するノード。したがって、検索は O(1) 時間で完了できます。
ただし、ハッシュ テーブルにはハッシュの競合という欠陥があります。つまり、2 つのキーワードがハッシュ関数を通じて同じ結果を計算します。 m と n をそれぞれハッシュ テーブルの長さと満たされたノードの数を表すとします。n/m はハッシュ テーブルの充填係数です。係数が大きいほど、ハッシュ競合の可能性が高くなります。
この欠陥のため、データベースはインデックスのデフォルト実装としてハッシュ テーブルを使用しません。Mysql は、ディスクベースの B ツリー インデックスを、実行クエリ形式に従って適切なハッシュ インデックスに変換しようとすると主張しています。さらなる進化を追求するため、検索速度を向上させます。他のデータベースベンダーも同様の戦略をとっていると思いますが、やはりデータベースの戦場では、検索速度と管理の安全性が非常に重要な競争ポイントとなります。

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