MySQL では、Innodb と MyIsam の両方がインデックス構造として B ツリーを使用します (ハッシュなどの他のインデックスはここでは考慮されません)。この記事では、最も一般的な二分探索ツリーから始めて、さまざまなツリーによって解決される問題と直面する新たな問題を徐々に説明し、それによって MySQL がインデックス構造として B ツリーを選択する理由を説明します。
1. 二分探索木 (BST): 不均衡# #Binary Search Tree (BST、Binary Search Tree) は、バイナリソートツリーとも呼ばれ、バイナリツリーに基づいて満たす必要があります。つまり、任意のノードの左側のサブツリー上のすべてのノードの値がルートノードの値より大きくないことです。 、任意のノード 右のサブツリー内のすべてのノードの値がルート ノードの値以上です。以下はBST（ピクチャーソース）です。
高速検索が必要な場合、BST にデータを保存するのが一般的な選択です。これは、現時点ではクエリ時間はツリーの高さに依存し、平均時間計算量は O であるためです。 (lgn)。ただし、
は、下の図 (画像ソース) に示すように、歪んで不均衡になる可能性があります。このとき、BST はリンク リストに縮退し、時間計算量は次のように縮退します。の上）。 この問題を解決するために、バランスのとれたバイナリ ツリーが導入されます。
AVL ツリーは厳密にバランスが取れていますバイナリ ツリーの場合、すべてのノードの左右のサブツリー間の高さの差は 1 を超えることはできません。AVL ツリーの検索、挿入、削除は、平均と最悪の場合の両方で O(lgn) です。
AVL でバランスを実現する鍵は、回転操作にあります。挿入と削除によってバイナリ ツリーのバランスが崩れる可能性があるため、1 回以上のツリーの回転を通じてツリーのバランスを再調整する必要があります。データ挿入時はせいぜい1回転（一回転または二回転）だけで済みますが、データを削除するとツリーのバランスが崩れてしまいますので、AVLでは削除したノードからのパス上にある全ノードのバランスを保つ必要があります。ルートノードまでの回転 回転の大きさはO(lgn)です。時間のかかるローテーションのため、AVL
ツリーはデータを削除する際に非常に非効率的です; 多数の削除操作がある場合、バランスを維持するコストが高くなる可能性があります。利益よりも高いため、AVL は実際には広く使用されていません。
3. 赤黒木: 木が高すぎるAVL 木と比較して、赤黒木は厳密なバランスを追求していないただし、これは大まかなバランスです。ルートからリーフまでの可能な最長のパスの長さが、可能な最短のパスの 2 倍を超えないように注意してください。実装の観点から見ると、赤黒ツリーの最大の特徴は、各ノードが 2 つの色 (赤または黒) のいずれかに属しており、ノードの色の分け方は特定の規則を満たす必要があることです (特定の規則は省略します)。 。赤黒ツリーの例は次のとおりです (画像ソース):
AVL ツリーと比較すると、赤黒ツリーのクエリ効率は低下します。木のバランスが変わってしまうからで、悪くなると高さが高くなってしまいます。ただし、赤黒ツリーには色も導入されているため、赤黒ツリーの削除効率は大幅に向上しました。データの挿入または削除の際、基本的なバランスを確保するために必要な回転と色の変更は O(1) 回だけです。 AVL は必要ありません。ツリーは O(lgn) 回の回転を実行します。一般に、赤黒ツリーの統計的パフォーマンスは AVL よりも高くなります。 
データがディスクなどの補助記憶装置 (
MySQL やその他のデータベースなど) にある状況では、赤黒ツリーは苦手です。なぜなら、赤黒の木はまだ高く成長しすぎているからです。データがディスク上にある場合、ディスク IO が最大のパフォーマンス ボトルネックになるため、設計目標は IO の数を最小限に抑えることです。ツリーの高さが高くなるほど、追加、削除、変更に必要な IO 時間は増加します。パフォーマンスに重大な影響を与える検索。 4. B ツリー: ディスクのために誕生
B
このツリーは B-# とも呼ばれます##tree (- はマイナス記号ではありません) は、ディスクなどの補助記憶装置用に設計されたマルチパス分散検索ツリーです。バイナリ ツリーと比較すると、B ツリーの各非葉ノードは複数のサブツリーを持つことができます。 したがって、ノードの総数が同じである場合、B ツリーの高さは AVL ツリーおよび赤黒ツリーよりもはるかに小さく (B ツリーは「ダンプティ」です)、ディスク IO が大幅に削減されます。
B ツリーを定義する際の最も重要な概念は順序です。m 次の B ツリーの場合、次の条件を満たす必要があります:
B ツリーの定義では、主に子ノードと非リーフ ノードのレコードの数が制限されていることがわかります。
次の図は 3 次 B ツリーの例です (画像ソース):
B ツリーの利点は次のとおりです。木の高さが低いだけでなく、局所的な領域にアクセスできる能力、性的原理の利用。いわゆる局所性原理とは、あるデータが使用されるとき、短時間のうちに近くのデータが使用される可能性が高いことを意味します。 B ツリーは、同じノードに同様のキーを持つデータを格納します。データの 1 つがアクセスされると、データベースはノード全体をキャッシュに読み取ります。隣接するデータがすぐにアクセスされると、キャッシュから直接読み取ることができます。ディスク IO が必要ないため、B ツリーのキャッシュ ヒット率が高くなります。
B ツリーはデータベースにいくつか応用されており、たとえば mongodb のインデックスは B ツリー構造を使用しています。ただし、多くのデータベース アプリケーションでは、B ツリーの変形である B ツリーが使用されます。
5. B ツリー
B ツリーもマルチパスバランス検索ツリーです。B ツリーとの主な違いは次のとおりです。 :
#したがって、B ツリーには、B ツリーと比較して次の利点があります。
6. B-tree のパワーを実感してください
前述したように、赤黒ツリーなどの二分木と比較すると、B- Tree/B-tree が最も大きく、樹高が低いという利点があります。実際、Innodb の B インデックスの場合、ツリーの高さは通常 2 ～ 4 レベルです。以下に具体的な見積もりをしてみましょう。 ツリーの高さは次数によって決まります。次数が大きくなるほど、ツリーは短くなり、次数のサイズは各ノードが保存できるレコードの数によって決まります。 Innodb の各ノードはページ (ページ) を使用します。ページ サイズは 16KB で、そのうちメタデータは約 128 バイトのみを占め (ファイル管理ヘッダー情報、ページヘッダー情報などを含む)、スペースのほとんどはデータの保存に使用されます。 。3 層 B ツリーの場合、最初の層 (ルート ノード) には 1 ページがあり、1000 レコードを保存できます。2 番目の層には 1000 ページがあり、1000*1000 レコードを保存できます。 3 番目の層 (リーフ ノード) には 1000*1000 ページがあり、各ページには 100 レコードを保存できるため、1000*1000*100 レコード、つまり 1 億レコードを保存できます。バイナリ ツリーの場合、1 億レコードを保存するには約 26 層が必要です。
7. まとめ
最後に、さまざまなツリーによって解決された問題と直面した新たな問題をまとめます:
1) 、Binary Search Tree (BST): ソートの基本的な問題を解決しますが、バランスが保証できないため、リンク リストに退化する可能性があります;
2)、Balanced Binary Tree (AVL): の問題を解決します。回転によるバランスを取るが、回転演算効率が低すぎる;
3)、赤黒ツリー: 厳密なバランスを放棄し、赤黒ノードを導入することで、AVL 回転効率が低すぎる問題が解決されます。ただし、ディスクなどのシナリオでは、ツリーがまだ高すぎて IO 回数が多すぎます;
4)、B ツリー: バイナリ ツリーをマルチパスのバランスの取れた検索ツリーに変更することで、ツリーが高すぎる問題は解決されます;
5)、B ツリー: B ツリーに基づいて、非リーフ ノードがデータを格納しない純粋なインデックス ノードに変換され、ツリーの高さがさらに低くなります。さらに、リーフ ノードはポインターを使用してリンク リストに接続されるため、範囲クエリがより効率的になります。
推奨学習: MySQL チュートリアル
以上がMySQL がインデックス構造として B+ ツリーを選択するのはなぜですか? (詳しい説明)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
