database - R-Tree 中的扇出是什么？

Question

我对R-Tree数据结构有疑问。 R-Tree 中的扇出是什么。是否有最大条目数？

我们如何确定 R-Tree 中条目的最小和最大数量？假设我有 10000 点，我的页面大小为 8kb。

谢谢

Answer 1

在任何树中，扇出是指向节点中子节点的指针的数量。

不同的树有不同的扇出。

A binary tree有扇出 2。

A B-tree有一个扇出 B，除了叶子节点之外的所有节点都有 B/2 和 B 个子节点。外部(磁盘上)实现通常会放宽最小子节点数限制以保存一些更新。

在数据库中，B-trees或它们的变体称为 B+-trees经常使用，因此每个节点的大小为 1 页，扇出由适合该空间的排序键和指针的数量决定。

安R-tree是一个搜索树，其中索引是多维区间。这些可能会重叠。它可能有任何扇出。通常是 2 到维度的数量(因此 4 表示 2 维，8 表示 3 维等)。但它也可能有更高的扇出，并且类似于 B-tree 组织它当然是可能的。

How can we determine the minimum and maximum number of entries in R-Tree? Let say if I have 10000 points and my page size is 8KiB.

树节点的大小不必与页面大小匹配。如果是这样(通常用于外部，即磁盘上的实现)，您仍然需要知道排序键有多大以及指针有多大。 R 树的每个维度需要 2 个坐标值，最小值和最大值。因此，具有 double 坐标的二维 R 树( map 应用程序中常见的情况)将具有四个 64 位值来描述矩形和一个子指针，外部实现可能也希望使用 64 位。那就是每个 child 20 B，你可以在一个 8 KiB 的页面中压缩其中的 409 个。点数无关紧要。坐标系的尺寸和精度。

在内存中，扇出低的树效率更高，因为尽管它们更深，但每次搜索需要的比较更少。然而在磁盘上(在数据库中)缓慢的操作是读取，因为这只能在 block 中完成，通过让每个节点填充整个 block 并具有相应的更高扇出来减少节点数量会更快。