FYI, searching the R-tree also has runtime complexity of O(N) in the worst case. I believe there is some R-tree variant which actually provides asymptotically better performance than the naive case, but it is very complicated and tends to perform worse on average in practice.

Source: just spent two months implementing R-trees in Rust