Bツリーとバイナリツリーの違い
コンテンツ
Bツリーとバイナリツリーは、非線形データ構造のタイプです。用語は似ているように見えますが、すべての面で異なっています。 RAMのアクセス速度はディスクよりもはるかに速いため、レコードまたはデータがディスクではなくRAMに格納される場合、バイナリツリーが使用されます。一方、Bツリーは、データがディスクに保存されるときに使用され、ツリーの高さを減らし、ノード内のブランチを増やすことでアクセス時間を短縮します。
Bツリーとバイナリツリーのもう1つの違いは、Bツリーにはすべての子ノードが同じレベルになければならないのに対して、バイナリツリーにはそのような制約がないことです。 2進ツリーには最大2つのサブツリーまたはノードを含めることができますが、BツリーではサブツリーまたはノードをM個持つことができます。ここで、MはBツリーの順序です。
- 比較表
- 定義
- 主な違い
- 結論
比較表
| 比較の根拠 | Bツリー | 二分木 |
|---|---|---|
| 本質的な制約 | ノードは最大M個の子ノードを持つことができます（Mはツリーの順序です）。 | ノードは最大2つのサブツリーを持つことができます。 |
| 中古 | データがディスクに保存されるときに使用されます。 | レコードとデータがRAMに保存されるときに使用されます。 |
| 木の高さ | ログM N（mはM-wayツリーの順序） | ログ2 N |
| 応用 | 多くのDBMSのコードインデックスデータ構造。 | コードの最適化、ハフマンコーディングなど |
Bツリーの定義
Bツリーは、バランスの取れたMウェイツリーであり、バランスの取れたソートツリーとしても知られています。これは、ノードが順序通りのトラバーサルに基づいて編成されるバイナリ検索ツリーに似ています。 Bツリーのスペースの複雑さはO（n）です。挿入および削除の時間の複雑さはO（log n）です。
Bツリーに当てはまる特定の条件があります。
- 木の高さは、可能な限り最小でなければなりません。
- ツリーの葉の上には、空のサブツリーがあってはなりません。
- 木の葉は同じレベルでなければなりません。
- すべてのノードには、Leaveノードを除く、最小数の子が必要です。
次数MのBツリーのプロパティ
- 各ノードには、最大M個の子と最小M / 2個の子、または2から最大の任意の数を含めることができます。
- 各ノードには、最大M-1キーを持つ子より1つ少ないキーがあります。
- キーの配列は、ノード内で特定の順序になっています。キーの左側にあるサブツリー内のすべてのキーはキーの先行バージョンであり、キーの右側にあるサブキーは後続バージョンと呼ばれます。
- フルノードの挿入時に、ツリーは2つの部分に分割され、中央値を持つキーが親ノードに挿入されます。
- ノードが削除されると、マージ操作が行われます。
二分木の定義
バイナリツリーは、子ノードに対して最大2つのポインタを持つことができるツリー構造です。これは、ノードが持つことができる最高次数が2であり、ゼロまたは1度のノードも存在する可能性があることを意味します。
厳密な二分木、完全な二分木、拡張二分木など、二分木の特定の変形があります。
- 厳密な二分木は、各非終端ノードが左サブツリーと右サブツリーを持たなければならないツリーです。
- ツリーは、2つの条件を満たした場合、完全なバイナリツリーと呼ばれます。 私 各レベルのノード（iはレベル）。
- スレッドバイナリは、0個のノードまたは2個のノードで構成されるバイナリツリーです。
トラバーサルテクニック
ツリートラバーサルは、ツリーデータ構造で実行される最も頻繁な操作の1つであり、各ノードが体系的に1回だけアクセスします。
- 順序-このツリートラバーサルでは、左側のサブツリーが再帰的に訪問され、次にルートノードが訪問され、最後の右側のサブツリーが訪問されます。
- Preorer-このツリートラバーサルでは、ルートノードが最初に、次に左のサブツリーで、最後に右のサブツリーでアクセスされます。
- 後順-この手法は、左のサブツリー、次に右のサブツリー、最後のルートノードを訪問します。
- Bツリーでは、非終端ノードが持つことができる子ノードの最大数はMです。ここで、MはBツリーの順序です。一方、バイナリツリーには最大2つのサブツリーまたは子ノードを含めることができます。
- Bツリーは、データがディスクに保存されるときに使用され、バイナリツリーは、データがRAMなどの高速メモリに保存されるときに使用されます。
- Bツリーのもう1つの応用分野は、DBMSのコードインデックスデータ構造です。これに対して、バイナリツリーはコードの最適化、ハフマンコーディングなどで使用されます。
- Bツリーの最大の高さはlogですMN（Mはツリーの順序）。反対に、バイナリツリーの最大の高さはlogです2N（Nはノードの数であり、ベースはバイナリであるため2です）。
結論
Bツリーはバイナリおよびバイナリ検索ツリーで使用されます。これの主な理由は、CPUが高帯域幅チャネルでキャッシュに接続され、CPUが低帯域幅チャネルでディスクに接続されるメモリ階層です。レコードがRAMに格納される場合（小さくて高速）にバイナリツリーが使用され、レコードがディスクに格納される場合に（大規模で低速）Bツリーが使用されます。したがって、分岐係数が高く、ツリーの高さが低いため、バイナリツリーの代わりにBツリーを使用すると、アクセス時間が大幅に短縮されます。
