MySQL の B ツリー インデックスと B+​​ ツリー インデックスの違いは何ですか?

インデックス データ構造としてツリーを使用する場合、データを検索するたびに、ツリーの 1 つのノード (ページ) がディスクから読み取られます。ただし、バイナリ ツリーの各ノードには 1 つの部分のみが保存されます。データ量が多く、ページを埋めることができません。ストレージ スペースがある場合、余分なストレージ スペースが無駄になっていませんか?バイナリ平衡検索ツリーのこの欠点を解決するには、単一ノードにより多くのデータを格納できるデータ構造、つまり多方向検索ツリーを探す必要があります。

1. マルチパス検索ツリー

1. 完全なバイナリ ツリーの高さ: O(log2N) (2 は対数、各レベルのノード数)ツリーの;

2. 完全な M 方向検索ツリーの高さ: O(logmN)、M は対数、つまりツリーの各レベルのノードの数です。 ;

M-way 検索ツリーは、保存されたデータの量が多すぎて一度にメモリにロードできないシナリオに適しています。レイヤーあたりのノード数を増やし、各ノードに保存するデータを増やすことで、1 つのレイヤーにさらに多くのデータを保存します。これにより、ツリーの高さが減り、データ ルックアップ中のディスク アクセスの数が減ります。

したがって、各ノードに含まれるキーワードの数とレベルごとのノードの数が増加すると、ツリーの高さは減少します。各ノードのデータ決定にはさらに時間がかかりますが、B ツリーの焦点はディスク パフォーマンスのボトルネックを解決することであるため、単一ノード上のデータ検索のコストは無視できます。

2. B ツリー - マルチパスバランス検索ツリー

B ツリーは M-way 検索ツリーであり、B ツリーは主に不均衡な M-way 検索の問題を解決するために使用されます。高、これはバイナリ ツリーのリンク リストへの縮退によって引き起こされるパフォーマンスの問題と同じです。 B ツリーは、ノードの分離、ノードの結合、1 つの層がいっぱいになったときに新しい層を追加するために親ノードを上方に分割するなどの操作など、各層のノードを制御および調整することにより、M-way 検索ツリーのバランスを確保します。

B ツリーでは、各ノードはディスク ブロック (ページ) であり、順序またはパス番号 M はノード内の子ノードの最大数を指定します。各非リーフ ノードはキーワードとサブツリーへのポインタを格納します。具体的な数は次のとおりです: M 次の B ツリー、各非リーフ ノードは M-1 個のキーワードとサブツリーへの M ポインタを格納します。この図は、5 次の B ツリー構造の概略図を示しています:

3. B ツリー インデックス

最初にユーザーを作成します。テーブル:

create table user(
	id int,
	name varchar,
	primary key(id)
) ROW_FORMAT=COMPACT;

B ツリーを使用してテーブル内のユーザー レコードのインデックスを作成する場合:

各ノードB ツリーの 1 つのディスク ブロックはページでもあります。上の図からわかるように、バランスのとれたバイナリ ツリーと比較して、B ツリーの各ノードにはより多くの主キーとデータが格納され、各ノードにはより多くの子ノードがあります。 . ノードの数を一般に次数と呼びますが、上図のBツリーは3次のBツリーとなり、高さも低くなります。 id=28 のユーザー情報を見つけたい場合、検索プロセスは次のようになります:

1. ルート ノードに従ってページ 1 を見つけ、それをメモリに読み込みます。 [ディスク I/O 操作 1 回目]

2. 区間 (17,35) のキー値 28 を比較し、ページ 1 のポインタ p2 を見つけます;

3. ページを見つけますp2 ポインタに基づく 3. メモリに読み取ります。 [ディスク I/O 操作 2 回目]

4. 区間 (26,35) のキー値 28 を比較し、ページ 3 のポインタ p2 を見つけます。

5. p2 ポインタに従ってページ 8 を検索し、メモリに読み込みます。 [ディスク I/O 操作 3 回目]

6. 8 ページのキー値リストでキー値 28 を見つけます。キー値に対応するユーザー情報は (28,po);

# です。

##B-Tree AVLTree と比較してノード数が減り、ディスク I/O が使用されるたびにメモリからデータを取得するため、クエリが改善されます。効率。

4. B ツリー インデックス

B ツリーは、B ツリーに基づいた最適化であり、外部ストレージ インデックス構造の実装により適しています。B ツリーのプロパティ:

1. 非リーフ ノードのサブツリー ポインタはキーワードの数と同じです;

2. すべてのリーフ ノードにリンク ポインタを追加します;

3. すべてのキーワードはin リーフ ノードが表示され、リンクされたリスト内のキーワードがたまたま順序どおりになっている;

4. 非リーフ ノードはリーフ ノードのインデックスに相当し、リーフ ノードはデータを格納するデータ層に相当します。 (キーワード) data;

InnoDB ストレージ エンジンは、B Tree を使用してインデックス構造を実装します。

B-ツリー構造図では、各ノードにはデータのキー値に加えてデータ値も含まれていることがわかります。各ページの記憶容量は限られており、データデータが大きい場合、各ノード (つまり 1 ページ) に保存できるキーの数は非常に少なくなります。 to B- ツリーの深さが大きくなり、クエリ中のディスク I/O の数が増加し、クエリの効率に影響します。 B Treeでは、すべてのデータレコードノードがキー値順に同じ階層のリーフノードに格納され、非リーフノードにはキー値情報のみが格納されるため、各ノードに格納されるキー値の数を大幅に増やすことができます。 . B ツリーの高さを下げます。

B ツリーには、B ツリーと比較していくつかの違いがあります:

1. 非リーフ ノードは、キー値の情報と子ノードのページ番号へのポインターのみを保存します。

2. すべてのリーフ ノード間にリンク ポインタがあります;

3. データ レコードはリーフ ノードに保存されます;

上の図に基づいて、B ツリーと B ツリーの違いを見てみましょう。

(2) B ツリー、非リーフ ノードはキー値のみを保存しますが、B ツリー ノードはキー値とデータの両方を保存します。

ページ サイズは固定されており、InnoDB のデフォルトのページ サイズは 16 KB です。データが保存されていない場合、より多くのキー値が保存され、対応するツリーの順序が大きくなり、ツリーが太く短くなり、その結果、データの検索に必要なディスク IO 回数が増加します。データクエリの効率もさらに速くなります。

さらに、B ツリーの 1 つのノードが 1000 個のキー値を保存できる場合、3 層 B ツリーは 1000×1000×1000=10 億個のデータを保存できます。一般に、ルート ノードはメモリ内に常駐します (ルート ノードを初めて取得するときにディスクを読み取る必要はありません)。そのため、10 億のデータを検索するのに必要なディスク IO は 2 回だけです。

(2) B-tree インデックスのすべてのデータはリーフ ノードに格納され、データは順番に配置されます。

B ツリー内のページは双方向リンク リストを介して接続され、リーフ ノードのデータは一方向リンク リストを介して接続されます。このようにして、テーブル内のすべてのデータは、見つけられた。 B ツリーを使用すると、範囲クエリ、並べ替えクエリ、グループ クエリ、および重複排除クエリが非常に簡単になります。 B ツリーではデータがさまざまなノードに分散しているため、これを実現するのは簡単ではありません。

以上がMySQL の B ツリー インデックスと B+​​ ツリー インデックスの違いは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。