MySQL で B+ ツリー インデックスを使用する利点は何ですか?

この問題を理解する前に、まず MySQL テーブルのストレージ構造を確認し、次にバイナリ ツリー、マルチ ツリー、B ツリー、B+ ツリーの違いを比較してみましょう。

MySQL ストレージ構造

テーブルストレージ構造

単位: 表 > セグメント > 領域 > ページ > 行

データベースでは、1 行を読み取るか複数行を読み取るかに関係なく、これらの行が配置されているページが読み込まれます。つまり、ストレージスペースの基本単位はページです。
ページは B+ ツリーのノードです。データベース I/O 操作の最小単位はページであり、データベース関連のすべてのコンテンツはページ構造に格納されます。

B+ツリーインデックス構造

1. B+ ツリーでは、各ノードはページです。新しいノードが作成されるたびに、ページ スペースが要求されます。
2. 同じレイヤー上のノード同士が接続され、ページ構造を通じて双方向のリンクリストが形成されます。
3. 非リーフ ノードには複数のインデックス行が含まれ、各インデックス行にはインデックス キーと次のレベルのページへのポインターが格納されます。
4. リーフ ノードには、キーワードと行レコードが格納されます。ノード内 (つまり、ページ構造内) のレコード間には、一方向のリンク リストが存在します。
   

B+ツリーページノード構造

いくつかの特徴がある

1. すべてのレコードを複数のグループに分割し、各グループに複数のレコードを保存します。
2. ページ ディレクトリには、グループ化されたレコードのインデックスに相当するスロットが格納されます。各スロット ポインターは、異なるグループの最後のレコードを指します。
3. スロットを通じてグループを見つけ、グループ内のレコードを表示します
   

ページの主な機能はレコードを保存することであり、レコードは単一のリンク リストの形式でページに保存されます。
単一リンクリストの利点は、挿入や削除が簡単なことですが、検索効率が低く、最悪の場合にはリンクリスト内のすべてのノードをトラバースする必要があるという欠点があります。そのため、ページディレクトリにはレコード検索の効率を向上させるためのバイナリ検索方式が用意されています。

B+ツリー取得プロセス

B+ツリーの取得プロセスを見てみましょう。

1. B+ ツリーのルートから始めて、レイヤーごとにリーフ ノードを検索します。
2. 対応するデータ ページとしてリーフ ノードを見つけ、データ リーフをメモリにロードし、ページ ディレクトリのスロットをバイナリ検索して、まず大まかなレコードのグループ化を見つけます。
3. リンク リストをトラバースすることで、グループ内のレコードが検索されます。

B+ ツリー インデックスを使用する理由は何ですか?

データベースはページを通じてデータにアクセスします。ページは B+ ツリー ノードです。ノードへのアクセスは I/O 操作に相当するため、ノードの検索速度が速いほど、検索パフォーマンスが向上します。
B+ ツリーの特徴は、十分に短くて太いため、ノード アクセスの数を効果的に減らし、パフォーマンスを向上できることです。

次に、バイナリツリー、マルチフォークツリー、B ツリー、B+ ツリーを比較してみましょう。

バイナリツリー

バイナリ ツリーは、バイナリ検索と同等の検索パフォーマンスに優れたバイナリ検索ツリーです。
しかし、N が大きいほど、ツリーの深さは高くなります。データクエリの時間は主にディスク IO の数に依存します。バイナリツリーが深くなるほど、実行される検索の数が増え、パフォーマンスが低下します。
最悪の場合、以下のようにリンクリストに退化してしまう。

バイナリ ツリーがリンク リストに退化するのを防ぐために、AVL ツリー (バランス バイナリ サーチ ツリー) が発明されました。これは、任意のノードの左サブツリーと右サブツリーの高さの差が最大 1 であるツリーです。

多枝ツリー

マルチフォークツリーはM個のノードを持つことができ、高さを効果的に減らすことができます。高さが減るとノード数が減り、I/Oが自然に減り、バイナリツリーよりもパフォーマンスが向上します。

Bツリー

B ツリーは単純に複数のブランチを持つツリーであり、各リーフにはデータと次のノードへのポインタが格納されます。

例えば、9を見つけるには、次の手順に従います。

1. これをルートノードのキーワード (17, 35) と比較します。9 は 17 より小さいので、ポインター P1 を取得します。
2. ポインター P1 をたどってディスク ブロック 2 を見つけます。キーは (8, 12) です。9 は 8 と 12 の間にあるため、ポインター P2 を取得します。
3. ポインター P2 に従ってディスク ブロック 6 を見つけます。キーは (9, 10) で、次にキー 9 を見つけます。
   

B+ ツリー

B+ ツリーは B ツリーの改良版です。簡単に言うと、リーフ ノードのみがデータを保存し、リーフ以外のノードはストレージ ポインターです。すべてのリーフ ノードは順序付けされたリンク リストを形成します。

B+ ツリーの内部ノードにはキーワードの特定の情報へのポインタがないため、その内部ノードは B ツリーの内部ノードよりも小さくなります。同じ内部ノードのすべてのキーワードが同じディスク ブロックに格納されている場合、ディスク ブロックはより多くのキーワードを収容でき、一度に検索する必要があるキーワードの数も増えるため、相対的な IO 読み取りおよび書き込み時間が短縮されます。

たとえば、キーワード16を検索する手順は次のとおりです。

1. ルートノードのキーワード（1、18、35）と比較すると、16は1と18の間にあり、ポインタP1（ディスクブロック2を指す）を取得します。
2. ディスクブロック2を見つけます。キーは(1, 8, 14)です。16は14より大きいので、ポインタP3（ディスクブロック7を指す）を取得します。
3. ディスク ブロック 7 が見つかります。キーは (14、16、17) です。次にキー 16 が見つかるので、キー 16 に対応するデータを見つけることができます。

B+ツリーとBツリーの違い:

1. B+ ツリーの非リーフ ノードにはデータはなく、インデックスのみがあります。B ツリーの非リーフ ノードにはデータが格納されます。
2. B+ ツリー クエリの方が効率的です。 B+ ツリーは双方向リンク リストを使用してすべてのリーフ ノードを接続するため、範囲クエリがより効率的になります (すべてのデータが B+ ツリーのリーフ ノードにあり、データベースのスキャンではリーフ ノードを 1 回スキャンするだけで済むため)。ただし、B ツリーでは、検索範囲を完了するために順序どおりのトラバーサルが必要です。
3. B+ ツリーのクエリ効率がより安定します。 B+ ツリーは、データを見つけるために毎回リーフ ノードをクエリする必要があり、B ツリーによってクエリされたデータはリーフ ノードに存在しない場合もあれば、リーフ ノードに存在する場合もあるため、クエリの効率が不安定になります。
4. B+ ツリーではディスクの読み取りおよび書き込みコストが低くなります。 B+ ツリーの内部ノードにはキーワードの特定の情報へのポインタがないため、その内部ノードは B ツリーの内部ノードよりも小さくなります。通常、B+ ツリーは短くて太く、小さなクエリでは I/O が少なくなります。
   

MySQL が B+ ツリーを使用するのはそのためです。とても簡単です!

上記は、MySQL で B+ ツリー インデックスを使用する利点の詳細な内容です。MySQL で B+ ツリー インデックスを使用する方法の詳細については、123WORDPRESS.COM の他の関連記事に注目してください。