R-Tree中的粉絲是什麼？

我對R-Tree數據結構有疑問。什麼是R-Tree中的扇形。這是最大數量的條目嗎？R-Tree中的粉絲是什麼？

我們如何確定R-Tree中最小和最大條目數？假設我有10000點，我的頁面大小爲8kb。

由於

來源

2014-03-05 user3030823

你確定你的意思是R-tree而不是B-tree（或B + -tree）嗎？ –

是的，我確定它是R-tree。 – user3030823

請注意，根據頁面大小確定的扇出僅適用於外部樹，即存儲在文件中的扇形，而且太大而無法在內存中完全加載。在記憶中，扇出較少的樹更有效，因爲它們總共需要每次搜索的較少比較。 –

扇出，在任何樹的每個節點的指針的數目，是在一個節點的指針的子節點的數目。

不同的樹有不同的扇出。

甲binary tree具有扇出2.

甲B-tree具有扇出乙，與所有節點除了B/2和孩子之間乙具有葉。外部（磁盤上）實施通常會放寬最少數量的兒童限制，以節省一些更新。

在數據庫中，或B-trees經常使用其變體稱爲B+-trees使得每個節點具有1頁的尺寸，並通過適合於該空間排序鍵和指針的數目來確定的扇出。

R-tree是索引是多維間隔的搜索樹。這些可能會重疊。它可能有任何扇出。通常是2到維數的數目（所以4維2維，8維3維等）。但它也可能有更高的扇出率，並且組織它類似於B樹也是可能的。

我們如何確定R-Tree中的最小和最大條目數？假設我有10000點，頁面大小是8KiB。

樹節點的大小不必與頁面大小相匹配。如果確實如此（通常用於外部，即在磁盤上，實現），您仍然需要知道排序鍵的大小以及指針的大小。一棵R樹需要2個座標值，每個維度的最小值和最大值。因此，具有雙精度座標的2維R樹（在映射應用程序中出現的常見情況）將有四個64位值描述該矩形和一個子指針，對於該子指針，外部實現可能也要使用64位。這是每個孩子20 B，你可以在8 KiB頁面中擠壓409個這樣的孩子。點數不重要。座標系的尺寸和精度確實如此。

在記憶中，扇出率較低的樹更高效，因爲雖然它們更深，但每次搜索所需的比較次數較少。然而，在磁盤上（在數據庫中），緩慢的操作是讀取，因爲只能以塊的形式完成，所以通過使每個節點填充整個塊並具有相應較高的扇出來減少節點的數量更快。

來源

2014-03-05 07:28:50

+1這是一個清晰的解釋！ –

我不同意最後一段。即使在內存中，由於L1/L2/L3緩存等原因，擴展扇出也許會有所幫助 - 出於同樣的原因，插入排序比小陣列上的排序更快。 –

「扇出」是指R-樹是具有

來源

2014-03-05 07:14:20

是否表示條目數量？ – user3030823

@ user3030823：沒有。這意味着每個父節點的條目數量。 –

R-Tree中的粉絲是什麼？

回答

相關問題