我对R-Tree数据结构有疑问。什么是R-Tree中的扇出。它是最大条目数吗？
我们如何确定R树中的最小和最大条目数？假设我有10000点，我的页面大小为8kb。
谢谢
最佳答案
在任何树中，扇出都是指向节点中子节点的指针数。
不同的树具有不同的扇出。
binary tree具有扇出2。
B-tree的扇出为B，除叶子以外的所有节点的子节点介于B/2和B之间。外部(磁盘上)实现通常会放宽对子级的最小限制，以保存一些更新。
在数据库中，通常使用B-trees或它们的变体B+-trees，以便每个节点的大小为1页，并且扇出大小由适合该空间的排序键和指针的数量确定。
R-tree是搜索树，其中索引是多维间隔。这些可能重叠。它可能有任何扇出。通常是2到维数(因此4表示2维，8表示3维，等等)。但是它也可能具有更高的扇出度，并且可以像B树一样组织它。
树节点的大小不必与页面大小匹配。如果确实如此(通常用于外部，即磁盘上的实现)，则您仍然需要知道排序键的大小和指针的大小。 R树需要每个尺寸2个坐标值，最小和最大。因此，具有 double 坐标的二维R树(在映射应用程序中经常出现)将具有四个描述矩形的64位值和一个子指针，为此，外部实现可能也希望使用64位。每个 child 20 B，您可以在8 KiB的页面中压缩409B。点数无关紧要。坐标系的尺寸和精度确实如此。
在内存中，扇出度较低的树更有效，因为它们虽然更深，但每次搜索所需的比较次数更少。但是，在磁盘上(在数据库中)，读取操作的速度很慢，并且由于只能以块为单位进行读取，因此通过使每个节点填满整个块并具有相应更高的扇出，可以减少节点数。
关于database - R-Tree中的扇出是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22190885/