mysqlインデックスのデータ構造は何ですか

1. はじめに

mysql インデックスのデータ構造はツリーであり、一般的に使用されるストレージ エンジン innodb は B ツリーを使用します。ここでは、B ツリーとそれに関連する

検索ツリーについて簡単に紹介します。

#2. さまざまな検索ツリー

#1. バイナリ ソート ツリー (バイナリ検索ツリーとも呼ばれます)

バイナリ ソート ツリーは最も単純な検索ツリーです。特徴:

a) これは二分木です;

b) 左のサブツリーのすべてのノードの値は、その親ノードの値よりも小さいです。右のサブツリー内のすべてのノードの値がその親ノードの値より大きい。

2. バランス バイナリ ツリー (AVL ツリーとも呼ばれます)

バランス バイナリ ツリーはバイナリ ソート ツリーに基づいており、ツリーの深さを制限します。削減 比較の数を見つけます。

特徴:

a) これはバイナリ ツリーです;

b) 左のサブツリー内のすべてのノードの値は、親ノードの値、右側のサブツリーのすべてのノードの値が親ノードの値より大きい;

c) 左側のサブツリーと右側のサブツリーの深さの差は -1、0 以内です。 、１、それ以外の場合、サブツリーは回転調整です。

3. B ツリー (B ツリー)

B ツリーは、多方向のバランスのとれた検索ツリーであり、バランスのとれた 2 分木と比較して、直接の子ノードの数は 2 に制限されなくなりました。

m (カスタム) を指定できるため、ツリーの深さを大幅に増やすことなく、より多くのノードを保存できます。

B ツリーはファイル システムでよく使用されます。

機能:

a) ツリーの各ノードには最大で m (カスタム) の子ノードがあります;

b) ルート ノードがリーフ ノードでない場合、次のようになります。少なくとも 2 つの子ノードがある;

c) ルート ノードを除くすべての非リーフ ノード (少なくとも m/2) が子ノード全体を取得します;

d) 親ノードの値左端のサブツリーのすべてのノードの値は、親ノードの最小値

より小さいです。右端のサブツリーのすべてのノードの値は、親ノードの最大値 ## より大きくなります。

#残りの中間値 サブツリー内のすべてのノードの値は、ポインタの親ノードの両側の値の間にあります;

e) すべての葉ノードは同じ上にありますlevel;

注: すべてのノードには値

4 があります。B ツリー (B ツリー)

B ツリーは B ツリーのバリアントです。 B ツリーと比較すると、リーフ ノードの値にはすべてが含まれます。すべての親ノードの値は、リーフ ノードの値を繰り返します。

親ノードはインデックス検索の役割のみを果たし、すべてのリーフ ノードも形成されます順序付けされたリンクリスト。

mysql のストレージ エンジンは innodb のインデックスであり、使用されるデータ構造は B ツリーです。

機能:

a) m 個の子ノードを持つ親ノードには m 個のキーワードがあります;

b) すべてのリーフ ノードにはすべてのキーワード (値) が含まれており、順序付けされたリンクを形成します。小さいものから大きいものへのリスト;

c) すべての非リーフ ノードはインデックスとして機能し、ノードにはサブツリー内のすべてのノードの最大値のみが含まれます;

d) すべてのリーフ ノードは同じレベル;

注: リーフ ノードにはすべてのキーワード (値) が含まれます。

5. B*Tree (B*Tree)

B* ツリーは B ツリーのバリアントで、B ツリーと比較して非リーフのサポートが追加されています。ポイントへのポインタ、つまり同じレベルの非リーフ ノードもリンク リストを形成します。

3. 概要

要約すると、上記の検索ツリーは相互に関連しています。

これは、主キーを通じてデータを集約し、それを実装するために B ツリーを使用するクラスター化インデックスなどの B ツリーを使用する、mysql の innodb インデックスに帰着します。はインデックスであり、MySQL のデータ ストレージ構造でもあります。リーフ ノードにはすべてのデータが含まれ、非リーフ ノードはインデックスとしてのみ機能します (

が主キーを定義しない場合、InnoDB は暗黙的に主キーを次のように定義します)クラスター化インデックス)。

MySQL に関連する技術的な記事については、

MySQL チュートリアル

列にアクセスして学習してください。

以上がmysqlインデックスのデータ構造は何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。