Bツリー

Bツリー
タイプ	ツリー（データ構造）
発明された	1970年[1]
発明者	ルドルフ・ベイヤー、エドワード・M・マクリート
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 検索 O(logn )は、 O(logn )は、 入れる O(logn )は、 O(logn )は、 消去 O(logn )は、 O(logn )は、 空間の複雑さ 空間 の 上） の 上）

コンピュータサイエンスにおいて、Bツリーは、ソートされたデータを維持し、対数時間で検索、順次アクセス、挿入、削除を可能にする自己バランス型ツリーデータ構造です。Bツリーは二分探索木を一般化し、 2つ以上の子を持つノードを許可します。 ^[2]他の自己バランス型二分探索木とは異なり、Bツリーは、データベースやファイルシステムなど、比較的大きなデータブロックを読み書きするストレージシステムに適しています。

B ツリーは、ボーイング研究所で働いていたルドルフ・ベイヤーとエドワード・M・マクリートによって、大規模なランダム アクセス ファイルのインデックス ページを効率的に管理する目的で発明されました。基本的な前提は、インデックスが非常に大きいため、ツリーの小さな部分しかメイン メモリに収まらないというものでした。ベイヤーとマクリートの論文「大規模な順序付きインデックスの編成と管理」^[1]は、1970 年 7 月に最初に配布され、後にActa Informaticaに掲載されました。^[3]

ベイヤーとマクリートは、 Bが何の略なのか、もしあったとしても何の略なのかを決して説明しなかった。ボーイング、バランス、間、広い、茂み、ベイヤーなどが示唆されている。^{[4] [5] [6]}マクリートは、「B ツリーの B が何を意味するかを考えれば考えるほど、B ツリーをよりよく理解できる」と述べている。^[5]

クヌースの定義によれば、 m次のB木は以下の性質を満たす木である: ^[7]

1. 各ノードには最大m 個の子が存在します。
2. ルートとリーフを除くすべてのノードには、少なくとも ⌈ m /2⌉ 個の子があります。
3. ルート ノードには、リーフでない限り、少なくとも 2 つの子が存在します。
4. すべての葉が同じレベルに表示されます。
5. k 個の子を持つ非リーフノードにはk −1 個のキーが含まれます。

各内部ノードのキーは、サブツリーを分割する分離値として機能します。たとえば、内部ノードに 3 つの子ノード (またはサブツリー) がある場合、キーは 1 と 2 の 2 つである必要があります_{。左端のサブツリーのすべての値は 1未満になり、中央のサブツリーのすべての値は 1}と2の_間になり_、右端のサブツリー_のすべての値は 2 より大きくなります。

内部ノード

内部ノード (インナー ノードとも呼ばれる) は、リーフ ノードとルート ノードを除くすべてのノードです。通常、これらは順序付けられた要素と子ポインターのセットとして表されます。すべての内部ノードには、最大U個の子と最小L個の子が含まれます。したがって、要素の数は常に子ポインターの数より 1 少なくなります (要素の数はL -1 とU -1 の間です)。Uは2 Lまたは 2 L -1のいずれかである必要があります。したがって、各内部ノードは少なくとも半分いっぱいです。UとLの関係は、半分いっぱいのノード 2 つを結合して 1 つの正当なノードを作成できること、および 1 つのいっぱいになったノードを 2 つの正当なノードに分割できること ( 1つの要素を親に押し上げる余地がある場合) を意味します。これらのプロパティにより、B ツリーから新しい値を削除して挿入し、B ツリーのプロパティを保持するようにツリーを調整できます。

ルートノード

ルート ノードの子の数には、内部ノードと同じ上限がありますが、下限はありません。たとえば、ツリー全体の要素数がL −1 未満の場合、ルートはツリー内で子を持たない唯一のノードになります。

リーフノード

Knuth の用語では、「リーフ」ノードは実際のデータ オブジェクト/チャンクです。これらのリーフの 1 レベル上にある内部ノードは、他の著者が「リーフ」と呼ぶものです。これらのノードには、キー (最大m -1、ルートでない場合は少なくともm /2-1) と、データ オブジェクト/チャンクを含むノードへのポインタ (キーごとに 1 つ) のみが格納されます。

深さn +1の B ツリーは、深さnの B ツリーの約U倍のアイテムを保持できますが、検索、挿入、および削除操作のコストはツリーの深さとともに増加します。バランスの取れたツリーと同様に、コストは要素の数よりもはるかにゆっくりと増加します。

一部のバランスツリーでは、リーフノードにのみ値を保存し、リーフノードと内部ノードに異なる種類のノードを使用します。B ツリーでは、リーフノードを除くツリー内のすべてのノードに値が保持されます。

Bツリーに関する文献では用語が統一されていない。^[8]

Bayer と McCreight (1972)、^[3] Comer (1979)、^[2]らは、B ツリーの順序を非ルート ノードのキーの最小数として定義しています。Folk と Zoellick ^[9]は、キーの最大数が明確ではないため用語が曖昧であると指摘しています。順序 3 の B ツリーは、最大 6 個のキーまたは最大 7 個のキーを保持できます。Knuth (1998) は、順序を子の最大数 (最大キー数より 1 多い数) として定義することで、この問題を回避しています。^[7]

リーフという用語も一貫性がありません。Bayer と McCreight (1972) ^{[3] は}リーフ レベルをキーの最下位レベルとみなしましたが、Knuth はリーフ レベルを最下位キーの 1 レベル下とみなしました。^[9]実装には多くの選択肢があります。設計によっては、リーフがデータ レコード全体を保持する場合もあれば、データ レコードへのポインターのみを保持する場合もあります。これらの選択は、B ツリーの考え方の基本ではありません。^[10]

簡単にするために、ほとんどの著者はノードに収まるキーの数は固定されていると仮定しています。基本的な仮定は、キーのサイズとノードのサイズが固定されていることです。実際には、可変長のキーが使用されることもあります。^[11]

他のツリーと同様に、B ツリーは、ルート、内部(別名、インテリア)、およびリーフの3 種類のノードのコレクションとして表すことができます。

次の変数定義に注意してください。

• K : B ツリー内の各ノードの潜在的な検索キーの最大数。(この値はツリー全体で一定です)。
• ${\displaystyle pt_{i}}$: サブツリーを開始する子ノードへのポインター。
• ${\displaystyle pr_{i}}$: データを格納するレコードへのポインタ。
• ${\displaystyle k_{i}}$: ゼロベースのノードインデックスにある検索キー。${\displaystyle i}$

B ツリーでは、これらのノードに対して次のプロパティが維持されます。

• B+ ツリーの任意のノードに が存在する場合、のノードに が存在します。${\textstyle k_{i}}$${\displaystyle k_{i-1}}$${\displaystyle i\geq 1}$
• すべてのリーフ ノードには同じ数の祖先があります (つまり、すべて同じ深さにあります)。

B ツリー内の各内部ノードの形式は次のとおりです。

B ツリーの各リーフ ノードの形式は次のとおりです。

ノード境界は以下の表にまとめられています。

子ノードの事前定義された範囲を維持するために、内部ノードが結合または分割される場合があります。

通常、キーの数は から の間で変化するように選択されます。ここで、はキーの最小数、 はツリーの最小次数または分岐係数です。係数 2 により、ノードを分割または結合できることが保証されます。 ${\displaystyle d}$${\displaystyle 2d}$${\displaystyle d}$${\displaystyle d+1}$

内部ノードにキーがある場合、そのノードにキーを追加するには、仮想キー ノードを 2 つのキー ノードに分割し、中間にあったキーを親ノードに移動します。分割された各ノードには、必要な最小数のキーがあります。同様に、内部ノードとその隣接ノードにそれぞれキーがある場合、隣接ノードと結合することで、内部ノードからキーを削除できます。キーを削除すると、内部ノードにキーが追加されます。隣接ノードを結合すると、キーと、隣接ノードの親から取得されたキーが 1 つ追加されます。結果は、完全にキーがいっぱいのノードになります。 ${\displaystyle 2d}$${\displaystyle 2d+1}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d-1}$${\displaystyle d}$${\displaystyle 2d}$

B ツリーは、キーの過剰入力になりそうなノードを2 つの-key 兄弟に分割し、中間値のキーを親に挿入することで、挿入後のバランスが保たれます。深さは、ルートが分割されたときにのみ増加し、バランスが維持されます。同様に、B ツリーは、削除後、非ルート ノードの -key 最小値を維持するために兄弟間でキーをマージまたは再分配することでバランスが保たれます。マージにより、親のキー数が減り、兄弟とのキーのマージまたは再分配が必要になる可能性があります。深さが変わるのは、ルートにと (遷移的に)キーの 2 つの子がある場合のみです。この場合、2 つの兄弟と親がマージされ、深さが 1 つ減ります。 ${\displaystyle 2d+1}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d-1}$

この深さは、ツリーに要素が追加されるにつれてゆっくりと増加しますが、全体的な深さの増加はまれであり、すべてのリーフ ノードがルートから 1 つ離れたノードになります。

子ノードの範囲が許可されるため、B ツリーは他の自己バランス検索ツリーほど頻繁に再バランスをとる必要はありませんが、ノードが完全にいっぱいではないため、いくらかのスペースを無駄にする可能性があります。

ノードのデータにアクセスする時間がそのデータの処理に要する時間を大幅に上回る場合、B ツリーは他の実装に比べて大きな利点があります。これは、ノードへのアクセス コストをノード内の複数の操作に分散できるためです。これは通常、ノード データがディスク ドライブなどの二次記憶装置にある場合に発生します。各内部ノード内のキーの数を最大化することで、ツリーの高さが低くなり、コストのかかるノード アクセスの回数が減ります。さらに、ツリーの再調整もあまり発生しません。子ノードの最大数は、各子ノードに格納する必要がある情報と、ディスク ブロック全体のサイズまたは二次記憶装置内の類似のサイズによって異なります。2 ～ 3 個の B ツリーの方が説明しやすいですが、二次記憶装置を使用する実際の B ツリーでは、パフォーマンスを向上させるために多数の子ノードが必要になります。

B ツリーという用語は、特定の設計を指す場合もあれば、設計の一般的なクラスを指す場合もあります。狭義では、B ツリーは内部ノードにキーを格納しますが、それらのキーをリーフのレコードに格納する必要はありません。一般的なクラスには、B+ ツリー、B ^*ツリー、B ^*+ツリーなどのバリエーションが含まれます。

• B+ツリーでは、内部ノードはレコードへのポインタを格納しないため、レコードへのポインタはすべてリーフノードに格納されます。さらに、リーフノードには、シーケンシャルアクセスを高速化するために、次のリーフノードへのポインタが含まれる場合があります。^[2] B+ツリーの内部ノードにはポインタが少ないため、各ノードはより多くのキーを保持でき、ツリーが浅くなり、検索が高速になります。
• B ^*ツリーは、より多くの隣接する内部ノードのバランスをとって、内部ノードをより高密度に保ちます。^[2]このバリアントは、非ルートノードが 1/2 ではなく少なくとも 2/3 いっぱいになることを保証します。^[13] B ツリーにノードを挿入する操作で最もコストのかかる部分はノードの分割であるため、B ^*ツリーは分割操作を可能な限り延期するように作成されます。^[14]これを維持するために、ノードがいっぱいになったときにすぐに分割するのではなく、そのキーを隣のノードと共有します。このスピル操作は、既存のノード間でキーをシフトするだけでよく、新しいノードにメモリを割り当てる必要がないため、分割よりもコストがかかりません。^[14]挿入の場合、最初にノードに空き領域があるかどうかがチェックされ、空き領域がある場合は新しいキーがノードに挿入されます。しかし、ノードがいっぱいの場合（m − 1 個のキーがあり、mは 1 つのノードからサブツリーへのポインターの最大数としてのツリーの順序）、右の兄弟が存在し、空き領域があるかどうかを確認する必要があります。右の兄弟がj < m − 1 個のキーを持っている場合、キーは 2 つの兄弟ノード間で可能な限り均等に再分配されます。この目的のために、現在のノードのm - 1個のキー、挿入された新しいキー、親ノードの 1 つのキー、兄弟ノードのjキーは、 m + j + 1 個のキーの順序付けられた配列と見なされます。配列は半分に分割されるため、⌊ ( m + j + 1)/2 ⌋ 個の最下位キーは現在のノードに残り、次の（中央の）キーは親に挿入され、残りは右の兄弟に送られます。^[14]（新しく挿入されたキーは、3 つの場所のいずれかになる可能性があります。）右の兄弟がいっぱいで、左の兄弟がいっぱいでない場合の状況は類似しています。^[14]兄弟ノードが両方ともいっぱいになると、2つのノード（現在のノードと兄弟）が3つに分割され、もう1つのキーがツリーの上の親ノードに移動します。^[14]親がいっぱいになると、スピル/分割操作はルートノードに向かって伝播します。^[14]ただし、ノードの削除は挿入よりもやや複雑です。
• B ^*+ツリーは、メインのB+ツリーとB ^*ツリーの機能を組み合わせたものです。^[15]
• Bツリーは順序統計ツリーに変換することができ、キー順でN番目のレコードを高速に検索したり、任意の2つのレコード間のレコード数を数えたり、その他さまざまな関連操作を行うことができます。^[16]

ソートおよび検索アルゴリズムは、順序表記法を使用して実行する必要がある比較操作の数によって特徴付けることができます。たとえば、Nレコードを含むソートされたテーブルのバイナリ検索は、およそ⌈ log ₂ N ⌉回の比較で実行できます。テーブルに 1,000,000 レコードがある場合、特定のレコードは最大 20 回の比較で見つけることができます: ⌈ log ₂ (1,000,000) ⌉ = 20。

大規模データベースは、歴史的にディスク ドライブに保存されてきました。ディスク ドライブ上のレコードの読み取り時間は、シーク時間と回転遅延のため、レコードが利用可能になった後にキーを比較するために必要な時間よりはるかに長くなります。シーク時間は 0 ～ 20 ミリ秒以上になる場合があり、回転遅延は平均して回転周期の約半分です。7200 RPM ドライブの場合、回転周期は 8.33 ミリ秒です。Seagate ST3500320NS などのドライブの場合、トラック間のシーク時間は 0.8 ミリ秒で、平均読み取りシーク時間は 8.5 ミリ秒です。^[17]簡単にするために、ディスクからの読み取りには約 10 ミリ秒かかると仮定します。

上記の例で 100 万件のレコードのうち 1 件を見つけるのにかかる時間は、ディスク読み取り 20 回 × ディスク読み取り 1 回あたり 10 ミリ秒、つまり 0.2 秒になります。

個々のレコードがディスクブロックにグループ化されるため、検索時間が短縮されます。 ディスク ブロックは 16 キロバイトです。各レコードが 160 バイトの場合、各ブロックに 100 レコードを保存できます。 上記のディスク読み取り時間は、実際にはブロック全体の時間です。 ディスク ヘッドが所定の位置に配置されると、1 つ以上のディスク ブロックをほとんど遅延なく読み取ることができます。 ブロックあたり 100 レコードの場合、最後の 6 回程度の比較ではディスク読み取りを行う必要はなく、比較はすべて最後のディスク ブロック読み取り内で行われます。

検索をさらに高速化するには、最初の 13 ～ 14 回の比較 (それぞれディスク アクセスが必要) にかかる時間を短縮する必要があります。

B ツリーインデックスを使用すると、パフォーマンスを向上させることができます。B ツリー インデックスは、データベースを固定サイズのブロックまたはページに分割する、マルチレベルのツリー構造を作成します。このツリーの各レベルは、アドレス位置を介してそれらのページをリンクするために使用でき、1 つのページ (ノードまたは内部ページと呼ばれる) が最下位レベルのリーフ ページを持つ別のページを参照できるようにします。1 つのページは通常、ツリーの開始点、つまり「ルート」です。これは、特定のキーの検索が開始される場所であり、リーフで終了するパスをたどります。この構造のほとんどのページは、特定のテーブル行を参照するリーフ ページになります。

各ノード (または内部ページ) は 3 つ以上の子を持つことができるため、B ツリー インデックスの高さ (ルートから最も遠いリーフまでの距離) は通常、バイナリ検索ツリーよりも短くなります。上記の例では、最初のディスク読み取りによって検索範囲が 2 分の 1 に狭められています。これは、各ディスク ブロックの最初のレコードを含む補助インデックス (スパース インデックスと呼ばれることもあります) を作成することで改善できます。この補助インデックスは元のデータベースの 1% のサイズになりますが、すばやく検索できます。補助インデックスのエントリが見つかると、メイン データベースで検索するブロックがわかります。補助インデックスを検索した後は、メイン データベースのその 1 つのブロックのみを検索すればよく、ディスク読み取りが 1 回多く必要になります。

上記の例では、インデックスには 10,000 エントリが保持され、結果を返すのに最大 14 回の比較が必要です。メイン データベースと同様に、補助インデックスの最後の 6 回程度の比較は同じディスク ブロック上にあります。インデックスは約 8 回のディスク読み取りで検索でき、目的のレコードには 9 回のディスク読み取りでアクセスできます。

補助インデックスの作成を繰り返すことで、補助インデックスに対する補助インデックスを作成できます。これにより、100 エントリのみを必要とし、1 つのディスク ブロックに収まる補助補助インデックスが作成されます。

目的のレコードを見つけるために 14 個のディスク ブロックを読み取る代わりに、3 個のブロックを読み取るだけで済みます。このブロック化は、ディスク ブロックがレベルの階層を埋めてインデックスを構成する B ツリーの作成の背後にある中核的な考え方です。ツリーのルートである aux-aux インデックスの最初の (そして唯一の) ブロックを読み取って検索すると、下のレベルの aux-index 内の関連ブロックが識別されます。その aux-index ブロックを読み取って検索すると、読み取る関連ブロックが識別され、リーフ レベルと呼ばれる最終レベルでメイン データベース内のレコードが識別されます。レコードを取得するのに必要な時間は、150 ミリ秒ではなく、わずか 30 ミリ秒です。

補助インデックスにより、検索問題は、およそlog ₂ N 回のディスク読み取りを必要とするバイナリ検索から、 log _b N 回のディスク読み取りのみを必要とする検索に変わりました。ここで、bはブロッキング係数です (ブロックあたりのエントリ数:この例では、ブロックあたりb = 100エントリ、 log ₁₀₀ 1,000,000 = 3 回の読み取り)。

実際には、メインデータベースが頻繁に検索される場合、補助補助インデックスと補助インデックスの大部分はディスクキャッシュに存在する可能性があるため、ディスク読み取りは発生しません。Bツリーは、ほとんどすべてのリレーショナルデータベースで標準的なインデックス実装であり、多くの非リレーショナルデータベースでも使用されています。^[18]

データベースが変更されない場合、インデックスのコンパイルは簡単に実行でき、インデックスを変更する必要はありません。変更があった場合は、データベースとそのインデックスの管理に追加の計算が必要になります。

データベースからレコードを削除するのは比較的簡単です。インデックスはそのままで、レコードを削除済みとしてマークするだけです。データベースはソートされた順序のままです。怠惰な削除が多数ある場合、検索と保存の効率が低下します。^[19]

挿入は、挿入するレコードのためのスペースを確保する必要があるため、ソートされた順次ファイルでは非常に遅くなることがあります。最初のレコードの前にレコードを挿入するには、すべてのレコードを 1 つ下に移動する必要があります。このような操作はコストがかかりすぎるため、実用的ではありません。1 つの解決策は、スペースを残すことです。すべてのレコードをブロックに密集させる代わりに、ブロックに空きスペースを残して、後続の挿入を可能にします。これらのスペースは、「削除された」レコードであるかのようにマークされます。

ブロックに空きスペースがある限り、挿入と削除はどちらも高速です。挿入がブロックに収まらない場合は、近くのブロックの空きスペースを見つけて補助インデックスを調整する必要があります。最良のケースは、近くに十分なスペースがあり、ブロックの再編成を最小限に抑えられることです。または、順序どおりでないディスクブロックを使用することもできます。^[18]

B ツリーは、上記のすべてのアイデアを活用します。特に、B ツリーは次のようになります。

• 順次走査のためにキーをソートした順序で保持する
• 階層型インデックスを使用してディスク読み取り回数を最小限に抑えます
• 部分的に満たされたブロックを使用して、挿入と削除を高速化します。
• 再帰アルゴリズムでインデックスのバランスを保つ

さらに、Bツリーは内部ノードが少なくとも半分は満たされていることを確認することで無駄を最小限に抑えます。Bツリーは任意の数の挿入と削除を処理できます。^[18]

h ≥ –1 を従来の B ツリーの高さとします (ツリーの高さの定義については、ツリー (データ構造) § 用語を参照してください) 。n ≥ 0をツリーのエントリ数とします。mをノードが持つことができる子の最大数とします。各ノードは最大でm −1個のキーを持つことができます。

高さhの B ツリーのすべてのノードが完全に埋められた場合、エントリはn = m ^{h +1} –1個になることが(たとえば帰納法によって) 示されます。したがって、B ツリーの最適な高さ (つまり最小の高さ) は次のようになります。

${\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}$

内部（非ルート）ノードが持つ必要のある子の最小数を とする。通常のBツリーの場合、${\displaystyle d}$${\displaystyle d=\left\lceil m/2\right\rceil .}$

Comer (1979)とCormen et al. (2001)は、Bツリーの最悪のケースの高さ（最大の高さ）を次のように示している^[20]

${\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}$

検索は、バイナリ検索ツリーの検索に似ています。ルートから始まり、ツリーは上から下まで再帰的にトラバースされます。各レベルで、検索の視野は、検索値を含む範囲を持つ子ポインタ (サブツリー) に縮小されます。サブツリーの範囲は、親ノードに含まれる値またはキーによって定義されます。これらの制限値は、分離値とも呼ばれます。

バイナリ検索は通常 (必ずしもそうとは限りませんが) ノード内で使用され、対象の分離値と子ツリーを見つけます。

すべての挿入はリーフ ノードから始まります。新しい要素を挿入するには、ツリーを検索して、新しい要素を追加するリーフ ノードを見つけます。次の手順で、そのノードに新しい要素を挿入します。

1. ノードに含まれる要素数が最大許容数より少ない場合、新しい要素のためのスペースがあります。ノードの要素の順序を維持したまま、新しい要素をノードに挿入します。
2. それ以外の場合は、ノードがいっぱいなので、次のように 2 つのノードに均等に分割します。
   1. リーフの要素と挿入される新しい要素の中から 1 つの中央値が選択されます。
   2. 中央値より小さい値は新しい左ノードに配置され、中央値より大きい値は新しい右ノードに配置され、中央値は分離値として機能します。
   3. 分離値はノードの親に挿入され、ノードが分割されるなどの原因となる場合があります。ノードに親がない場合 (つまり、ノードがルートだった場合)、このノードの上に新しいルートを作成します (ツリーの高さが増加します)。

分割がルートまで続く場合、単一のセパレータ値と 2 つの子を持つ新しいルートが作成されます。これが、内部ノードのサイズの下限がルートには適用されない理由です。 ノードあたりの要素の最大数はU −1 です。ノードが分割されると、1 つの要素が親に移動しますが、1 つの要素が追加されます。したがって、最大数U −1 の要素を 2 つの正当なノードに分割できる必要があります。この数が奇数の場合、U =2 Lであり、新しいノードの 1 つは ( U −2)/2 = L −1 個の要素を含むため正当なノードであり、もう 1 つはもう 1 つの要素を含むため正当なノードです。U −1 が偶数の場合、U =2 L −1 であるため、ノードには2 L −2 個の要素があります。この数の半分はL −1 であり、これはノードごとに許可される要素の最小数です。

代替アルゴリズムは、ルートから挿入が行われるノードまでツリーを 1 回通過し、途中で遭遇した完全なノードを事前に分割することをサポートします。これにより、ノードが二次ストレージにある場合にコストがかかる可能性がある、親ノードをメモリに呼び戻す必要がなくなります。ただし、このアルゴリズムを使用するには、新しい要素を追加せずに、1 つの要素を親に送信し、残りのU −2 要素を 2 つの有効なノードに分割できる必要があります。これには、 U = 2 L −1ではなくU = 2 L が必要です。これが、一部の^{[ which? ]}教科書が B ツリーの定義でこの要件を課す理由です。

B ツリーからの削除には、2 つの一般的な戦略があります。

1. アイテムを見つけて削除し、不変条件を保持するようにツリーを再構築するか、
2. ツリーを1回下って進みますが、ノードに入る（訪問する）前にツリーを再構築して、削除するキーに遭遇したら、それ以上の再構築を必要とせずに削除できるようにします。

以下のアルゴリズムは前者の戦略を使用します。

要素を削除するときに考慮すべき 2 つの特殊なケースがあります。

1. 内部ノード内の要素は、その子ノードの区切りとなる。
2. 要素を削除すると、そのノードは要素と子の最小数以下になる場合があります。

これらのケースの手順は以下のとおりです。

1. 削除する値を検索します。
2. 値がリーフ ノード内にある場合は、ノードから値を削除するだけです。
3. アンダーフローが発生した場合は、以下の「削除後の再バランス調整」のセクションで説明されているようにツリーを再バランス調整します。

内部ノードの各要素は 2 つのサブツリーの分離値として機能するため、分離の代替を見つける必要があります。左のサブツリーの最大要素は、依然としてセパレーターより小さいことに注意してください。同様に、右のサブツリーの最小要素は、依然としてセパレーターより大きいです。これらの要素は両方ともリーフ ノードにあり、どちらかが 2 つのサブツリーの新しいセパレーターになることができます。アルゴリズムは次のように説明されます。

1. 新しいセパレーター (左のサブツリー内の最大要素または右のサブツリー内の最小要素) を選択し、それが含まれているリーフ ノードから削除し、削除する要素を新しいセパレーターに置き換えます。
2. 前の手順では、リーフ ノードから要素 (新しいセパレーター) が削除されました。そのリーフ ノードに不足がある場合 (必要なノード数より少ない場合)、リーフ ノードからツリーのバランスを再調整します。

再バランス調整はリーフから始まり、ツリーのバランスが取れるまでルートに向かって進みます。ノードから要素を削除して最小サイズを下回った場合、すべてのノードを最小サイズにするために一部の要素を再配分する必要があります。通常、再配分には、最小数を超えるノードを持つ兄弟ノードからの要素の移動が含まれます。この再配分操作はローテーションと呼ばれます。兄弟が要素を節約できない場合、不足しているノードを兄弟とマージする必要があります。マージにより、親はセパレーター要素を失うため、親が不足し、再バランス調整が必要になる場合があります。マージと再バランス調整は、ルートまで続く場合があります。最小要素数はルートには適用されないため、ルートが唯一の不足ノードになることは問題ではありません。ツリーを再バランス調整するアルゴリズムは次のとおりです。

• 欠陥ノードの右兄弟が存在し、最小要素数を超える場合は、左に回転します。
  1. 親から不足ノードの末尾にセパレータをコピーします（セパレータは下に移動します。不足ノードの要素数は最小になります）。
  2. 親のセパレーターを右兄弟の最初の要素に置き換えます (右兄弟は 1 つのノードを失いますが、少なくとも最小数の要素が残っています)
  3. 木はバランスが取れました
• それ以外の場合、欠陥ノードの左の兄弟が存在し、最小要素数を超える場合は、右に回転します。
  1. 親から欠損ノードの先頭にセパレータをコピーします（セパレータは下に移動します。欠損ノードの要素数は最小になります）。
  2. 親のセパレーターを左の兄弟の最後の要素に置き換えます (左の兄弟は 1 つのノードを失いますが、少なくとも最小数の要素が残っています)
  3. 木はバランスが取れました
• それ以外の場合、両方の直下の兄弟が最小数の要素しか持たない場合は、親から取り除いたセパレータを挟んだ兄弟とマージします。
  1. セパレータを左ノードの末尾にコピーします（左ノードは不足ノードの場合もあれば、要素数が最小の兄弟の場合もあります）。
  2. すべての要素を右ノードから左ノードに移動します（左ノードには最大数の要素があり、右ノードは空です）
  3. 親からセパレーターを削除し、その右側の空の子も削除します（親は要素を失います）
     • 親がルートであり、現在要素がない場合は、それを解放し、マージされたノードを新しいルートにします（ツリーは浅くなります）
     • そうでなければ、親に必要な要素数より少ない要素しかない場合は、親のバランスを再調整する^[21]

注: 再バランス調整操作は、B+ ツリー (例: 親がキーのコピーを持っているため回転が異なります) と B ^*ツリー (例: 3 つの兄弟が 2 つの兄弟にマージされます) では異なります。

新しくロードされたデータベースは良好なシーケンシャル動作を示す傾向がありますが、データベースが大きくなるにつれてこの動作を維持することがますます困難になり、ランダムI/Oとパフォーマンスの課題が増加します。^[22]

よくある特殊なケースは、大量の事前ソートされたデータを最初は空の B ツリーに追加することです。一連の連続した挿入を単純に実行することは可能ですが、ソートされたデータを挿入すると、ほぼ完全に半分満たされたノードで構成されるツリーが生成されます。代わりに、特別な「バルク ロード」アルゴリズムを使用して、より高い分岐係数を持つより効率的なツリーを作成できます。

入力がソートされると、すべての挿入はツリーの右端で行われ、特にノードが分割されるたびに、左半分にそれ以上の挿入が行われないことが保証されます。一括読み込みの際には、これを利用し、いっぱいになったノードを均等に分割するのではなく、できるだけ不均等に分割します。つまり、左のノードを完全にいっぱいにして、キーが 0 個で子が 1 個ある右のノードを作成します (通常の B ツリー ルールに違反します)。

一括ロードの終了時には、ツリーはほぼ完全に満杯のノードで構成されます。各レベルの右端のノードのみが満杯未満になる可能性があります。これらのノードも半分未満になる可能性があるため、通常の B ツリー ルールを再確立するには、これらのノードを (確実に満杯になる) 左側の兄弟ノードと結合し、キーを分割して少なくとも半分満杯の 2 つのノードを生成します。左側の兄弟ノードが満杯でない唯一のノードはルートであり、ルートは半分未満でもかまいません。

データベースでの使用に加えて、B ツリー (または § バリアント) は、特定のファイル内の任意のブロックへの迅速なランダム アクセスを可能にするために、ファイル システムでも使用されます。基本的な問題は、ファイル ブロックアドレスをディスク ブロック アドレスに変換することです。 ${\displaystyle i}$

一部のオペレーティング システムでは、ファイルの作成時にユーザーがファイルの最大サイズを割り当てる必要があります。ファイルは連続したディスク ブロックとして割り当てられます。その場合、ファイル ブロック アドレスをディスク ブロック アドレスに変換するために、オペレーティング システムはファイル ブロック アドレスを、ファイルを構成する最初のディスク ブロックのアドレスに追加するだけです。この仕組みは単純ですが、ファイルは作成されたサイズを超えることはできません。 ${\displaystyle i}$${\displaystyle i}$

他のオペレーティング システムでは、ファイルの拡張が許可されます。その結果、ディスク ブロックが連続しない可能性があるため、論理ブロックを物理ブロックにマッピングすることはより複雑になります。

たとえば、MS-DOS は単純なファイル アロケーション テーブル(FAT) を使用していました。FAT には各ディスク ブロックのエントリがあり^{[注 1]}、そのエントリはブロックがファイルによって使用されているかどうか、使用されている場合はどのブロック (ある場合) が同じファイルの次のディスク ブロックであるかを識別します。したがって、各ファイルの割り当てはテーブル内のリンク リストとして表されます。ファイル ブロックのディスク アドレスを見つけるには、オペレーティング システム (またはディスク ユーティリティ) は FAT 内のファイルのリンク リストを順番にたどる必要があります。さらに悪いことに、空きディスク ブロックを見つけるには、FAT を順番にスキャンする必要があります。MS-DOS の場合、ディスクとファイルが小さく、FAT のエントリが少なく、ファイル チェーンが比較的短かったため、これは大きなペナルティではありませんでした。FAT12 ファイル システム (フロッピー ディスクや初期のハード ディスクで使用) では、エントリは 4,080 個以下で^{[注 2]}、FAT は通常メモリ内に常駐していました。ディスクが大きくなるにつれて、FAT アーキテクチャはペナルティに直面し始めました。 FAT を使用する大容量ディスクでは、読み取りまたは書き込みの対象となるファイル ブロックのディスク上の位置を確認するために、ディスク読み取りを実行する必要がある場合があります。 ${\displaystyle i}$

TOPS-20 (およびおそらくTENEX ) は、B ツリーに類似した 0 ～ 2 レベルのツリーを使用しました^[要出典]。ディスク ブロックは 512 個の 36 ビット ワードでした。ファイルが 512 (2 ⁹ ) ワード ブロックに収まる場合、ファイル ディレクトリはその物理ディスク ブロックを指します。ファイルが 2 ¹⁸ワードに収まる場合、ディレクトリは補助インデックスを指します。そのインデックスの 512 ワードは NULL (ブロックが割り当てられていない) になるか、ブロックの物理アドレスを指します。ファイルが 2 ^{27ワードに収まる場合、ディレクトリは補助補助インデックスを保持するブロックを指します。各エントリは NULL になるか、補助インデックスを指します。その結果、2 27}ワード ファイルの物理ディスク ブロックは、2 回のディスク読み取りで見つけられ、3 回目で読み取られます。

AppleのファイルシステムHFS+とAPFS、MicrosoftのNTFS、^[23] AIX（jfs2）、およびBcachefs、Btrfs、ext4などの一部のLinuxファイルシステムはBツリーを使用します。

B ^{*ツリーは、} HFSおよびReiser4 ファイル システムで使用されます。

DragonFly BSDのHAMMERファイルシステムは修正されたB+ツリーを使用しています。^[24]

B ツリーは、リンク リストの線形性よりも、データ量の増加とともに遅くなります。スキップ リストと比較すると、両方の構造のパフォーマンスは同じですが、 B ツリーはn の増加に対してより適切にスケーリングされます。メイン メモリ データベースシステム 用のT ツリーは似ていますが、よりコンパクトです。

Lehman と Yao ^{[25] は、}各レベルのツリー ブロックを「次の」ポインタでリンクすることで、すべての読み取りロックを回避できる (したがって同時アクセスが大幅に改善される) ことを示しました。これにより、挿入操作と検索操作の両方がルートからリーフに降りるツリー構造が実現します。書き込みロックは、ツリー ブロックが変更されるときにのみ必要になります。これにより、複数のユーザーによる同時アクセスが最大化されます。これは、データベースやその他の B ツリー ベースのISAMストレージ メソッドにとって重要な考慮事項です。この改善に伴うコストは、通常の操作中に空のページを B ツリーから削除できないことです。(ただし、ノードのマージを実装するためのさまざまな戦略については^[26]を参照し、ソース コードは^[27]を参照してください)

1994 年に付与された米国特許 5283894 は、ロックなしで B+ ツリーの同時アクセスと変更を可能にする「メタ アクセス メソッド」^[28]を使用する方法を示しているようです。この技術は、ブロック キャッシュの各レベルのブロックを指す追加のメモリ内インデックスを使用して、検索と更新の両方でツリーを「上向き」にアクセスします。削除のための再編成は必要なく、Lehman と Yao のように各ブロックに「次の」ポインタはありません。

B ツリーは構造が赤黒ツリーに似ているため、赤黒ツリーの並列アルゴリズムをB ツリーにも適用できます。

メープルツリーは、 Linuxカーネルで仮想メモリ管理におけるロック競合を減らすために開発されたBツリーです。 ^{[29] [30] [31]}

(a,b)-ツリーは B-ツリーの一般化です。B-ツリーでは、各内部ノードに最小 個の子と最大 個の子 (それぞれ の事前設定値)が必要です。対照的に、(a,b)-ツリーでは、内部ノードの最小子数を任意に低く設定できます。(a,b)-ツリーでは、各内部ノードにa～b個の子 (それぞれ の事前設定値aとb )があります。 ${\displaystyle \lfloor K/2\rfloor +1}$${\displaystyle K}$${\displaystyle K}$

• B+ツリー
• Rツリー
• 赤黒木
• 2～3本の木
• 2–3–4 木

 この記事には、 Paul E. Blackのパブリック ドメイン資料が組み込まれています。「(a,b)-tree」。アルゴリズムとデータ構造の辞書。NIST 。

• Bayer, R. ; McCreight, E. (1972). 「大規模順序付けインデックスの構成と保守」(PDF) . Acta Informatica . 1 (3): 173–189. doi :10.1007/bf00288683. S2CID  29859053.。
• Comer, Douglas (1979年6 月)。「ユビキタス B ツリー」。コンピューテ ィング調査。11 (2): 123–137。doi : 10.1145 / 356770.356776。ISSN 0360-0300。S2CID 101673  。。
• トーマス・コーメン;チャールズ・ライザーソン;ロナルド・リベスト;スタイン、クリフォード(2001)。アルゴリズム入門(第 2 版)。 MIT プレスとマグロウヒル。 434–454ページ。ISBN 0-262-03293-7。第 18 章: B ツリー。
• Folk, Michael J.; Zoellick, Bill (1992)。ファイル構造(第 2 版)。Addison- Wesley。ISBN 0-201-55713-4。。
• Knuth, Donald (1998)。『ソートと検索。コンピュータプログラミングの技法。第 3 巻 (第 2 版)。Addison- Wesley。ISBN 0-201-89685-0。セクション 6.2.4: マルチウェイ ツリー、481 ～ 491 ページ。また、セクション 6.2.3 (バランス ツリー) の 476 ～ 477 ページでは、2 ～ 3 ツリーについて説明しています。

• バイエル、ルドルフ、マクリート、E.（1970 年 7 月）、大規模順序付けインデックスの構成と保守、数学および情報科学レポート第 20 巻、ボーイング科学研究所。
• Bayer, Rudolf (1971)。「仮想メモリ用のバイナリ B ツリー」。1971 ACM-SIGFIDET ワークショップ「データ記述、アクセス、および制御」の議事録。カリフォルニア州サンディエゴ。。

• SJSU の David Scot Taylor による B ツリー講義
• B ツリーの視覚化 (「init」をクリック)
• アニメーション化された B ツリーの視覚化
• Scholarpedia の B ツリーと UB ツリー キュレーター: Dr Rudolf Bayer
• B ツリー: バランスのとれたツリー データ構造 2010-03-05 にWayback Machineにアーカイブされました
• NIST のアルゴリズムとデータ構造の辞書: B ツリー
• Bツリーチュートリアル
• InfinityDB BTreeの実装
• キャッシュオブリビアス B(+) ツリー
• アルゴリズムとデータ構造の辞書の B*-tree の項目
• オープン データ構造 - セクション 14.2 - B ツリー、Pat Morin
• カウントされた B ツリー
• B-Tree .Net、最新の仮想化 RAM およびディスク実装

一括読み込み

• Shetty, Soumya B. (2010)。ユーザーが設定可能な B ツリーの実装 (論文)。アイオワ州立大学。
• Kaldırım, Semih (2015 年 4 月 28 日). 「ファイル編成、ISAM、B+ ツリー、一括読み込み」(PDF)。トルコ、アンカラ:ビルケント大学。pp. 4–6。2022年 10 月 9 日のオリジナルからアーカイブ(PDF) 。
• 「ECS 165B: データベースシステムの実装: 講義 6」(PDF)。カリフォルニア大学デービス校。2010 年 4 月 9 日。p. 23。2022年 10 月 9 日のオリジナルからアーカイブ(PDF) 。
• 「SQL Server 2017 での BULK INSERT (Transact-SQL)」。Microsoft Docs。2018 年 9 月 6 日。