Mysql の B+Tree インデックス原理を深く理解する
- Guanhui転載
- 2020-04-28 14:57:113552ブラウズ
まず、適切なインデックスを正しく作成することが、データベース クエリのパフォーマンスを向上させるための基礎です。
インデックスとは何ですか?
インデックスは、テーブル内のデータ行の取得を高速化するために作成された分散ストレージ データ構造です。
インデックスはどのように機能しますか?
MYSQL データベースはインデックスのデータ構造として B TREE を使用するのはなぜですか?
データの取得を高速化するために、最初に思い浮かぶのは二分木ですが、二分木の検索時間の計算量は O(log2(n)) に達することがあります。二分木の記憶構造を見てみましょう。
##バランスのとれた二分探索ツリーは次のように定義されます: ノードの子ノード間の高さの差は 1 を超えることはできません。上図のノード20のように、左のノードの高さが1、右のノードの高さが0、差分が1なので、上図は定義に違反しない平衡二分木です。二分木のバランスを保つ方法には、左手演算、右手演算などがありますが、左手演算、右手演算に関しては、自分で関連する知識を探すことができます。
上図のバランス バイナリ ツリーが ID インデックスを保存する場合、ID = 8 のデータから開始し、まずルート ノードをメモリにロードし、8 と 10 を比較し、8 が10 より小さい場合は続行します。10 の左側のサブツリーをロードします。 5 をメモリにロードし、8 と 5 を比較します。同様に、ノード 5 の右側のサブツリーをロードします。この時点でヒットしたので、id 8 のインデックスに対応するデータがロードされることになります。
インデックスに対応するデータを見つけるにはどうすればよいですか?インデックスにデータを保存するには大きく2つの方法があり、1つ目はノードのデータ領域にid=8のロウデータの特定のデータ内容をすべて保存する方法です。別の方法では、データ領域には、データが実際に保存されるディスク アドレスが保存されます。
現時点では、バランスのとれたバイナリ ツリーが線形リンク リストの問題を解決します。データ クエリの効率は基本的に O(log2(n)) に達するので問題ないようです。では、なぜ MySQL はそのようなものを選択しないのでしょうか。データ構造?彼はどのような問題を抱えていますか?
問題 1: 検索効率の不足 一般に、ツリー構造では、データの深さによって検索時の IO 数が決まります。上の図に示すように、id = 8 のデータを検索するには 3 つの IO が必要です。データの量が数百万に達すると、その木の高さは恐ろしいものになります。
質問 2: クエリは不安定ではありません。クエリされたデータがルート ノードにある場合、必要な IO は 1 つだけです。リーフ ノードまたはブランチ ノードの場合、複数の IO が必要になります。
問題 3: ノードに保存されているデータの内容が少なすぎます。オペレーティング システムやディスク データ交換機能、またディスク IO の先読み機能もうまく活用できません。オペレーティング システムとディスク間のデータ交換はページ単位であるため、1 ページ = 4K、つまり、オペレーティング システムは IO ごとに 4K データをメモリにロードします。ただし、バイナリ ツリー内の各ノードの構造では、1 つのキーワード、1 つのデータ領域、および 2 つの子ノード参照のみが保存され、4K のコンテンツを満たすことはできません。幸いIO処理を頑張ったのですが、読み込まれたキーワードは1つだけで、ツリーの高さが高く、検索したキーワードがたまたま葉ノードや枝ノードにあった場合、検索に何回も時間がかかりました。キーワード。IO。
この二分木の問題を解決できる構造はあるのでしょうか?はい、多方向バランス検索ツリー: (バランス ツリー):
B ツリーは完全にバランスの取れたツリーであり、図に示すように、すべてのリーフ ノードが同じ高さにあります。次の図:
B Tree の利点は何ですか?また、B Tree によっていくつかの問題がどのように解決されますか?
まず定義を見てみましょう. 上の図は 2-3 ツリーを示しています (各ノードには 2 つのキーワードが格納され、3 つの方法があります). マルチウェイのバランスのとれた検索ツリーはマルチフォークを意味します。上記の図からわかるように、各ノードに保存されているキーワードの数とパスの数の関係は、
キーワードの数 = パスの数 – 1 となります。
上の図から ID = 28 のデータを検索するとします。B TREE の検索プロセスは次のとおりです:
まずルート ノードをメモリにロードし、次に 2 つのルート ノードをロードします。判定ルールは、
#上記のルールで28をヒットした後、28に相当するデータをロードし、28に相当するデータ領域を検索します。データ領域には、特定のデータまたはデータへのポインタが格納されます。
なぜこの構造がバランスの取れた二分木の問題を解決できるのでしょうか?
オペレーティング システムとディスクのインタラクティブな特性をうまく利用できます。ディスクの先読み機能をうまく活用するために、MYSQL はページ サイズを 16K に設定します。これはノード (ディスク ブロック) のサイズを設定するもので、16K なので、1 回の IO で 1 つのノード (16K) の内容がメモリにロードされます。ここで、キーワードの型を int、つまり 4 バイトと仮定します。各キーワードに対応するデータ領域も 4 バイトとすると、上図の各ノードは、子ノードの参照を考慮せずに、約 ( 16 * 1000) を格納できます。 ) / 8 = 2000 キーワードなので、合計 2001 通りあります。高さ 3 段階の 2 分木の場合、最大 7 個のキーワードを保存できますが、この 2001 個のパスを持つ B ツリーでは、高さ 3 段階で検索できるキーワードの数がはるかに多くなります。二分木。
B TREEではツリーのバランスを整える過程で、キーワードが変わるたびに構造が大きく変化するため、特に時間がかかるため、インデックスを作成する際には必ずインデックスを作成する必要があります。すべてのフィールドにインデックスを作成するのではなく、冗長なインデックスを作成しても、データの追加、削除、変更時にパフォーマンスの消費が増加するだけです。
B-tree は問題をうまく解決しているのに、なぜ MYSQL は依然として B-TREE を使用するのでしょうか?
まず B TREE がどのようなものかを見てみましょう. B TREE は B TREE のバリアントです. B ツリー種では、B ツリー種内のパスの数とキーワードの数の関係B TREE では、データ取得ルールは左閉区間を使用し、次の図に示すように、パスの数とキーの数の関係は 1:1 です。
#上図の場合 IDで作成したインデックスであり、id=1のデータを検索する場合、検索規則は次のようになります。 
#上記のルールに従えば、最終的にはリーフノードにデータがヒットすることになるので、リーフノードに従ってノード1のデータ領域から実データを取得します。
3. B TREE の葉ノードは順番に配置されており、隣接するノードは順番の参照関係にあり、上図のように葉ノード間はポインタで接続されています。
MYSQL はなぜ最終的に B TREE を選択するのでしょうか?
1. B TREE は B TREE の変形です。B TREE で解決できる問題は、B TREE でも解決できます (ツリーの高さを減らし、ノードに保存されるデータ量を増やします) ) 2. B TREE には強力なデータベースおよびテーブル スキャン機能があります。インデックスに基づいてデータ テーブルをスキャンしたい場合、B TREE のスキャンではツリー全体をスキャンする必要がありますが、B TREE ではすべてのツリーをスキャンするだけで済みます。それは葉ノードです (葉ノード間には参照があります)。3. B TREE はディスクの読み書き機能が強化されており、ルート ノードとサポート ノードはデータ領域を保存しません。ルート ノードとサポート ノードがすべて同じサイズの場合、保存されるキーワードの数が多くなります。 B TREEよりも多いです。リーフ ノードは子ノード参照を保存しません。したがって、B TREE は、B TREE よりも多くのディスクにロードされたキーワードの読み取りと書き込みを行います。
4. B TREE はソート機能が強い 上図からも分かるように、B TREE には当然ソート機能が備わっています。 5. B TREE クエリの効率がより安定しているため、データをクエリするたびに IO クエリの数が安定している必要があります。もちろん、これについての理解は人によって異なります。B TREE では、ルート ノードがヒットすると直接返されるため、確かにその方が効率的です。MYSQL B TREEの具体的な実装形式
ここでの主な説明は、異なる B TREE インデックス構造に基づく MYSQL の 2 つのストレージ エンジン (MYISAM と INNODB) の実装です。まず、MYSQL がデータを保存するフォルダーを見つけて、mysql がどのようにデータを保存するかを確認します。
このディレクトリを入力してください。すべてのデータベースはこのディレクトリに保存されているため、特定のデータベース ディレクトリを入力してください。ここでは、さまざまなデータ ストレージ エンジンがありますが、ここでは図に示すように、MYISAM と innodb について説明します:
MYISAM ストレージ エンジン インデックス:
図からわかるように、MYISAM ストレージ エンジンを使用してデータベース データを格納するファイルは合計 3 つあります:
Frm、テーブル定義ファイル。 MYD: データ ファイル。すべてのデータはこのファイルに保存されます。 MYI: インデックス ファイル。
MYISAM ストレージ エンジンでは、データとインデックスの関係は次のとおりです。
データを見つけるには? id = 101 のデータをクエリする場合は、まず MYI インデックス ファイルに基づいて id = 101 のノードを検索し (上図の左側を参照)、データを通じて実際にデータが保存されているディスク アドレスを取得します。このノードの領域を指定し、このアドレスを使用して MYD データ ファイルからデータを取得します (上の図の右側に示すように) 対応するレコードをロードします。
複数のインデックスがある場合、式は次のようになります。
つまり、MYISAM ストレージ エンジンでは、主キー インデックスと補助インデックスは次のとおりです。同じレベルであり、主キーインデックスはありません。
Innodb ストレージ エンジン:
まず、クラスター化インデックスの概念を見てみましょう。クラスター化インデックスは次のように定義されます: データベース テーブル行内のデータの物理的な順序は、キー値の論理順序と同じです。
Innodb は主キーをインデックスとして使用して、データ ストレージを集約および整理します。Innodb がデータをどのように整理するかを見てみましょう。
Innodb には、FRM ファイル (テーブル定義ファイル) と Ibd ファイルの 2 つのファイルしかなく、データを保存するための専用のファイルはありません。データは主キーを使用して集約および保存され、実際のデータはリーフ ノードに保存されます。 innodb の本来の設計意図は、主キーが最も重要なインデックスであるということです。具体的には下図のように
上図のようにリーフノードのデータ領域には実データが保存されており、インデックス経由で取得する場合は、リーフノードがヒットした場合、リーフノードから直接ロウデータを取得できます。 mysql5.5 バージョンより前は MYISAM エンジンが使用され、5.5 以降は innodb エンジンが使用されました。
innodb では、補助インデックスの形式は次の図のようになりますか?
#上記のように、主キー インデックスのリーフ ノードには実際のデータが格納されます。補助インデックスリーフノードのデータ領域には、主キーのインデックスキーの値が格納されます。検索プロセスは次のとおりです。名前 = 7 のデータをクエリする場合は、最初に補助インデックスでクエリを実行し、最後に主キー ID = 101 を見つけます。次に、主キー インデックスで ID 101 のデータを検索し、最後に取得します。主キーインデックスのリーフノードからの実データ。したがって、補助インデクスによる検索では、インデクスを 2 回検索する必要があります。
以下に示すように、Innodb と MYISAM の違いを図に示します。
インデックスを作成するためのいくつかの原則:
1.列の離散型:
離散型の計算式: count(distinctcol):count(col). 離散型が高いほど、選択型が優れています。
次の表の各フィールドで、どの列が最適な離散型を持つかを示します。
上の図から、離散型の列は明らかです。性別を使用してインデックスを作成する場合は、名前が最適です。
なぜ離散型が高いほど選択型が優れていると言われるのですか?
以下に示すように、Sex に関するインデックスを作成すると、インデックス構造は次のようになります。
このとき、sex = 1、ルートノードを判定した場合、結果は左のサブツリーを問い合わせることになりますが、左のサブツリーの2段目で判定した場合、左右の枝が両方とも条件を満たしているため、どちらのブランチを選択して検索を続行するか、または 2 つのブランチを結合するか判断するのが難しいため、ブランチは同時に検索されます。
2. 左端一致の原則
インデックス内のキーワードを比較する場合、比較は左から右に行う必要があり、スキップすることはできません。先ほど説明したidは全てint型のデータですが、idが文字列の場合は以下のようになります。
一致する場合、文字列は abc が 97 98 99 になるなどの ascll コードに変換され、左から右に文字ごとに比較されます。したがって、SQL クエリで like %a を使用する場合、% は完全一致を意味するため、インデックスは無効になります。完全一致がある場合、インデックスは必要ありません。テーブル全体を直接スキャンすることをお勧めします。
3. 最小スペースの原則
前に述べたように、キーワードが占めるスペースが小さい場合、各ノードに保存されるキーワードの数が多くなり、それぞれがメモリにロードされます。キーワードが多いほど検索効率が高くなります。
ジョイント インデックス:
単一列インデックス: ノード [名前] のキーワード
#ジョイント インデックス: ノード [名前、phoneNum]
単一列インデックスは特殊な結合インデックスとみなすことができ、結合インデックスの比較も左端の一致原則に基づいて行われます。
結合インデックス列を選択するための原則:
(1) よく使用される列の優先順位 (左端の一致原則)
(2) 離散性の高い列の優先順位 (離散性が高い原則)程度)
(3) 幅が小さい列の優先順位 (最小スペースの原則)
次に、よく発生する問題の簡単な例を示します。
例、通常、頻繁に使用されるクエリ SQL は次のとおりです:
Select * from users where name = ?
Select * from users where name = ? and pahoneNum = ?
取得を高速化するために、次のように上記のクエリ SQL のインデックスを作成します。
ユーザー(名前)にインデックス idx_name を作成します
users(name,phoneNum) にインデックス idx_name_phoneNum を作成します。
上記の解決策では、左端の一致原則に従って、idx_name は冗長インデックスです。ここで、name = ?インデックス idx_name_phoneNum も検索に使用できます。冗長インデックスは、B TREE バランスを維持するためのパフォーマンスの消費を増減させ、ディスク領域を占有します。
カバードインデックス:
クエリ対象の列をインデックス項目の情報を通じて直接返すことができる場合、そのインデックスは SQL クエリ用のカバーインデックスと呼ばれます。インデックスをカバーすると、クエリの効率が向上します。
以下、例を挙げてカバリングインデックスについて説明します。
テーブル: 教師
インデックス:PK(id)、キー(名前、電話番号)、一意(教師番号)
どれ次のSQLはカバリングインデックスを使用していますか?
Select TeacherNo = Teacher where TeacherNo = ?: 使用すると、TeacherNo を取得するときに、データ領域に入ることなく、インデックス内の TeacherNo 値を直接返すことができます。
Select id, TeacherNo from Teacher where TeacherNo = ?: 使用すると、補助インデックスのリーフ ノードはプライマリ インデックスの値を保存するため、補助インデックスのリーフ ノードがが取得された場合は、間の ID を返します。
先生からの名前、電話番号を選択 (TeacherNo = ?): 使用されていません
名前 = ? の先生から電話番号を選択、使用されています。
カバリング インデックスを理解すると、SQL で select * をできるだけ使用せず、クエリする特定のフィールドを指定する必要がある理由がわかります。理由の 1 つは、カバリング インデックスを使用するときに、入力する必要はありません。データ領域に入ると、データを直接返すことができるため、クエリの効率が向上します。
前の調査を通じて、次の結論を簡単に理解できます:
1. ビジネス ニーズを満たす場合、インデックス列のデータ長は可能な限り小さくてもかまいません。
2. テーブル内のインデックスが多いほど良いです。
3. Where 条件 (like 9%、like %9%、like%9) では、3 つのメソッドはインデックスを使用しません。後の 2 つの方法はインデックスには無効です。最初の 9% は不確実であり、列の離散型に依存します。結論として、それは使用できます。離散状況が特に悪いことが判明した場合、クエリ オプティマイザはインデックス クエリのパフォーマンスが低下していると判断しますが、そうではありません。フルテーブルスキャンと同様に優れています。
4. Where 条件の NOT IN にはインデックスを使用できません。
5. 指定したクエリをより頻繁に使用して必要な列のみを返し、select * の使用を減らします。
6. クエリ条件に関数を使用した場合、インデックスは無効になります。これは列の離散型に関係します。一度関数を使用すると、その関数は不確定になります。
7. 結合インデックスでは、インデックスの左端の列から検索を開始しないと、インデックスを使用できません。
8. ジョイント インデックスの場合、インデックスを使用して、左端の列と完全に一致し、別の列と範囲一致することができます。
9. 結合インデックスでは、クエリに特定の列の範囲クエリがある場合、その右側のすべての列はインデックスを使用できません。
推奨Mysqlチュートリアル「Mysqlチュートリアル」
以上がMysql の B+Tree インデックス原理を深く理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。