Bツリーとバイナリツリーのもう1つの違いは、Bツリーはその子ノードをすべて同じレベルに持つ必要があるのに対し、バイナリツリーにはそのような制約がないことです。 二分木は最大２つの部分木またはノードを持つことができるのに対し、Ｂ木ではＭ個の部分木またはノードを持つことはできず、ＭはＢ木の次数である。
比較表
| 比較基準 | Bツリー | 二分木 |
|---|---|---|
| 本質的な制約 | ノードは最大M個の子ノードを持つことができます（Mはツリーの次数です）。 | 1つのノードは最大2つのサブツリーを持つことができます。 |
| 中古 | データがディスクに保存されるときに使用されます。 | レコードやデータがRAMに保存されるときに使用されます。 |
| 木の高さ | log M N（mはM-wayツリーの位数） | log 2 N |
| 応用 | 多くのDBMSにおけるコード索引付けデータ構造。 | コード最適化、ハフマンコーディングなど |
Bツリーの定義
Bツリーはバランスの取れたMウェイツリーで、バランスソートツリーとも呼ばれます。 これは、ノードがinorder traversalに基づいて編成されている二分探索木に似ています。 Bツリーの空間複雑度はO（n）です。 挿入と削除の時間の複雑さはO（log n）です。
Bツリーに当てはまる必要がある特定の条件があります。
- 木の高さはできるだけ最小になるようにしてください。
- 木の葉の上には、空のサブツリーがあってはいけません。
- 木の葉は同じ高さになければなりません。
- すべてのノードは、離脱ノードを除いて、最小数の子を持つべきです。
M次のB木の性質
- 各ノードは、最大M個の子と最小M / 2個の子、または2から最大の任意の数の子を持つことができます。
- 各ノードは、最大M-1個のキーを持つ子より1つ少ないキーを持ちます。
- キーの配置はノード内で特定の順序になっています。 キーの左側に存在するサブツリー内のすべてのキーはキーの先行操作であり、キーの右側に存在するものは後続操作と呼ばれます。
- フルノードの挿入時に、ツリーは2つの部分に分割され、中央値を持つキーが親ノードに挿入されます。
- ノードが削除されると、マージ操作が行われます。
二分木の定義
二分木は、その子ノードに対して最大2つのポインタを持つことができる木構造です。 つまり、ノードが持つことができる最高度は2で、ゼロ度または1度のノードもあり得るということです。
厳密な二分木、完全二分木、拡張二分木など、二分木の特定の変形がある。
- 厳密に二分木とは、各非終端ノードが左部分木と右部分木を持っていなければならない木です。
- ツリーが各レベルに2 i個のノードを持つという条件を満たす場合、そのツリーはComplete Binaryツリーと呼ばれます。ここで、iはレベルです。
- スレッド化されたバイナリは、0のノード数または2の数のノードからなるバイナリツリーです。
トラバーサルテクニック
ツリー走査は、各ノードが系統的に1回だけ訪れたツリーデータ構造に対して実行される最も頻繁な操作の1つです。
- 順序付け - このツリートラバーサルでは、左のサブツリーが再帰的に訪問され、次にルートノードが訪問され、最後の右でサブツリーが訪問されます。
- Preorer - このツリーのトラバースでは、ルートノードが最初に訪問され、次に左側のサブツリーと最後の右側のサブツリーに移動します。
- ポストオーダー - この技法は、左のサブツリーを訪問し、次に右のサブツリーを訪問し、最後のルートノードを訪問します。
Bツリーとバイナリツリーの主な違い
- Bツリーでは、非終端ノードが持つことができる子ノードの最大数はMです。ここでMはBツリーの次数です。 一方、バイナリツリーは、最大2つのサブツリーまたは子ノードを持つことができます。
- Bツリーはデータがディスクに格納されるときに使用され、バイナリツリーはデータがRAMのような高速メモリに格納されるときに使用されます。
- Ｂツリーの他の適用分野は、ＤＢＭＳにおけるコード索引付けデータ構造であり、対照的に、バイナリツリーは、コード最適化、ハフマン符号化などにおいて使用される。
- Bツリーの最大の高さはlog M Nです（Mはツリーの次数です）。 それとは対照的に、二分木の最大の高さはlog 2 Nです（Nはノードの数で、baseは2のため2です）。
結論
Bツリーはバイナリおよびバイナリサーチツリーで使用されています。この主な理由は、CPUが高帯域幅チャネルでキャッシュに接続され、CPUが低帯域幅チャネルでディスクに接続されているメモリ階層です。 レコードがRAMに格納されている（小さいものと速い）場合はバイナリツリーが使用され、レコードがディスクに格納される場合（大きいものと遅い）はBツリーが使用されます。 そのため、バイナリツリーの代わりにBツリーを使用すると、分岐係数が高くなり、ツリーの高さが減少するため、アクセス時間が大幅に短縮されます。
