私は最近、B+ツリーとTツリーを研究しています。ディスク上のインデックスにはB+ツリーが使用され、メモリではTツリーが使用される傾向があるようです。
ディスクのI/Oが原因だと思いますが、その概念を裏付けるものは何も見つかりません。私はその仮定で正しいですか？
また、Tツリーへのディスクアクセスをキャッシングを介してログBに制限できる場合、logBNでB+ツリーよりもパフォーマンスが優れているのではないでしょうか。
質問する
468 次
1 に答える
1
Tツリーは本質的に二分木です。したがって、ツリーの深さは、Tツリーのlog2（N / B）とB +ツリーのlogB（N）のようになります（N =＃データ項目、B=各ノードに格納されているキーの数=Bの分岐係数+ツリー）。どちらのツリーにも各ノードに固定数のアイテムがないため、これらは概算です。とにかく、大きなNの場合、B+Treeはそのメトリックで手軽に勝ちます。均一なメモリアクセスを前提とすると、その数値は重要ではありませんが、セカンダリストレージへのアクセス数とほぼ同じであるセカンダリストレージでは実際に重要です。また、階層メモリを備えた最新のマシン（Vax 11/750でテストされた元のT-Treeペーパー）でも重要です。
それぞれの環境で両方の構造を更新する方法について、上記の仮定を立てます。それらは対称的で公平だと思います。主に、データとキーは参照によってメモリに保存され、コピーによってセカンダリストレージに保存されると想定しています。このように構造を調整しないと、Tツリーにとって悲惨なことになります。Tツリーは、設計のコアとして均一なアクセスコストがあり、各キーの比較には外部アクセスが必要になるためです。固定されていないサイズのデータの場合、どちらの場合も他のパッキング調整が必要です（実際の世界で使用されます）。
于 2013-02-18T18:32:00.613 に答える