关于R-Tree时间复杂度的探讨：能否明确其最坏情况表达式？

Great question! Let's break this down clearly.

First, as you've already noted, the average time complexity of an R-Tree search is O(log_M n), where:

• M = the maximum number of entries (either child nodes or data objects) a single R-Tree node can contain
• n = the total number of data objects stored in the tree

The reason the worst-case complexity is often described as "undefined" ties directly to Guttman's observation:

"访问节点下可能有多个子树需搜索，无法保证良好的最坏情况性能"

But we can quantify this worst case using those same core parameters (M and n):

• In the absolute worst scenario—say, every minimum bounding rectangle (MBR) in the tree fully overlaps with your query region—you’ll have to visit every node in the tree and check every single data object for a match. This gives us a worst-case time complexity of O(n).
• If you want to be more granular, you could write it as O((n/M) + n), but since M is a fixed constant (determined by the R-Tree's implementation), this simplifies down to the cleaner O(n).

The key difference here from balanced trees like B-trees is that R-Trees don’t restrict you to a single path from root to leaf. When multiple child MBRs intersect with your query, you have to explore all of them. In the extreme case where all MBRs overlap the query, this means traversing the entire tree structure and validating every data point—hence the linear worst-case complexity.

内容的提问来源于stack exchange，提问作者Zeruno