MySQL インデックスデータ構造の詳細な分析

概要

インデックスは、データベーステーブル内の 1 つ以上の列の値を並べ替える構造です。インデックスを使用すると、データベーステーブル内の特定の情報にすばやくアクセスできます。

インデックスデータ構造

バイナリツリー

二分木は、木内のノードの次数が 2 以下である順序付き木です。これは最も単純で最も重要な木です。二分木の再帰的な定義は次のとおりです。二分木は空の木、またはルートノードとルートの交差しない 2 つの左サブツリーと右サブツリーで構成される空でない木です。左サブツリーと右サブツリーも二分木です。

配列{1,2,3,4,5}の場合、データ構造はリンクリストになります。

特徴：

親ノードの下に 2 つの子ノードがあります。
右ノードのデータは左ノードのデータよりも大きいです。

バイナリツリー.png

赤黒木

赤黒木は、コンピュータサイエンスで数値などのデータブロックを整理するために使用される構造であるバイナリツリーの特定の種類です。二分探索木が赤黒木である場合、そのサブツリーのいずれも赤黒木でなければなりません。

赤黒木は、バランスのとれた二分探索木の変形です。左と右のサブツリーの高さの差が 1 より大きい場合があるため、赤黒木は厳密にバランスのとれた二分木 (AVL) ではありませんが、バランスをとるコストは低く、平均的な統計的パフォーマンスは AVL よりも強力です。

各赤黒木は二分ソート木であるため、赤黒木を検索する際には、通常の二分ソート木に適用される検索アルゴリズムを使用でき、検索プロセス中に色情報は必要ありません。

赤黒木のデータ構造は次のとおりです。

赤黒木データ構造.png

特徴：

赤黒木は、各ノードに赤または黒の色属性がある二分探索木です。
ノードは赤または黒です。
ルートノードは黒です。
葉っぱはすべて黒です。 (葉はNILノードです)
すべての赤いノードには 2 つの黒い子ノードがあります。 (各リーフからルートまでのパス上に連続する 2 つの赤いノードが存在することはできません)
任意のノードから各リーフへのすべてのパスには、同じ数の黒いノードが含まれます。
これらの制約は、赤黒木の重要な特性、つまりルートからリーフまでの最長パスが最短パスの 2 倍を超えないことを強制します。結果、ほぼバランスの取れた木が完成します。値の挿入、削除、検索などの操作には、最悪の場合、ツリーの高さに比例した時間が必要となるため、高さのこの理論的な上限により、通常の二分探索木とは異なり、赤黒木は最悪の場合でも効率的になります。
パス上に連続する 2 つの赤いノードが存在することはできないため、この結果を保証するのはプロパティ 4 です。最短のパスではノードはすべて黒色になり、最長のパスでは赤と黒のノードが交互に現れます。特性 5 により、すべての最長パスには同じ数の黒いノードがあるため、どのパスも他のパスの 2 倍以上長くなることはないことがわかります。
赤黒木は特殊な二分探索木であるため、赤黒木に対する読み取り専用操作は通常の二分探索木に対する操作と同じです。

Bツリー

リーフノードは同じ深さを持ち、リーフノードポインタは空です
すべての要素はユニークです
ノード内のデータインデックスは、左から右へ昇順に並べられます。

B ツリーデータ構造.png

B+ツリー

非リーフノードはデータを保存せず、インデックスのみ（冗長性）を保存し、より多くのインデックスを保存できます。
リーフノードにはすべてのインデックスフィールドが含まれます
リーフノードはポインタでリンクされており、区間アクセスのパフォーマンスが向上します（範囲検索の効率が向上します）。

B+ ツリーデータ構造.png

キーワード: ノード内の順序、リーフノードのポインタリンク、非リーフノードのストレージインデックス (冗長)

mysql インデックスのデータページのサイズを照会します。

mysql> 'Innodb_page_size' のようなグローバル ステータスを表示します。
+------------------+-------+
| 変数名 | 値 |
+------------------+-------+
| Innodb_ページサイズ | 16384 |
+------------------+-------+

なぜ16kbに設定するのですか?

ハッシュ

インデックスキーのハッシュ計算により、データストレージの場所を特定できます。
多くの場合、ハッシュインデックスは B+ ツリーインデックスよりも効率的です。
「=」のみがサポートされています。「in」は範囲クエリをサポートしていません。
ハッシュ競合の問題が発生しています

ハッシュデータ構造.png

索引

InnoDB インデックスの実装 (クラスタリング)

テーブルデータファイル自体はB+Treeで編成されたインデックス構造ファイルである。

クラスター化インデックス - リーフノードには完全なデータレコードが含まれます

InnoDb テーブルに主キーが必要なのはなぜですか? また、整数の自動増分主キーを使用することをお勧めしますか?

インデックスが設定されていない場合、MySQL は、そのような列が見つからないときに、一意のデータを持つ列を主キーインデックスとして選択します。私が行うことは、rowid のような隠し列を作成することです。
テーブルデータファイルは B+Tree データ構造に従って維持され、リーフノードは行のデータを維持します。したがって、主キーが存在する必要があります。
整数は B+ ツリーソートに便利です。整数が自己増加型の場合、多数のツリーバランス操作を必要とせずに、データ構造をより高速かつ連続的に格納できます。

非主キーインデックス構造のリーフノードに主キー値が格納されるのはなぜですか?

一貫性: 主キーインデックスを最初に成功させ、次に非主キーインデックスの関係を更新します。
ストレージスペースを節約します。

主キーインデックス図:

InnoDB インデックスの実装.png

非主キーインデックス図

クエリが name = Alice に基づいている場合:

非主キーインデックスを使用してクエリを実行し、クエリ後の情報 (Alice、18) を取得します。実はこれも非クラスタ化インデックスです
次に、バックテーブルクエリを実行し、主キーを使用してテーブルを再度クエリします。

2 つのデータファイル:

.frmは主にテーブル構造情報を保存します

.ibdは主にインデックスとデータを保存します

MyISAM インデックスファイル (非クラスター化)

インデックスファイルとデータファイルは別々です（非クラスター化）

MyISAM ストレージエンジンインデックス.png

3 つのデータファイル:

.frm データ構造ファイル

.mydファイルは主にデータを保存するために使用されます

.myiファイルは主にインデックス情報を保存します

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

特徴：

クラスタリング/非クラスタリングは、主にインデックスファイルがデータファイルと一緒にあるかどうかを指します。

クエリの効率性という点では、クラスター化インデックスはファイル間でクエリを行わないため、クエリが高速になります。

ジョイント/複合インデックス

複数のフィールドが共通のインデックスに整理される

結合されたインデックス.png

なぜこのように左端接頭辞の原則が使用されるのでしょうか?

インデックス化されたデータはソートされており、フィールドがスキップされている場合は使用できません。

例：

name = 'Jeff' かつ age = 22 の場合 -- インデックスにヒットします。 age = 30 かつ postatin='manager' の場合 -- インデックスにヒットしません。 postation = 'dev' の場合 -- インデックスにヒットしません。

参考文献

百度百科事典

要約する

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

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