MySQLのインデックスシステムがB+ツリーを使用する理由の分析

1. インデックスとは何ですか?

インデックスは、テーブル内のデータ行の取得を高速化するために作成される分散ストレージ構造です。 （子供の頃に使っていた辞書と同じように、辞書で対応する単語を探す方が早いでしょう）

2. インデックスはなぜ必要なのでしょうか?

まず、いくつかの概念と知識を理解する必要があります

1. mysql データはどこに保存されますか? - - ディスク
2. データのクエリが遅い場合、通常どこに問題がありますか? ----IO
3. （IOの効率を上げる必要があるのですが、どうやって上げればいいのでしょうか？----頻度と量の2つのレベル。例えば、レンガを1回動かすのと10回動かすのに費やされる労力は異なります。レンガを1個ずつ動かすのと10個ずつ動かすのに費やされる労力（IOリソースを占有する）も異なります。そのため、自分たちのニーズを満たしながら、IOとのやりとりをできるだけ減らすようにしています）
4. ディスクからデータを読み取るとき、必要なだけ読み取りますか? ----ディスクの事前読み取り
5. ディスクの事前読み取り: メモリとディスク間でデータが交換されるとき、通常はページ (データページ) と呼ばれる最小の論理単位があります。ページのサイズは一般にオペレーティング システムによって決定され、通常は 4k または 8k です。データを交換するとき、ページの整数倍でデータを読み取ることができます。InnoDB ストレージ エンジンは、毎回 16k のデータを読み取ります。
6. 局所性原則: データとプログラムは一緒にクラスター化される傾向があり、以前アクセスされたデータは再度クエリされる可能性があり、空間的局所性と時間的局所性が関係します。

上記の概念を通じて、インデックスが何のために使用されるのか大まかにわかります。つまり、事前にインデックス システムを設計し、データをクエリするときに IO とのやり取りを減らして、クエリの効率を向上させます。

3. インデックス システムをどのように設計するか?

まずはいくつかの概念を理解しましょう

• インデックスはどこに保存されますか? ----ディスク、データをクエリするときに、インデックスが最初にメモリにロードされます
• インデックスを保存するときに必要な情報は何ですか?どのようなフィールド値を保存する必要がありますか?
  

——キー: 実際のデータ行に格納されている値 -ファイル アドレス(ポインター、データ ファイルが保存されている場所を見つけるにはファイル アドレスに頼る必要があります)
—— offset : オフセット（ファイル内のデータを取得する場合は、オフセットを使用する必要があります）

• 上記の形式でデータを保存するには、どのようなデータ構造を使用する必要がありますか?
  

—— 上記から、データ形式が KV タイプであることがわかります。KV 形式のデータがわかれば、ハッシュ テーブル、ツリー (バイナリ ツリー、バイナリ検索ツリー、バイナリ バランス ツリー、赤黒ツリー、 B ツリー、 B+ ツリー) など、データを格納するために使用するデータ構造がわかります。
まとめると、上記のデータ構造を使用してインデックスシステムを設計することができます。

4.MYSQL インデックス システムとは何ですか?

上記の形式で保存してみませんか?

ご存知のとおり、MySQL のインデックス システムはB+ ツリーを使用します。なぜ B+ ツリーなのでしょうか?次に、他のストレージ構造が機能しない理由を 1 つずつ分析します。その前に、OLAPとOLTPという2つの前提条件を理解する必要があります。

保存するデータが増えるほど、対応するインデックスも大きくなります。ディスクからメモリに読み込むときに、IO 問題が発生します。それでは、インデックスにインデックスを作成するのでしょうか?いいえ、MySQLはB+ツリーを使用します

5. ハッシュテーブル

上記はハッシュ テーブルのストレージ構造です。このタイプのストレージ構造の利点と欠点について説明します。

• ハッシュ衝突により、データ ハッシュが不均一になり、大量の線形クエリが生成され、時間がかかります。
• 範囲クエリはサポートされていません。範囲クエリを実行するときは、各
• メモリスペースの要件が比較的高い（すべてのデータをメモリに追加する必要がある）
  

アドバンテージ：
等価値クエリであれば、非常に高速になります

MySQL にはハッシュ インデックスがあるのでしょうか?

• メモリ ストレージ エンジンはハッシュ インデックスを使用します。
• InnoDBは適応ハッシュをサポート

6. 木

6.1 二分木

バイナリ ツリー自体は順序付けられていません。データを検索するときは、データ要件を満たしているかどうかを確認するために、各ノードとデータを 1 つずつ比較する必要があり、非効率的です。

6.2 二分探索木 (BST)

二分探索木の特性: データは順番に挿入する必要があり、左のサブツリーはルート ノードよりも小さく、右のサブツリーはルート ノードよりも大きくなることが保証される必要があります。したがって、バイナリ ツリーと比較してバイナリ検索ツリーを使用すると、クエリの効率が明らかに向上します。
ただし、データが昇順または降順で挿入されると、バイナリ検索木はリンクリストに退化し、検索効率が低下します。

6.3 バランス二分木 (AVL 木)

バイナリ検索ツリーによって明らかになった問題に応じて、AVL ツリーを使用してツリーを左または右に回転させてバランスをとります。ただし、バランスを確保するためには、データを挿入するときにローテーションが必要であり、クエリのパフォーマンスの向上を挿入パフォーマンスの低下で補うことになります。読み取りが多く、書き込みが少ない場合は問題ありませんが、読み取り要求と書き込み要求の数が同じ場合は適していません。

6.4 赤黒木

赤黒木も左右の回転でバランスが取れており、色が変わる動作もあります。最長のサブツリーは最短のサブツリーの 2 倍以下であればよいので、クエリ パフォーマンスと挿入パフォーマンスはほぼバランスが取れます。ただし、データが挿入されると、ツリーの深さが深くなることがわかります。深さが深くなるほど、IO 時間が増え、データ読み取りの効率に影響します。

6.5 Bツリー

赤黒木によって明らかになった問題を考慮すると、読み取りの効率をどのように向上させるべきでしょうか?より多くのデータを保存できるように、順序付きバイナリ ツリーから順序付きマルチブランチ ツリーに変更できますか?

次数 4 は、ノードが 3 つのデータ値を格納し、それを超える値は変換する必要があることを意味します。では、実際のデータはどのように保存されるのでしょうか?キーと完全なデータ行が必要です

上の図は、B ツリーが実際にデータを格納する方法を示しています。各ノードには、キー、ポインタ、データの3 つの要素があります。
たとえば、データ 28 を見つけたい場合、まずディスク ブロック 1 から開始しますが、読み取れないことがわかります。p2 ポインターが指すディスク ブロック 3 と範囲を比較した後も、まだ見つかりません。次に、ディスク ブロック 8 を指しているディスク ブロック 3 の p2 ポインターに従って 28 を見つけます。分析してみましょう。各ディスク ブロックのサイズは 16kb です。3 つのディスク ブロックを検索するには、 48kb を読み取るだけで済みます。3層の B ツリーには、いくつのレコードを保存できますか。

理想化して、キーとポインターはスペースを占有せず、1 つのデータが 1k のスペースを占有すると仮定します。すると、ディスク 1 には 16 個のデータが保存でき、ディスク 3 にも 16 個のデータがあり、ディスク 8 にも 16 個のデータがあります。この場合、16 + 16 + 16 = 4096レコードしか保存できませんが、明らかに少し少なすぎます。実際、キーとポインターもスペースを占有します。

では、なぜ保存されるデータの量がこんなに少ないのか疑問に思わざるを得ません。
ストレージの各層のサイズはデータによって占有されていることがわかりましたが、キーとポインターのみを保存できますか?このため、B+ツリーが導入される。

6.6 B+ツリー

BツリーからB+ツリーへの進化:非リーフノードはデータを保存せず、リーフノードのみがデータを保存します

上図では、p1と28は10バイトのグループであると仮定すると、第1層は16000/10=1600のサイズを保存でき、第2層も1600、第3層のデータは1kbを占め、これは16レコードであるため、合計ストレージは1600 1600 16=40960000（ 4096万）レコードになります。

MySQL のインデックス構造は一般的に3 ～ 4層ですが、注意が必要な問題が 1 つあります。 3 層のストレージ構造があると仮定した場合、より多くのデータを保存するにはどうすればよいですか?
p1 と 28 のサイズが 10 バイトであると仮定しました。1 バイトの場合はどうなるでしょうか? その場合、合計ストレージ容量は 16000 16000 10 = 4096000000 になります。したがって、面接で常に尋ねられる質問につながります。インデックスを作成するには、int と var のどちらを使用する方が良いですか?

回答: キーの長さが短いほど良いです。長さが 4 バイト未満の varchar の場合は varchar を使用し、長さが 4 バイトを超える varchar の場合は int を使用します。

B+ ツリーの特性として、ストレージ容量が大きく、クエリが高速であることから、MySQL では B+ ツリーが採用されています。

要約する

これで、MySQL インデックス システムが B+ ツリーを使用する理由の説明は終わりです。何か間違ったことを言っていたら、指摘して訂正していただければ幸いです。

これで、MySQL のインデックス システムが B+ ツリーを使用する理由に関するこの記事は終了です。MySQL インデックス B+ ツリーの詳細については、123WORDPRESS.COM の以前の記事を検索するか、次の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。