21

私は B ツリーを読んでいて、O(lg n) 時間で動的集合操作を達成しているようです。Red Black Tree(Java の TreeMap ) も漸近的に同じ時間枠で同じ操作を実現します。Bツリーがデータベースやファイルシステムにとってより便利な理由を知りたい

4

3 に答える 3

28

Bツリーが存在する主な理由は、大量のデータを読み書きするデバイスの動作をより有効に活用するためです。データをディスクに保存する必要がある場合、Bツリーをバイナリツリーよりも優れたものにするためには、次の2つのプロパティが重要です。

  • ディスクへのアクセスは非常に遅いです（メモリやキャッシュと比較して、ディスク上のデータへのランダムアクセスは桁違いに遅くなります）。と
  • 読み取りごとに、セクター全体がドライブからロードされます。セクターサイズを4Kとすると、これは1000の整数、または格納している数十の大きなオブジェクトを意味します。

したがって、2番目の事実の長所を使用しながら、短所、つまりディスクアクセスの数を最小限に抑えることができます。

したがって、左または右のどちらに進むべきかを示すすべてのノードに単一の数値を格納する代わりに、最初の1/100、2番目に続ける必要があるかどうかを示すより大きなインデックスを作成できます。または99番目まで（最初の文字でソートされ、次に2番目の文字でソートされたライブラリ内の本を想像してください）。このすべてのデータが単一のセクターに収まる限り、とにかくロードされるので、完全に使用したほうがよいでしょう。

これにより、おおよそlog b Nのルックアップが生成されます。ここで、Nはレコードの数です。この数は、漸近的にlog 2 Nと同じですが、実際には数分の1であり、十分なNとbがあります。データベースなどで使用するためにデータをディスクに保存することについて話しているので、データの量は通常です。これを正当化するのに十分な大きさ。

N-aryツリーの変更はバイナリツリーよりも難しいため、残りの設計上の決定は主にこれを効率的に機能させるために行われます。

于 2012-10-10T21:10:20.380 に答える
11

RB ツリーは二分探索ツリーです。B ツリーは、3 つ以上の子ノードを持つことができます。実際、子ノードの数は可変です。

そのため、ノードのサイズが常にファイルシステムのブロック サイズの倍数になるように、子ノードの数を変えることができます。これにより、読み取り時の無駄が削減されます。とにかく、1 ブロック未満を読み取ることはできません。常にブロック全体を読み取る必要があるため、有用なデータで埋めることもできます。子ノードの数を増やすと、ツリーの深さも減少するため、「ホップ」(ディスク読み取り) の平均数が減少し、パフォーマンスが再び向上します。

注意: B ツリーは通常、メモリよりも桁違いに大きいデータ構造を格納するために使用されますが、RB ツリーは通常、メモリよりも桁違いに小さいデータ構造を格納するために使用されます。実際、B ツリーは、メモリ内のデータ構造ではなく、ディスク上のデータ構造として特別に設計されています。

これはウィキペディアの記事の重要な文です(強調は私のものです):

B ツリーは、大きなデータ ブロックを読み書きするシステム用に最適化されています。

于 2012-10-10T12:27:25.007 に答える
2

メモリ内のアクセス速度はディスク上よりもはるかに高速であるため、異なるアルゴリズムが必要です。赤黒木はメモリアクセスが多いので、メモリの高速アクセスと相性がいいです。アクセスするディスクが遅いため、b-tree はより少ない、より大きなアクセスを行います。

于 2012-10-10T12:53:46.777 に答える