MySQL のクラスター化インデックスとクラスター化インデックスの成長の仕組みを理解する

このノートでは、

MySQL の B+Tree インデックスとは何ですか?
クラスター化インデックスはどのようにして大きくなるのでしょうか?

少しずつ見ていくと、実はとても簡単に理解できます。

私の以前のメモを読んだことがあるなら、MySQL がメモリ内、つまりバッファプール内で CRUD を実行することをご存知でしょう。また、メモリ内に MySQL が必要とするデータがない場合、MySQL は IO 操作を通じてディスクからメモリにデータを読み込むこともご存じでしょう。読み取り単位はデータページです

一般的なデータページの長さは次のとおりです。

そうです、実際のデータはデータページに保存され、データページはメモリ内で双方向リンクテーブルとして編成されます。下記の通り

B+Tree の設定では、主キーインデックスを増分する必要があります。つまり、主キーインデックスを増分する場合は、右側のデータページ内のすべてのデータが左側のデータページのデータよりも大きくなければなりません。しかし、上の図は明らかに一致していないので、ページ分割によって以下のように調整する必要があります。

さて、思い出してみてください。以前にも聞いたことがあるはずです。MySQL の B+Tree クラスター化インデックスでは、リーフノードのみが実際のデータを格納し、非リーフノードはインデックスデータを格納し、リーフノードは双方向のリンクリストによって接続されます。

そうです、B+ツリーのすべてのリーフノードは上図のデータページであり、それらは実際に二重リンクリストによってリンクされています。

読み進めてみましょう。上の図のデータページによって接続された二重リンクリストだけを見ると、id=7 のデータ行を取得すると何が起こるでしょうか。

当然、スキャンを最初からやり直す必要があります。

すると、あなたはこう思うかもしれません: B+ ツリーでは主キーが増加する必要があると言ったのではないですか?また、右側のデータページ内のすべてのデータが左側のデータページのインデックス値よりも大きくなるようにするページ分割メカニズムがあります。バイナリ検索を実行してみませんか?

回答: はい、確かに単一のデータページでバイナリ検索を実行することは可能ですが、データページ間の組織関係はリンクリストであるため、最初からのトラバーサルは避けられません。

では、MySQL はどうでしょうか?

下図に示すように、MySQLは多くのデータページのインデックスディレクトリを抽象化します。

このインデックスディレクトリを使用すると、多数のデータページ間の検索がはるかに簡単になります。バイナリ検索の能力を直接持つ！

そして、このディレクトリは実際にはデータページに存在します。リーフノードとの違いは、リーフノードには実際のデータが格納されるのに対し、このディレクトリにはインデックス情報のみが格納されることです。

インデックスページの誕生は、B+Tree のプロトタイプが誕生したことを意味します。

ユーザーが選択を続けると、バッファープール内のデータページの数が増加し、インデックスページ内のデータ数も増加します。既存のインデックスサイズが 16 KB (データページの容量) を超える場合、新しいインデックス情報を格納するために新しいインデックスページを作成する必要があります。この時点で、B+ツリーは徐々に太くなっていきます。

そして、B+ツリーはBツリーの変種であり、Bツリーは実際には2-3ツリー、2-3-4ツリーなどのM次ツリーの総称であることがわかります。各ノードに格納できる要素が上限に達すると、ツリーは高くなります（前の記事で説明しました）。

次の図のように: