AVLツリーはBツリーとどのように異なりますか？
49321 次
9 に答える
55
AVLツリーは、ランダムアクセスが比較的安価なメモリ内での使用を目的としています。Bツリーは、読み取りまたは書き込み操作に必要なシークの数を最小限に抑えるために、各ノードに多数のキーをグループ化するため、ディスクバックアップストレージに適しています。（これが、 SQLiteなどのファイルシステムやデータベースでBツリーがよく使用される理由です。）
于 2010-04-29T04:07:44.187 に答える
46
AVLツリーとBツリーはどちらも、要件によってそれぞれのツリーの高さを最小化するデータ構造であるという点で類似しています。この「短さ」により、可能な最大の読み取り数がツリーの高さに対応するため、O（log n）時間で検索を実行できます。
5
/ \
3 7
/ / \
1 6 9
これはAVLツリーであり、その中核となる二分探索木です。ただし、これは自己バランス型です。つまり、ツリーに要素を追加すると、ツリーはそれ自体を再構築して、可能な限り均一な高さを維持します。基本的に、長いブランチは許可されません。
Bツリーもこれを行いますが、別のリバランススキームを使用します。書き出すのは少し複雑すぎますが、Googleで「Bツリーアニメーション」を検索すると、Bツリーを非常によく説明する非常に優れたアプレットがいくつかあります。
これらは、AVLツリーがメモリベースのソリューションを念頭に置いて実装されているのに対し、Bツリーはディスクベースのソリューションを念頭に置いて実装されているという点で異なります。AVLツリーは、動的メモリ割り当てとメモリの次のブロックへのポインタを使用するため、大量のデータコレクションを保持するようには設計されていません。明らかに、ディスクの場所とディスクポインタを使用してAVLツリーの機能を複製することはできますが、非常に大きなサイズのツリーを読み取るためにかなりの数の読み取りが行われるため、処理速度は大幅に低下します。
データ収集が大きすぎてメモリに収まらない場合、解決策はBツリーです（興味深いファクトイド：「B」が実際に何を表すかについてのコンセンサスはありません）。Bツリーは、1つのノードに多くの子を保持し、子ノードへの多くのポインターを保持します。このように、ディスクの読み取り（単一のディスクブロックの読み取りに約10ミリ秒かかる場合があります）中に、関連するノードデータの最大量と、「リーフノード」ディスクブロックへのポインターが返されます。これにより、データの取得時間をlog（n）時間に償却できるため、Bツリーはデータベースおよび大規模なデータセットの取得実装に特に役立ちます。
于 2011-04-05T21:16:19.770 に答える
19
AVLツリーは、平衡二分探索木であり、O（log n）の高さを維持するようにバランスがとられています。
Bツリーはバランスの取れたツリーですが、二分木ではありません。ノードにはより多くの子があり、ノードごとの検索時間は長くなりますが、検索でアクセスする必要のあるノードの数は減ります。これにより、ディスクベースのツリーに適しています。詳細については、ウィキペディアの記事を参照してください。
于 2010-04-29T04:06:10.460 に答える
4
AVLツリーは、検索の挿入および削除操作でO（lgN）平均および最悪のケースを有効にする自己平衡二分木です。これは、メモリに裏打ちされた検索ツリー（中程度のサイズのデータセット）で使用されます。
Bツリーは、ディスクへの読み取りが少なくて済むため、主に非常に大きなデータセットのストレージに基づく検索ツリーとして使用されます（各ノードにはN> 1のN個のキーが含まれているため）。Bツリーは（N、N + 1）Bツリーと呼ばれます。ここで、Nはノードあたりのキーの数、N+1はノードあたりの子の数です。ノードあたりのキーが多いほど、ディスクから読み取る必要のある時間が少なくなり、当然、ツリーも浅くなります（レベルが低くなります）。
于 2012-12-17T05:35:03.310 に答える
2
AVLは自己バランス型であり、すべての操作が平均および最悪の場合にO（log n）であることを保証します。
于 2010-04-29T04:02:50.517 に答える
2
Bツリーは、上記のすべてのアイデアを使用します。特に、Bツリー：
1)keeps keys in sorted order for sequential traversing
2)uses a hierarchical index to minimize the number of disk reads
3)uses partially full blocks to speed insertions and deletions
4)keeps the index balanced with an elegant recursive algorithm
さらに、Bツリーは、内部ノードが少なくとも半分満たされていることを確認することにより、無駄を最小限に抑えます。Bツリーは、任意の数の挿入と削除を処理できます。
于 2012-10-02T07:17:42.240 に答える
2
他の回答者は、AVLとB-Treeの両方に関する非常に詳細な技術的詳細をすでに提供していますが、これら2つに関する比較的初心者の情報を追加したいと思います。
- AVLツリーはバイナリツリーですが、Bツリーはマルチウェイツリー（N-aryツリー）です。つまり、AVLツリーの任意のノードは最大2つの子ノードと1つの情報/データを持つことができますが、 Bツリーの任意のノードはn個のノードとn-1個の情報/データを持つことができます。Bツリーの場合、nはその順序とも呼ばれます。
于 2017-12-30T00:04:12.497 に答える
2
それらは実際には非常に異なりますが、連想テーブルをサポートするというほぼ同じ目的を果たします。歴史的に、AVLツリーはメモリ内操作でBツリーよりも優れていると見なされていましたが、CPUサイクルと比較した場合、メモリへのアクセスが安価であった場合に特に当てはまります。
データベースでは一般的に可変長キーを格納するために使用されますが、Bツリーは固定長および短いレコード（キー+データ）に最適です。このような用途では、メモリフットプリント（データをよりコンパクトに格納するため）と速度（キャッシュの局所性がはるかに優れているため）の両方の点で、メモリ内の用途のAVLツリーを大幅に上回る可能性があります。
L2は、Bツリー上で非常に高速な連想テーブルとシーケンスを実装するデータ構造ライブラリです。また、AVLツリーがあり、2つのパフォーマンスを簡単に比較できます。
于 2018-01-18T10:35:21.367 に答える
0
Bツリー
ここでの典型的なユースケースは、ディスク上のデータベースの場合です。この場合、ツリーのレベルを下ってアイテムを見つけるのに費用がかかります。あなたがそれをしなければならないとき、あなたはできるだけ多くの仕事を削る必要があります。各bツリーには最大次数があり、各ノードはアイテムと他のノードへの参照（nアイテム、n + 1参照）を保持します。この事実により、ディスク上のアイテムのチャンクを簡単に保存して後で見つけることができます。また、アイテムを追加/削除するときに、ツリーの大きなチャンクを書き直さないようにすることもできます。
AVLツリー
自己平衡平衡二分木の多様性。平衡二分木は、最大高さが。の二分木ですlog(n)。
于 2020-06-14T14:28:45.180 に答える