在wikipedia上的一个快速搜索显示，r-tree对于搜索的最差情况性能是未定义的，平均情况是o（logmn）。
我想最坏的情况是这样的，因为我们不知道在这个结构中要执行多少次搜索，直到我们找到这个项目，事实上，guttman确实说“在访问的节点下可能需要搜索多个子树，因此，不可能保证良好的最坏情况下的性能，“我们能用必须执行的搜索次数来表示最坏情况吗？
关于一般情况，我不明白这是如何计算的。最好的案子呢？
最佳答案
我认为最坏的情况是o（n+logmn）：假设您在r树中存储了很多重叠的矩形。现在存储一个小矩形，它位于所有其他矩形重叠的区域中。对该矩形的查询必须遍历所有子树：nodes->o（logm n）和entries->o（n）。
最佳情况是o（log n）。一个r树在每个分支中都有相同的深度，并且数据只存储在叶节点中，因此您将始终必须遍历o（logm n）节点和该节点中的所有条目，因此它应该是o（m*logmn）。
我不确定你真的能计算出平均O（logm n）。但是，如果您有一些平均的正态分布数据（无论这意味着什么），与平均查询（无论平均值是什么）相比，重叠很少（无论这意味着什么），那么不应该遍历超过几个（1或2？）子树。我实际上会说平均值是o（m*logm n），因为在一个节点中遍历m个条目。
关于database - 了解R-Tree的时间复杂性吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48815868/