了解R-Tree的时间复杂性吗？

Question

在维基百科上快速搜索一下就会发现，R-树的最坏情况下的搜索性能是不确定的，平均情况是O(logMn)。

我认为最坏的情况是这样的，因为在找到项目之前，我们不知道必须在这个结构中执行多少次搜索，实际上，Guttman确实说过，“可能需要搜索访问的节点下的多个子树，因此不可能保证良好的最坏情况下的性能。”我们能用必须执行的搜索次数来表示最坏的情况吗？

关于平均情况，我不明白这是如何计算的。那么最好的情况呢？

Answer 1

我会说最坏的情况是O(n + logM n)：假设你在R树中存储了许多重叠的矩形。现在存储一个位于所有其他矩形重叠区域的小矩形。对该矩形的查询必须遍历所有子树: nodes -> O(logM n)和entries -> O(n)。

最好的情况是O(log )。R-树在每个分支中具有相同的深度，并且数据仅存储在叶节点中，因此您将始终必须遍历O(logM n)个节点和该节点中的所有条目，因此它应该是O(M * logM n)。

我不确定你是否真的能计算出平均值O(logM n)。但是，如果您有一些平均的正态分布数据(无论这意味着什么)，并且重叠(无论几个意味着什么)，那么您的平均查询(无论平均值是多少)不应该遍历超过几个(1或2?)子树。我实际上认为平均值是O(M * logM n)，因为在一个节点中需要遍历M个条目。