use*_*823 5 database tree r-tree
我对R-Tree数据结构有疑问.什么是R-Tree中的扇出.它是最大条目数吗？
我们如何确定R-Tree中的最小和最大条目数？如果我有10000点,我的页面大小为8kb.
谢谢
Jan*_*dec 12
在任何树中扇出都是指向节点中子节点的指针数.
不同的树木有不同的扇出.
一个二叉树有扇出2.
甲B-树具有扇出乙,与所有节点除了具有间叶B/2和乙儿童.外部(磁盘上)实现通常会放宽最小数量的子限制以保存一些更新.
在数据库中,经常使用B树或称为B + 树的变体,因此每个节点的大小为1页,扇出由适合该空间的排序键和指针数决定.
一个R-树是一个搜索树,其中指数是多维的时间间隔.这些可能会重叠.它可能有任何扇出.通常是2到维数的数量(因此2维为4,3维为8等).但它也可能有更高的扇出,组织它类似于B树肯定是可能的.
我们如何确定R-Tree中的最小和最大条目数？如果我有10000点,我的页面大小是8KiB.
树节点的大小不必与页面大小匹配.如果它(通常用于外部,即在磁盘上,实现),您仍然需要知道排序键有多大以及指针有多大.R树需要每个维度2个坐标值,最小值和最大值.因此,具有双精度坐标的二维R树(在映射应用程序中出现的常见情况)将具有四个64位值,其描述矩形加上子指针,对于该外部实现,外部实现可能也想要使用64位.这是每个孩子20 B,你可以在8 KiB页面中挤出其中的409个.积分数无关紧要.坐标系的尺寸和精度确实如此.
在内存中,扇出较低的树更有效,因为虽然它们更深,但每次搜索需要更少的比较.但是在磁盘上(在数据库中),慢速操作是读取,并且因为这只能在块中完成,所以通过使每个节点填满整个块并具有相应更高的扇出来减少节点数量更快.
| 归档时间： |
|
| 查看次数： |
5824 次 |
| 最近记录： |