database - R-Tree のファンアウトとは何ですか?

Question

R-Tree のデータ構造に疑問があります。R-Tree のファンアウトとは。エントリーの最大数ですか？

R ツリーのエントリの最小数と最大数をどのように決定できますか? 10000 ポイントがあり、ページ サイズが 8kb であるとします。

ありがとう

Answer 1

ファンアウトは、任意のツリーで、ノード内の子ノードへのポインターの数です。

ツリーが異なれば、ファンアウトも異なります。

二分木にはファンアウト 2 があります。

BツリーにはファンアウトBがあり、葉を除くすべてのノードはB/2からBの子を持ちます。外部 (ディスク上) の実装では、いくつかの更新を保存するために、子の最小数の制限が緩和されることがよくあります。

データベースでは、B ツリーまたはB+ ツリーと呼ばれるそのバリアントがよく使用されるため、各ノードのサイズは 1 ページで、ファン アウトはそのスペースに収まるソート キーとポインターの数によって決定されます。

R ツリーは、インデックスが多次元間隔である検索ツリーです。これらは重複する可能性があります。ファンアウトがある場合があります。通常は、次元数に対して 2 の数です (つまり、2 次元の場合は 4、3 次元の場合は 8 など)。ただし、ファンアウトも大きくなる可能性があり、B ツリーと同様に編成することは確かに可能です。

R ツリーのエントリの最小数と最大数をどのように決定できますか? 10000 ポイントがあり、ページ サイズが 8KiB だとします。

ツリー ノードのサイズは、ページ サイズと一致する必要はありません。その場合 (通常は外部、つまりディスク上での実装に使用されます)、ソート キーの大きさとポインタの大きさを知る必要があります。R ツリーには、次元ごとに最小値と最大値の 2 つの座標値が必要です。したがって、倍精度座標を持つ 2 次元 R ツリー (マッピング アプリケーションでよく見られるケース) には、四角形を表す 4 つの 64 ビット値と子ポインターが含まれます。外部実装では、おそらく 64 ビットも使用する必要があります。これは子供 1 人あたり 20 B であり、8 KiB ページで 409 個を絞り込むことができます。点数は問いません。座標系の寸法と精度です。

メモリ内では、ファンアウトが小さいツリーの方が効率的です。ツリーは深くなりますが、検索ごとに必要な比較が少なくなるためです。ただし、ディスク上 (データベース内) では読み込みが遅く、これはブロック内でしか実行できないため、各ノードでブロック全体を埋め、それに応じてファンアウトを大きくすることで、ノードの数を減らす方が高速です。

Answer 2

「ファンアウト」とは、R-Tree が持っているノードごとのポインターの数を指します。