Bツリー

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

BayerとMcCreight（1972）^{[ 5 ]} 、 Comer（1979）^{[ 2 ]}らは、Bツリーの次数を非ルートノードの最小キー数として定義している。FolkとZoellick ^{[ 11 ]}は、キーの最大数が不明確であるため、用語が曖昧であると指摘している。次数3のBツリーは、最大6個のキーを持つ場合もあれば、最大7個のキーを持つ場合もある。Knuth（1998）は、次数を子ノードの最大数（キーの最大数より1つ多い）として定義することで、この問題を回避している。^{[ 9 ]}

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

簡略化のため、ほとんどの著者は、ノードに収まる鍵の数が固定されていると仮定しています。基本的な仮定は、鍵のサイズとノードのサイズの両方が固定されているということです。実際には、可変長の鍵が使用される場合があります。^{[ 13 ]}

他の木構造と同様に、B木は、ルート、内部（別名：内部）、葉の3種類のノードの集合として表現できます。

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

• K - Bツリー内の各ノードにおける潜在的な検索キーの最大数。（この値はツリー全体で一定です。）
• pt _i - サブツリーを開始する子ノードへのポインタ。
• pr _i - データを格納するレコードへのポインタ。
• k _i - 0 から始まるノードインデックスiの検索キー。

Bツリーでは、これらのノードに対して以下の特性が維持されます。

• Bツリー内の任意のノードにk _iが存在する場合、 k _{i -1}はそのノードに存在し、${\displaystyle i\geq 1}$。
• すべてのリーフノードは同じ数の祖先を持つ（つまり、すべて同じ深さにある）。

Bツリー内の各内部ノードは、次の形式をとります。

Bツリーの各リーフノードは、次の形式をとります。

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

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

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

内部ノードが${\displaystyle 2d}$キー、次にそのノードにキーを追加するには、仮説上の${\displaystyle 2d+1}$キーノードを 2 つのdキーノードに分割し、中央にあったキーを親ノードに移動します。分割された各ノードには、必要な最小数のキーがあります。同様に、内部ノードとその隣接ノードがそれぞれdキーを持っている場合、キーを隣接ノードと結合することで、内部ノードからキーを削除できます。キーを削除すると、内部ノードには次のキーが存在します。${\displaystyle d-1}$キー。隣のノードに参加すると、d 個のキーと、隣のノードの親から引き継がれたもう 1 つのキーが追加されます。結果として、完全に満たされたノードになります。${\displaystyle 2d}$鍵。

Bツリーは、挿入後に過充填になりそうなノードを分割することによってバランスが保たれます。${\displaystyle 2d+1}$キーを 2 つのdキーの兄弟に分割し、中間値のキーを親に挿入します。深さはルートが分割されたときにのみ増加し、バランスが維持されます。同様に、B ツリーは、削除後も兄弟間でキーをマージまたは再分配して、ルート以外のノードのdキーの最小値を維持することにより、バランスが維持されます。マージにより親のキーの数が減り、場合によっては兄弟とのキーのマージまたは再分配が強制され、以下同様です。深さが変わるのは、ルートにdと (一時的に)の 2 つの子がある場合のみです。${\displaystyle d-1}$キーの場合、2 つの兄弟と親がマージされ、深さが 1 つ減少します。

ツリーに要素が追加されるにつれて、この深さは徐々に増加しますが、全体の深さが増加することはまれであり、結果としてすべての葉ノードが根からさらに1つ遠いノードになります。

子ノードの範囲が許容されるため、Bツリーは他の自己平衡型探索木ほど頻繁に再平衡化する必要はありませんが、ノードが完全に満たされていないため、いくらかのスペースが無駄になる可能性があります。

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

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

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

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

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

上記の例で100万件のレコードの中から1件を見つけるのに必要な時間は、ディスク読み取りを20回行い、1回あたり10ミリ秒かかるため、合計で0.2秒になります。

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

検索速度をさらに向上させるには、最初の13～14回の比較（それぞれディスクアクセスが必要）にかかる時間を短縮する必要がある。

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

各ノード（または内部ページ）は2つ以上の子を持つことができるため、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ツリーは、ほぼすべてのリレーショナルデータベースで標準的なインデックス実装であり、多くの非リレーショナルデータベースでも使用されています。^{[ 20 ]}

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

データベースからレコードを削除するのは比較的簡単です。インデックスはそのままにして、レコードを削除済みとしてマークするだけで済みます。データベースはソートされた状態を維持します。遅延削除が多数ある場合、検索とストレージの効率が低下します。^{[ 21 ]}

ソートされたシーケンシャルファイルでは、挿入するレコードのためのスペースを確保する必要があるため、挿入処理が非常に遅くなることがあります。最初のレコードの前にレコードを挿入するには、すべてのレコードを1つずつずらす必要があります。このような操作はコストが高すぎて実用的ではありません。解決策の一つは、スペースを空けておくことです。すべてのレコードをブロック内に密集させるのではなく、ブロック内に空きスペースを設けて、後続の挿入に対応できるようにします。これらのスペースは、「削除済み」レコードとしてマークされます。

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

Bツリーは、上記で説明したすべてのアイデアを使用します。具体的には、Bツリーは次のようになります。

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

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

検索は、二分探索木における検索と似ています。ルートから開始し、木は上から下へと再帰的に走査されます。各レベルで、検索対象は検索値を含む範囲を持つ子ポインタ（サブツリー）に絞り込まれます。サブツリーの範囲は、親ノードに含まれる値、つまりキーによって定義されます。これらの制限値は、分離値とも呼ばれます。

バイナリサーチは、通常（ただし必ずしもそうとは限らない）、ノード内で分離値と対象となる子ツリーを見つけるために使用されます。

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

1. ノードに含まれる要素数が許容される最大数よりも少ない場合は、新しい要素を挿入する余地があります。ノードの要素の順序を維持したまま、新しい要素をノードに挿入します。
2. そうでなければ、ノードが満杯なので、2つのノードに均等に分割します。
   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つの要素を親ノードに送信し、残りのU −2 個の要素を新しい要素を追加せずに 2 つの有効なノードに分割できる必要があります。これは、U = 2 LではなくU = 2 L −1 である必要があるため、一部の教科書で B ツリーを定義する際にこの要件が課されている理由となっています。

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

1. アイテムを見つけて削除し、ツリーを再構築して不変条件を保持するか、
2. ツリーを一度だけ走査しますが、ノードに入る（訪問する）前にツリーを再構築し、削除対象のキーが見つかった時点で、それ以上の再構築を必要とせずに削除できるようにします。

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

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

1. 内部ノード内の要素は、その子ノードを区切る役割を果たします。
2. 要素を削除すると、そのノードが要素数と子ノード数の最小値を下回る場合があります。

これらのケースに関する手続きは以下のとおりです。

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

よくある特殊なケースとして、大量のソート済みデータを、最初は空のBツリーに追加するケースが挙げられます。単純に連続して挿入操作を行うことも可能ですが、ソート済みデータを挿入すると、ほぼ半分しかデータが埋まっていないノードで構成されるツリーになってしまいます。そこで、より効率的で分岐率の高いツリーを生成するために、特別な「一括ロード」アルゴリズムを用いることができます。

入力がソートされている場合、すべての挿入はツリーの最右端で行われ、特にノードが分割されるたびに、左半分にはそれ以上の挿入が行われないことが保証されます。一括ロード時には、この特性を利用し、満杯になったノードを均等に分割する代わりに、できるだけ不均等に分割します。つまり、左側のノードを完全に満杯のままにしておき、右側のノードにはキーがゼロで子ノードが1つ作成します（これは通常のBツリーのルールに反します）。

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

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

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

B木は構造的に赤黒木と似ているため、赤黒木用の並列アルゴリズムをB木にも適用できる。

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

(a,b)-木はB-木の一般化です。B-木では、各内部ノードが最低限${\displaystyle \lfloor K/2\rfloor +1}$子供と最大${\displaystyle K}$子供、あるプリセット値${\displaystyle K}$対照的に、(a,b)-木では、内部ノードの最小子数を任意に低く設定できます。(a,b)-木では、各内部ノードは、あらかじめ設定されたaとbの値に対して、aからb個の子を持ちます。

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