メニュー

C ++でのBツリーとB +ツリーのデータ構造

b tree b tree data structure c

問題を排除するために楽器を試してください

このC ++チュートリアルでは、BツリーとB +ツリーのデータ構造について説明します。データ全体をメインメモリに保存できない場合に、データをディスクに保存するために使用されます。

Bツリーは、自己平衡型ツリーであると同時に、ディスクアクセスに使用される特殊なm-wayツリーです。

保存するデータ量が非常に多い場合、データ全体をメインメモリに保存することはできません。したがって、データをディスクに保存します。ディスクからのデータアクセスは、メインメモリアクセスに比べて時間がかかります。

ディスクに保存されているデータのキーの数が非常に多い場合、データは通常、ブロックの形式でアクセスされます。これらのブロックにアクセスする時間は、木の高さに正比例します。

=> 絶対C ++トレーニングシリーズについては、ここをクリックしてください。

BツリーとB +ツリー

学習内容：

C ++のBツリー

Bツリーはフラットツリーです。つまり、Bツリーの高さは最小限に抑えられます。代わりに、Bツリーの各ノードに同じ数のキーが配置されます。 Bツリーの高さを最小限に抑えることで、AVLツリーのような他のバランスの取れたツリーと比較してアクセスが高速になります。

典型的なBツリーを以下に示します。

Bツリーの例

経験豊富なDevOpsインタビューの質問と回答

通常、Bツリーのノードサイズはブロックサイズと同じに保たれます。

以下にリストされているのは、Bツリーのいくつかのプロパティです。

  • B木のすべての葉は同じレベルにあります。
  • 次数mのBツリーは、最大でm-1個のキーとm個の子を持つことができます。
  • Bツリーのすべてのノードには最大m個の子があります。
  • ルートノードには、少なくとも2つのノードが必要です。
  • ルートノードとリーフノードを除くすべてのノードには、m / 2の子が含まれています。

次に、Bツリーの基本的な操作のいくつかについて説明します。

Bツリーの基本操作

以下に、Bツリーの基本的な操作の一部を示します。

＃1）検索

Bツリーでの検索はBSTでの検索と似ています。上記のツリーで、項目3を探したい場合は、次のように進めます。

  • 3をルート要素と比較します。ここで、3<6 and 3 <15. So we proceed to the left subtree.
  • 左側のサブツリーの3と4を比較してください。 3として<4, we proceed to the left subtree of node 4.
  • 次のノードには、2と3の2つのキーがあります。3> 2、3 = 3。したがって、このノードでキーが見つかりました。見つかった場所に戻ります。

Bツリーでの検索は、ツリーの高さによって異なります。通常、特定のアイテムを検索するのにO（log n）の時間がかかります。

＃2）挿入

Bツリーへの新しいアイテムの挿入は、リーフノードレベルで行われます。

以下は、Bツリーに新しいアイテムを挿入するための一連の手順（アルゴリズム）です。

  • Bツリーをトラバースして、アイテムを挿入するリーフノードの場所を見つけます。
  • リーフノードにキーが含まれている場合
  • それ以外の場合、リーフノードキー= m-1の場合、次のようになります。
    • ますます多くのアイテムに新しいアイテムを挿入します。
    • ノードの中央値を取り、ノードを2つのノードに分割します。
    • 中央値をその親ノードにプッシュします。
    • 親ノードキー= m-1の場合、親ノードについても上記の手順を繰り返します。これは、適切なリーフノードが見つかるまで行われます。
  • 最後に、要素を挿入します。

以下のようにBツリーへの挿入を示しました。

以下に示すツリーにアイテム70を挿入しましょう。

アンドロイド用の無料mp3音楽ダウンロードアプリ

与えられたツリーの最小次数は「m」= 3です。したがって、各ノードは、その中に2 * m -1 = 5個のキーを収容できます。

Bツリーの挿入

ここで、アイテム70を挿入します。ノードに5つのキーを含めることができるため、要素70をルート要素30と比較します。70> 30なので、右側のサブツリーにアイテム70を挿入します。

右側のサブツリーには、キー40、50、60のノードがあります。各ノードには5つのキーを含めることができるため、このノード自体にアイテム70を挿入します。

挿入後、Bツリーは次のようになります。

挿入後のBツリー

＃3）削除

挿入と同様に、キーの削除もリーフノードレベルで実行されます。ただし、挿入とは異なり、削除はより複雑です。削除するキーは、リーフノードまたは内部ノードのいずれかです。

キーを削除するには、以下の一連の手順（アルゴリズム）に従います。

1.1。 リーフノードを見つけます。

2.2。 ノード内のキーの数がm / 2を超える場合は、指定されたキーをノードから削除します。

3.3。 リーフノードにm / 2キーがない場合は、Bツリーを維持するために、右または左のサブツリーからキーを取得してキーを完成させる必要があります。

次の手順に従います。

  • 左側のサブツリーにm / 2個の要素が含まれている場合は、その最大の要素を親ノードにプッシュしてから、間にある要素をキーが削除された場所に移動します。
  • 右側のサブツリーにm / 2個の要素が含まれている場合は、その最小の要素を親ノードにプッシュしてから、間にある要素をキーが削除された場所に移動します。

四。 m / 2ノードを持つノードがない場合、上記の手順を実行できないため、2つのリーフノードと親ノードの間にある要素を結合して、新しいリーフノードを作成します。

5.5。 親にm / 2ノードがない場合は、問題の親ノードに対して上記の手順を繰り返します。これらの手順は、バランスの取れたBツリーが得られるまで繰り返されます。

以下に示すのは、Bツリーからノードを削除するための図です。

次のB木をもう一度考えてみましょう。

Btree-削除

Bツリーからキー60を削除するとします。 Bツリーを確認すると、削除するキーがリーフノードに存在することがわかります。このリーフノードからキー60を削除します。

これで、ツリーは次のようになります。

削除後のBツリー

キー60を削除した後、Bツリーリーフノードが必要なプロパティを満たし、Bツリーにこれ以上変更を加える必要がないことがわかります。

ただし、キー20を削除する必要がある場合は、キー10のみが左側のリーフノードに残ります。この場合、ルート30をリーフノードにシフトし、キー40をルートに移動する必要があります。

したがって、Bツリーからキーを削除するときは注意が必要であり、Bツリーのプロパティに違反しないようにする必要があります。

Bツリーのトラバーサル

BツリーのトラバーサルもBSTの順序トラバーサルに似ています。左から再帰的に開始し、ルートに到達して、左のサブツリーに向かって進みます。

Team FoundationServerの使用方法

Bツリーのアプリケーション

  • ディスク上の大規模なデータベースに格納されているデータへのアクセスには非常に時間がかかるため、Bツリーは特に大規模なデータベースでデータのインデックスを作成するために使用されます。
  • より大きなソートされていないデータセット内のデータの検索には多くの時間がかかりますが、これはBツリーを使用したインデックス作成によって大幅に改善できます。

C ++のB +ツリー

B +ツリーはBツリーの拡張です。 B +ツリーとBツリーの違いは、Bツリーではキーとレコードを内部ノードとリーフノードとして保存できるのに対し、B +ツリーではレコードはリーフノードとして保存され、キーは内部ノードにのみ保存されることです。

レコードは、リンクリスト方式で相互にリンクされています。この配置により、B +ツリーの検索がより高速かつ効率的になります。 B +ツリーの内部ノードはインデックスノードと呼ばれます。

B +ツリーには2つの順序があります。1つは内部ノード用で、もう1つはリーフノードまたは外部ノード用です。

B +ツリーの例を以下に示します。

B +ツリー

B +ツリーはBツリーの拡張であるため、トピックBツリーで説明した基本的な操作は引き続き有効です。

挿入と削除の間、B +ツリーの基本的なプロパティをそのまま維持する必要があります。ただし、データはリーフノードにのみ保存され、常にリーフノードから削除されるため、B +ツリーでの削除操作は比較的簡単です。

B +ツリーの利点

  • 同数のディスクアクセスでレコードをフェッチできます。
  • Bツリーと比較して、B +ツリーの高さは低く、バランスが保たれています。
  • インデックス作成にはキーを使用します。
  • B +ツリーのデータには、リーフノードがリンクリストに配置されているため、順次または直接アクセスできます。
  • データはリーフノードにのみ保存され、リンクリストとして保存されるため、検索が高速になります。

BツリーとB +ツリーの違い

BツリーB +ツリー
データは、内部ノードだけでなくリーフノードにも保存されます。データはリーフノードにのみ保存されます。
データは内部ノードとリーフノードに保存されるため、検索は少し遅くなります。データはリーフノードにのみ保存されるため、検索が高速になります。
冗長な検索キーはありません。冗長な検索キーが存在する可能性があります。
削除操作は複雑です。リーフノードから直接データを削除できるため、削除操作が簡単です。
リーフノードをリンクすることはできません。リーフノードは互いにリンクされて、リンクリストを形成します。

結論

このチュートリアルでは、BツリーとB +ツリーについて詳しく説明しました。これらの2つのデータ構造は、データ量が非常に多い場合、およびデータ全体をメインメモリに保存できない場合に使用されます。したがって、データをディスクに格納するために、BツリーとB +ツリーを利用します。

Bツリー検索は、データが内部ノードとその中のリーフノードに格納されるため、少し遅くなります。 B +ツリーはBツリーの拡張であり、ここのデータはリーフノードにのみ保存されます。この要因により、B +ツリーでの検索はより高速で効率的です。

=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。

推奨読書

^