MySQL でインデックスとして B+Tree を使用する利点は何ですか?

データベースにインデックスが必要なのはなぜですか?

データベースのデータはディスクに保存されることは誰もが知っています。プログラムを起動すると、マシンのメモリ内でプロセスが実行されることと同じになります。したがって、プログラムがデータを照会する場合、メモリからディスクに移動してデータを検索し、そのデータをメモリに書き戻す必要があります。ただし、ディスクの IO 効率はメモリの IO 効率よりもはるかに低いため、データの検索速度はプログラムの効率に直接影響します。
データベースにインデックスを追加する主な目的は、適切なデータ構造を使用することです。これにより、愚かなグローバルトラバーサルではなく、データクエリの効率が向上し、ディスク IO の数が減少し、データ検索の速度が向上します。

インデックスが B+Tree データ構造を使用するのはなぜですか?

単純に考えると、データを素早く探したいならハッシュテーブルが一番速いようです。キーに従って特定のスロットにハッシュしておけば、たった1回の検索でデータの場所を正確に見つけることができます。これはどれくらい速いのでしょうか？しかし、ビジネスを行う際には、必要なデータが 1 つだけであることが多く、特定の条件に基づいてデータの一部を照会する必要がある場合がほとんどです。このとき、ハッシュ表示はあまり適していません。

二分木、バランス二分木、赤黒木、B 木などの木を考えてみましょう。これらはすべて二分探索を使用し、数字を見つけるのが速いです。ただし、バランス二分木であろうと最適化された赤黒木であろうと、最終的にはすべて二分木です。ノードの数が多いほど、高さが高くなります。データをいくつか見つけてみましょう。ルート ノードがない場合は、次のレイヤーを探します。次のレイヤーにまだデータがない場合、次のレイヤーを再度探します。この結果、データを複数回検索する必要があり、そのたびにディスク IO が実行されます。インデックスの目的はディスク IO を削減することであるため、この設計は受け入れられません。それで、高さを低くすればいいのでしょうか?
それでは、B ツリーをもう一度考えてみましょう。まず、B ツリーのデータ構造を簡単に紹介します。
まず、B ツリーの定義を見てみましょう。

1. 各ノードには最大 m-1 個のキーワード (保存できるキーと値のペア) があります。
2. ルート ノードには少なくとも 1 つのキーワードを含めることができます。
3. 非ルートノードには少なくとも m/2 個のキーワードがあります。
4. 各ノード内のキーワードは昇順で並べられています。各キーワードの左側のサブツリー内のすべてのキーワードはそれより小さく、右側のサブツリー内のすべてのキーワードはそれより大きくなります。
5. すべてのリーフ ノードは同じレイヤーに配置されているか、ルート ノードから各リーフ ノードまでの長さが同じです。
6. 各ノードにはインデックスとデータ、つまり対応するキーと値が格納されます。
   

したがって、ルート ノードのキーワードの数の範囲は 1 <= k <= m-1 であり、非ルート ノードのキーワードの数の範囲は m/2 <= k <= m-1 です。

ここで、m は順序を表し、ノードが最大でいくつの子ノードを持つかを示します。そのため、B ツリーを記述するときには順序を指定する必要があります。

上記の概念を説明するために、別の例を見てみましょう。たとえば、ルート ノード番号の範囲が 1 <= k <= 4、非ルート ノード番号の範囲が 2 <= k <= 4 の 5 次 B ツリーがあります。

次に、挿入例を通して B ツリーの挿入プロセスを説明し、その後キーワードを削除するプロセスを説明します。

Bツリー挿入

挿入するときは、現在のノードのキーの数が m-1 以下であるかどうかを判断するというルールを覚えておく必要があります。条件を満たしている場合は、そのまま挿入します。条件を満たしていない場合は、ノードの中央のキーを使用してノードを 2 つの部分に分割し、中央のノードを親ノードに配置します。

例: 5 次 B ツリーでは、ノードには最大 4 つのキーがあり、最小 2 つのキーがあります (注: 次のノードは、キーと値を表す 1 つのノードで均一に表されます)。

18、70、50、40を挿入

挿入22

22 を挿入すると、このノードのキーワードがすでに 4 より大きいことがわかり、分割する必要があります。分割のルールは上記で説明しました。分割後は次のようになります。

次に23、25、39を挿入します

分割すると次のようになります。

したがって、B ツリーの各層のノード数が増加します。同じデータ量の場合、B ツリーはバイナリ ツリーよりも低くなり、必要な IO 操作の数も減少するため、インデックス作成の要件を満たします。では、なぜ MySQL は最終的に B+ ツリーを選択したのでしょうか? B ツリーと比べて何が優れているのでしょうか?
まず、B+ ツリーと B ツリーの違いを見てみましょう。

• B+ツリーのリーフノードには、ツリーのすべてのキー値が含まれます。非リーフノードにはデータは保存されず、インデックスのみが格納されます。データはリーフノードに保存されます。 B ツリーでは、各ノードにインデックスとデータが格納されます。
• B+ ツリーの各リーフ ノードには隣接するリーフ ノードへのポインタが格納され、リーフ ノード自体はキーワードのサイズに応じて昇順にリンクされます。
  

図に示すように:

1 点目: 非リーフ ノードにインデックス キーのみが格納され、データは格納されない場合、非リーフ ノードが占めるスペースを削減できます。同じ容量のノードには、より多くのインデックスを格納できます。同じ 3 層 B+ ツリーの場合、レベル数が増え、B ツリーよりも多くのデータを格納できます。
2 番目のポイント: B+ ツリーのリーフ ノードには、隣接するリーフ ノードへのポインタが格納されます。このポインタの利点を理解するには、まず、ディスクがデータを読み取るときに、厳密にオンデマンドで読み取られるのではなく、毎回事前に読み取られることを知っておく必要があります。必要なのが 1 バイトだけの場合でも、ディスクはこの位置から開始し、一定の長さのデータを順番に逆方向にメモリに読み込みます。この理論的根拠は、コンピュータ サイエンスにおける有名な局所性原理です。

• あるデータが使用されると、通常は近くのデータもすぐに使用されます。
• プログラム実行中に必要なデータは通常集中しています。
  

事前読み取りの長さは、通常、ページの整数倍になります。ページは、コンピュータ管理メモリの論理ブロックです。ハードウェアとオペレーティング システムは、多くの場合、メイン メモリとディスク ストレージ領域を同じサイズの連続ブロックに分割します。各ストレージ ブロックはページと呼ばれます (多くのオペレーティング システムでは、ページ サイズは通常 4k です)。メイン メモリとディスクは、ページ単位でデータを交換します。プログラムが読み取ろうとするデータがメインメモリにない場合、ページフォールト例外が発生します。このとき、システムはディスクに読み取り信号を送信します。ディスクはデータの開始位置を見つけ、1つまたは複数のページを連続的に読み取り、メモリにロードします。その後、例外が返され、プログラムは引き続き実行されます。

ここで、B+ツリーの子ノードのポインタを見て、その用途を理解しましょう。事前に読み取るときに、連続して読み取られるデータが順序どおりであることを保証できます。

学生の中には、B+ ツリーをベースにして非リーフ ノードのリンク リスト ポインターを追加した B* ツリーについて言及した人もいるかもしれません。個人的には、非リーフ ノードにデータを保存しないので、B スター ツリーは不要だと思います。データはすべてリーフ ノードにあり、非リーフ ノードのリンク リスト ポインターは使用されません。

いくつかの派手なコンセプト

クラスター化インデックスと非クラスター化インデックス: 前述のように、B+ ツリーのリーフ ノードにはインデックス キーのデータが格納されますが、MySQL エンジンによってデータの格納方法が異なります。MyISAM は、インデックス ファイルと実際のデータ ファイルを 2 つのファイルに格納します。インデックス ファイルに格納されるデータは、データ ファイル内のインデックス キーに対応するデータのアドレス値ですが、InnoDB はリーフ ノードに正式なデータを格納します。したがって、クラスタリングと非クラスタリングは、リーフノードに格納されているデータが本物であるかどうかを区別するためのものです（リーフノードが混雑しているかどうかと理解できます）。

テーブルに戻る: テーブルに戻るのも簡単ですが、まず主キー インデックスと通常のインデックスを理解する必要があります。前述のリーフ ノードには実際のデータが格納されますが、これは主キー インデックスにのみ格納されます。通常のインデックスに格納されるデータは、主キー インデックスのキーです。そうすれば、私たちにとっても理解しやすくなります。たとえば、テーブルの名前フィールドに通常のインデックスを作成しました。name = 'test' のテーブルから * を選択したいとします。テスト ノードを見つけると、取得するキーはこのデータ行に対応する主キーのみになります。行全体のデータを取得する場合は、このキーのみを使用して主キー インデックス ツリーを再度検索できます。この操作はテーブル戻りと呼ばれます。

左端の一致原則: (name+age) などの新しい複合インデックスを作成する場合、where name = xx and age = xx を使用してクエリを実行すると、複合インデックスが使用され、where age = xx and name = xx は使用されません。これは、MySQL が共同インデックスを作成するためのルールでは、最初に共同インデックスの左端のフィールドをソートし、次に最初のフィールドのソートに基づいて 2 番目のフィールドをソートするためです。

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