データ構造

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



Difference Between B Tree



B木：


B +ツリー：



構造的に



Bツリーに設定されたキーワードはツリー全体に分散され、リーフノードにはキーワード情報が含まれず、B +ツリーのキーワードセットはリーフノードに分散され、非リーフノードはリーフノードのキーワード
Bツリーのキーワードは1つのノードにのみ表示され、B +ツリーのキーワードはリーフノードまたは非リーフノードに表示される必要があります

パフォーマンス（実際のアプリケーションのオペレーティングシステムのファイルインデックスとデータベースインデックスには、BツリーよりもB +ツリーの方が適しているのはそのためですか？）

  • B +ツリーディスクの読み取りと書き込みのコストが低くなります B +ツリーのため 非リーフノードはインデックス情報のみを保存します 、そして 実際のデータ情報はリーフノードにのみ保存されます このようにして、各非リーフノードはより多くのインデックス情報を格納し、1つのディスクIOがより多くのインデックス情報をメモリに読み取ることができるため、ディスクIOの数を減らすことができます。
  • B +ツリークエリの効率はより安定しています 非リーフノードはインデックス情報のみを格納し、実際のデータ情報は格納しないため、キーワード検索ではルートノードからリーフノードへのパスを使用する必要があります。すべてのキーワードクエリのパス長は同じであるため、各データのクエリ効率が向上します。
  • B +ツリーは間隔クエリに適しています B +ツリーのデータはリーフノードに格納されるため、非リーフノードはすべてインデックス付けされ、すべてのデータ情報を取得するためにリーフノードのみをスキャンする必要がありますが、Bツリーはそのためデータも格納します。非リーフノード。特定のデータを見つける必要があります。順番にスイープするためにシーケンシャルトラバーサルを実行する必要があるため、B +ツリーは間隔クエリに適しているため、通常はB +ツリーがデータベースのインデックス作成に使用されます。