3

バイナリ ツリーまたは B ツリーをディスクやテープなどのセカンダリ ストレージ デバイスに保存する場合、バイナリ ツリーは B ツリーよりも優れていますか?

「B ツリーがバイナリ ツリーよりも優れているのはいつですか?」という課題で、私は尋ねられました。

私が思いついたのは、ディスク アクセスの頻度が少なくて済み (ノード アクセスごとにより多くのデータを読み取る)、最終ノードに到達するためにジャンプするノードが少ないため、B ツリーの方が優れているということです。しかし、質問の言い方からすれば、バイナリ ツリーが実際に B ツリーよりも有利な点があることを意味します。では、バイナリ ツリーがセカンダリ ストレージに格納されている場合、B ツリーよりも優れている (効率的である) 点はありますか?

4

1 に答える 1

1

並べ替えられたツリー (B ツリー) と単純なバイナリ ツリーを比較するのは正しくありません。それらは等しくありません。つまり、二分探索木を意味していると思います。

B-Tree は、データが比較的低速なストレージに格納されている場合に効率的になるように設計されています。たとえば、クラスタ サイズが 4kb のファイル システムからデータをロードまたは保存する場合、この範囲 0..4kb のデータがどれだけ必要かは関係ありません。1 バイトまたは 4kb を読み取るのに同じ時間がかかり、実際には時間。B-tree はそのことを念頭に置いて使用します。したがって、すべての通常/一般的な使用シナリオでは、B ツリーを使用する方が効率的です (使用されるスペースとパフォーマンスの観点から)。

于 2013-10-07T21:58:12.443 に答える