我对 R-Tree 数据结构有疑问。R-Tree 中的扇出是什么。它是最大条目数吗？
我们如何确定 R-Tree 中的最小和最大条目数？假设我有 10000 个点并且我的页面大小为 8kb。
谢谢
问问题
8846 次
2 回答
18
在任何树中，扇出是指向节点中子节点的指针数。
不同的树有不同的扇出。
二叉树有扇出2。
B树有一个扇出B，除了叶子之外的所有节点都有B/2和B个子节点。外部（磁盘上）实现通常放宽最小数量的子限制以保存一些更新。
在数据库中，通常使用B-trees或其变体称为B+-trees，以便每个节点的大小为 1 页，并且扇出由适合该空间的排序键和指针的数量决定。
R-tree是一种搜索树，其中索引是多维区间。这些可能会重叠。它可能有任何扇出。通常是 2 到维数的数量（所以 4 代表 2 维，8 代表 3 维等）。但它也可能有更高的扇出，并且像 B-tree 一样组织它当然是可能的。
我们如何确定 R-Tree 中的最小和最大条目数？假设我有 10000 个点并且我的页面大小是 8KiB。
树节点的大小不必与页面大小匹配。如果是这样（通常用于外部，即磁盘上的实现），您仍然需要知道排序键有多大以及指针有多大。R-tree 每个维度需要 2 个坐标值，最小值和最大值。因此，具有双精度坐标的二维 R 树（映射应用程序中出现的常见情况）将有四个 64 位值描述矩形加上一个子指针，外部实现可能也希望使用 64 位。也就是说，每个孩子 20 B，您可以在 8 KiB 页面中压缩其中的 409 个。点数无关紧要。坐标系的尺寸和精度。
在内存中，低扇出的树更有效，因为虽然它们更深，但每次搜索需要的比较更少。然而，在磁盘上（在数据库中），缓慢的操作是读取，并且由于只能在块中完成，因此通过让每个节点填充整个块并相应地具有更高的扇出来减少节点数量会更快。
于 2014-03-05T07:28:50.070 回答
3
“扇出”是指 R-Tree 具有的每个节点的指针数量
于 2014-03-05T07:14:20.057 回答