R树和R*树的范围搜索复杂度
range search complexity of R tree and R* tree
R树和R*树的范围搜索复杂度是多少？我了解范围搜索的过程：类似于 DFS 搜索，它访问每个节点，如果节点的边界框与目标范围相交，则将该节点包含在结果集中。更准确地说，我们还需要考虑它使用的分支定界策略：如果父节点不与目标相交，那么我们就不会访问它的子节点。那么复杂度应该小于 O(n)，其中 n 是节点数。我真的不知道如何计算给定叶数（或数据点）的节点数。
有人可以在这里给我一个解释吗？谢谢你。
显然，如果你的范围在每个维度上都是 [-∞;∞]，那么最坏的情况必须至少是 O(n)。由于这棵树，它可能和 O(n log n) 一样糟糕。
假设答案是单个条目，平均情况可能是 O(log n) - 只需要遵循几条穿过树的路径（如果重叠足够少）。
它以您的页面大小为准。所以它通常不会超过 5，因为你永远不希望树有超过 1000^5=10^15 个对象。
出于所有实际目的，假设运行时复杂度只是答案集大小 O(s)。 Select 2% 的数据花费的时间是 1% 的两倍。
R树和R*树的范围搜索复杂度是多少？我了解范围搜索的过程：类似于 DFS 搜索，它访问每个节点，如果节点的边界框与目标范围相交，则将该节点包含在结果集中。更准确地说，我们还需要考虑它使用的分支定界策略：如果父节点不与目标相交，那么我们就不会访问它的子节点。那么复杂度应该小于 O(n)，其中 n 是节点数。我真的不知道如何计算给定叶数（或数据点）的节点数。 有人可以在这里给我一个解释吗？谢谢你。
显然，如果你的范围在每个维度上都是 [-∞;∞]，那么最坏的情况必须至少是 O(n)。由于这棵树，它可能和 O(n log n) 一样糟糕。
假设答案是单个条目，平均情况可能是 O(log n) - 只需要遵循几条穿过树的路径（如果重叠足够少）。
它以您的页面大小为准。所以它通常不会超过 5，因为你永远不希望树有超过 1000^5=10^15 个对象。
出于所有实际目的，假设运行时复杂度只是答案集大小 O(s)。 Select 2% 的数据花费的时间是 1% 的两倍。