最後に、MySQL インデックスは B+tree を使用する必要があり、それが非常に高速であることを理解しました。

mysql チュートリアル 列では、インデックスを理解するための B ツリーを紹介します。

無料の推奨事項: mysql チュートリアル(ビデオ)

はじめに

遅い SQL に遭遇し、それを最適化する必要がある場合、すぐにどのような最適化方法を思いつくでしょうか?

ほとんどの人の最初の反応は、インデックスの追加でしょう。ほとんどの場合、index で SQL ステートメントにクエリを追加できます。効率は次のとおりです。数 桁 改善されました。

インデックスの本質: レコードを迅速に検索するために使用される データ構造。

一般的に使用されるインデックスデータ構造:

1. バイナリ ツリー
2. 赤黒ツリー
3. ハッシュ テーブル
4. B-tree (B ツリーは B マイナス ツリーとは呼ばれません)
5. B ツリー

データ構造グラフィカルWebサイト: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

インデックス クエリ

誰もが知っているselect * from t where Col = 88 このような SQL ステートメントがインデックスを使用せずに検索される場合、通常の検索は full table scan: テーブルの最初の行から開始して行ごとに検索します。各行の col フィールドの値を 88 と比較すると、これは明らかに非常に非効率的です。

また、インデックスを使用する場合、クエリ プロセスは完全に異なります (インデックス列の格納に バランス バイナリ ツリー データ構造が使用されていると仮定します) )

このときのバイナリツリーの格納構造 (Key - Value): Key はインデックスフィールドのデータ、Value はインデックスが配置されている行のディスクファイルアドレスです。

最終的に 88 が見つかったら、その値に対応するディスク ファイル アドレスを取り出し、ディスクに直接アクセスしてこのデータ行を見つけます。フルテーブルスキャンよりもはるかに高速になります。

しかし実際には MySQL 最下層はインデックス データの保存に バイナリ ツリーを使用しません。 Bツリー(Bツリー)を使用します。

バイナリ ツリーを使用しない理由

通常のバイナリ ツリーを使用して id インデックス列を記録すると仮定すると、レコードの列。

このとき、id ​​= 7 のデータを探したい場合、検索処理は次のようになります。

この時点では、行

id ​​= 7

7 回検索しましたが、これはテーブル全体のスキャンとあまり変わりません。明らかに、バイナリ ツリーは実際には、この 増加する データ列のインデックスとして 不適切なデータ構造です。 ハッシュ テーブルを使用しない理由

ハッシュ テーブル: 高速検索のためのデータ構造、検索の時間計算量は O(1)

ハッシュ関数: 変換a 任意のタイプのキーを int タイプの添字に変換できます。

ハッシュ テーブルを使用して

id

インデックス列を記録すると仮定して、レコードの行を同時にハッシュ テーブルのインデックス フィールドを保守します。

現時点では、id ​​= 7

のツリー ノードは

1 回のみ検索されており、非常に効率的です。

しかし、MySQL

のインデックスは依然として、正確に配置できる

ハッシュ テーブルを使用していません。 は 範囲クエリ に適用されないためです。 赤黒ツリーを使用しない理由赤黒ツリーは特殊な AVL ツリー (バランス バイナリ ツリー) であり、挿入および削除操作中の特定の操作を通じて維持されます。二分探索ツリーのバランス;

二分探索ツリーが赤黒ツリーの場合、そのサブツリーのいずれも赤黒ツリーでなければなりません。

この時点で赤黒ツリー レコード id インデックス列が使用されると仮定すると、レコードの行を挿入する間、赤黒ツリー インデックス フィールドを維持する必要があります。

挿入プロセス中に、ツリーの左右のサブツリー間の高さの差が 1 より大きい場合、通常のバイナリ ツリーとは異なることがわかります。 スピン オペレーションを実行して、ツリーのバランスを保ちます。

このとき、id ​​= 7 のツリーノードは 3 回しか検索されず、いわゆる通常の二分木よりも高速です。

しかし、MySQL のインデックスは、正確な位置決めと範囲クエリに優れた をまだ使用していません red-黒い木＃＃＃。 MySQL

データ量が大きい場合、インデックスのサイズも非常に大きくなり、メモリに格納できない可能性があるため、関連する読み取りと書き込みが必要になります。ツリー レベルが大きすぎる場合 ツリー レベルが高いと、ディスクの読み取りおよび書き込み (I/O インタラクション) の数が多くなり、パフォーマンスが低下します。

B ツリー

赤黒ツリーの唯一の欠点は、木の高さが制御できないことです。そのため、

エントリ ポイント

は

の木の高さは です。 現在、ノードは 1 つの要素を格納するためにのみ割り当てられています。高さを制御したい場合は、より大きなスペースをノードに割り当て、 で複数の要素を水平方向に格納できるようにすることができます

今回は高さが制御可能です。このような変革のプロセスを経て、

B-tree になりました。

B-tree

は、完全にバランスの取れたマルチウェイ ツリーです。その構造には 2 つの概念があります。 次数: ノードが持つ子ノード (サブツリー) の数。 (場所によっては

B-tree の説明に degree

を使用します。ここで説明します)

Order: ノードの子ノードの最大数。 (通常は m で表されます) キーワード: データ インデックス。

m 次 B ツリー

は、平衡型 m 方向探索ツリーです。これは空のツリーであるか、次の特性を満たす可能性があります:

ルート ノードとリーフ ノードを除き、他の各ノードには少なくとも ## があります。

1. #⌈##m$⌈$

   $\lceil {\displaystyle \#\#m\frac{2}{\mathrm{}}\rceil }\backslash lceil\; \backslash dfrac\{m\}\{2\}\backslash rceil$#各非ルート ノードに含まれるキーワード j の数は、次の条件を満たします。

2. ⌈$2{\displaystyle \frac{\rceil }{\mathrm{}}}\#\lceil$

   名前の意味 (本題から外れます、リラックスしてください)

3. 以下は Wikipedia からの抜粋です

4. ルドルフ バイエル (ルドルフ・バイエルとエド・M・マクレイトは、ボーイング研究所で働いていた1972年に

   Bツリー

   を発明しましたが、Bが（もしあれば）どのような意味を表しているのかについては説明していませんでした。

Douglas Comer は次のように説明しています: どちらの著者も

B ツリー

の本来の意味を説明していません。バランスが取れていて、幅が広く、茂みのあるものが適していると感じるかもしれません。文字Bはボーイングを表していると主張する人もいた。ただし、彼のスポンサーシップにより、

B-tree はバイエル ツリーと考える方が適切であると思われます。

Donald Knuth は、1980 年 5 月に発表された「ディスク ストレージと B ツリーに関する CS144C 教室講義」というタイトルの論文で

B ツリー について推測しました。名前の解釈では、B がボーイングまたは B を意味する可能性があることを示唆しています。バイエル社の名前。

検索

B ツリー の検索は、実際には二分木と非常によく似ています。

二分木にはキーワードと 2 つの分岐があります。各ノード

B-tree 上の各ノードには k 個のキーワードと (k 1) 個の分岐があります。

二分木の検索では左に行くか右に行くかだけが考慮されますが、

B-tree

は複数の分岐によって決定する必要があります。

B-tree

の検索は 2 つのステップに分かれています:

1. 最初にノードを見つけます。B ツリー は通常ディスクに保存されているため、この手順では ディスク IO 操作が必要です。
2. キーを見つけますつまり、ノードが見つかると、ノード がメモリ に読み込まれ、逐次検索または二分探索によってキーワードが検索されます。キーワードが見つからない場合は、サイズを判断して適切なブランチを見つけて検索を続ける必要があります。

#操作プロセス

次に、要素: 88

初回: ディスク IO

を見つける必要があります。 ## 2 回目: Disk IO

3 回目: Disk IO

次にメモリ比較があり、それぞれ 70 と 88 と比較されます。 、そして最終的に88が見つかりました。

検索プロセスから、

B-tree の比較数とディスク IO 数は実際には比較数とそれほど変わらないことがわかりました。バイナリツリー、違いはないようですが、どのようなメリットがあるのでしょうか。

しかし、詳しく見てみると、比較はメモリ内で完了し、ディスク IO を必要とせず、時間の消費も無視できることがわかります。

さらに、

B-tree は、1 つのノードに多数の キーワード (順序によって数が決まります) を格納することができ、同じ数の キーワードを格納できます。 B-tree で生成されるノードはバイナリ ツリーのノードに比べてはるかに少なく、ノード数の差はディスク IO の数に相当します。一定の数値に達すると、パフォーマンスの差が顕著になります。

挿入

B-tree がキーワードを挿入したい場合、葉ノードを直接見つけて操作を実行します。

挿入する
1. keyword に従って、挿入するリーフ ノードを見つけます。
ノードの子ノードの最大数 (順序) は次のとおりです。 m であるため、現在のノード
2. 内のキーワード の数が (m - 1) 未満であるかどうかを判断する必要があります。
   はい: 直接挿入
   • いいえ:
   • ノード分割が発生します。ノードは、ノードの中央のキーワードと中央のキーワードに基づいて左右の部分に分割されますが配置されている場合は、親ノードに移動するだけです。

操作プロセス

たとえば、最大次数 (次数) の要素を

B ツリー に挿入する必要があります。 3: 72

1. 挿入するリーフ ノードを見つけます

   

2. ノード分割: である必要があります。 [70,88] 同じディスク ブロック上ですが、ノードに 3 つのキーワードがある場合、そのノードには 4 つの子ノードがある可能性があり、定義した制限の最大次数 3 を超えるため、この時点で

   split## を実行する必要があります。 time #: 真ん中のキーワードを境界としてノードを2つに分割し、新しいノードを生成し、真ん中のキーワードを親ノードまで移動します。

ヒント: 真ん中のキーワードが 2 つある場合、通常は左側のキーワードが使用されます。分割。 削除

削除操作は、検索と挿入よりも面倒です。削除するキーワードがリーフ ノードに存在する場合と存在しない可能性があり、削除によって

B が発生する可能性があるためです。 -tree

はバランスが崩れており、ツリー全体のバランスを維持するにはマージや回転などの操作が必要です。 任意のツリー (レベル 5) を例として取り上げます

以上が最後に、MySQL インデックスは B+tree を使用する必要があり、それが非常に高速であることを理解しました。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。