最後に、MySQL インデックスは B+tree を使用する必要があり、それが非常に高速であることを理解しました。-mysql チュートリアル-php.cn

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

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

はじめに

遅い SQL に遭遇し、それを最適化する必要がある場合、すぐにどのような最適化方法を思いつくでしょうか? ほとんどの人の最初の反応は、インデックスの追加でしょう。ほとんどの場合、index で SQL ステートメントにクエリを追加できます。効率は次のとおりです。数桁改善されました。 インデックスの本質: レコードを迅速に検索するために使用される データ構造。一般的に使用されるインデックスデータ構造:

バイナリツリー
赤黒ツリー
ハッシュテーブル
B-tree (B ツリーは B マイナスツリーとは呼ばれません)
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 方向探索ツリーです。これは空のツリーであるか、次の特性を満たす可能性があります:

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

#⌈ $⌈$
$m 2 \frac{⌉}{} #⌈$
名前の意味 (本題から外れます、リラックスしてください)
以下は Wikipedia からの抜粋です
ルドルフバイエル (ルドルフ・バイエルとエド・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 つのステップに分かれています:

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

#操作プロセス

次に、要素: 88

初回: ディスク IO

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

3 回目: Disk IO

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

検索プロセスから、

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

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

さらに、

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

挿入

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

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

操作プロセス

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

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

挿入するリーフノードを見つけます
ノード分割: である必要があります。 [70,88] 同じディスクブロック上ですが、ノードに 3 つのキーワードがある場合、そのノードには 4 つの子ノードがある可能性があり、定義した制限の最大次数 3 を超えるため、この時点で
split## を実行する必要があります。 time #: 真ん中のキーワードを境界としてノードを2つに分割し、新しいノードを生成し、真ん中のキーワードを親ノードまで移動します。