B+ Tree は、効率的な挿入、削除、検索操作を可能にする B Tree の拡張機能です。
B ツリーでは、キーとレコードの両方を内部ノードとリーフ ノードに保存できます。一方、B+ ツリーでは、レコード (データ) はリーフ ノードにのみ保存でき、内部ノードはキー値のみを保存できます。
B+ ツリーのリーフ ノードは、検索クエリをより効率的にするために、単一リンク リストの形式でリンクされます。
B+ Tree は、メインメモリに格納できない大量のデータを格納するために使用されます。メイン メモリのサイズは常に制限されているため、B+ ツリーの内部ノード (レコードにアクセスするためのキー) はメイン メモリに格納され、リーフ ノードは二次メモリに格納されます。
B+ ツリーの内部ノードは、インデックス ノードと呼ばれることがよくあります。次数 3 の B+ ツリーを次の図に示します。
B+ ツリーの利点
- 同じ回数のディスクアクセスでレコードをフェッチできます。
- 木の高さはバランスが取れており、B木に比べて低くなります。
- B+ ツリーに格納されたデータには、直接アクセスすることも、順次アクセスすることもできます。
- キーはインデックス作成に使用されます。
- データがリーフ ノードにのみ保存されるため、検索クエリが高速になります。
B ツリー VS B+ ツリー
| SN | Bツリー | B+ ツリー |
|---|---|---|
| 1 | 検索キーを繰り返し保存することはできません。 | 冗長な検索キーが存在する可能性があります。 |
| 2 | データは内部ノードだけでなくリーフノードにも保存できます | データはリーフ ノードにのみ保存できます。 |
| 3 | データはリーフ ノードだけでなく内部ノードでも見つかる可能性があるため、一部のデータの検索は処理が遅くなります。 | データはリーフ ノードでのみ見つかるため、検索は比較的高速になります。 |
| 4 | 内部ノードの削除は非常に複雑で時間がかかります。 | 要素は常にリーフ ノードから削除されるため、削除は複雑なプロセスになることはありません。 |
| 5 | リーフ ノードを相互にリンクすることはできません。 | リーフ ノードは、検索操作をより効率的に行うために相互にリンクされます。 |
B+ ツリーへの挿入
ステップ1： 新しいノードをリーフ ノードとして挿入します
ステップ2： リーフに必要なスペースがない場合は、ノードを分割し、中間ノードを次のインデックス ノードにコピーします。
ステップ 3: インデックス ノードに必要なスペースがない場合は、ノードを分割し、中央の要素を次のインデックス ページにコピーします。
例 ：
次の図に示す次数 5 の B+ ツリーに値 195 を挿入します。
195 は、120 の右側のサブツリーの 190 の後に挿入されます。任意の位置に挿入します。
ノードには最大数 (つまり 4) を超える要素が含まれているため、ノードを分割し、中央ノードを親まで配置します。
ここで、インデックス ノードには 6 つの子と 5 つのキーが含まれており、B+ ツリーのプロパティに違反しているため、次のように分割する必要があります。
B+ ツリーの削除
ステップ1： リーフからキーとデータを削除します。
ステップ2： リーフ ノードに含まれる要素が最小数に満たない場合は、そのノードをその兄弟とマージし、それらの間にあるキーを削除します。
ステップ 3: インデックス ノードに含まれる要素が最小数に満たない場合は、ノードを兄弟とマージし、それらの間のキーを下に移動します。
例
次の図に示す B+ ツリーからキー 200 を削除します。
夕食対夕食
200 は、190 の右側のサブツリーの 195 の後に存在します。これを削除します。
195、190、154、129 を使用して 2 つのノードをマージします。
ここで、要素 120 は、B+ ツリーのプロパティに違反しているノード内に存在する単一の要素です。したがって、60、78、108、120 を使用してマージする必要があります。
これで、B+ ツリーの高さが 1 減ります。
