How does a geospatial index work?

indexing geospatial
Scott Hyndman picture Scott Hyndman · Jan 2, 2011 · Viewed 12.1k times · Source

I'm wondering how a geospatial index, such as the one used by MongoDB, works. Can anyone explain what data structure/algorithm is used internally? What time complexity does a search run in?

Links to resources would be great too.

Answer

codekaizen picture codekaizen · Jan 2, 2011

Depending on the data type and usage pattern, either an R-Tree or variant (R*, R+) or a quadtree or perhaps even a kd-tree.

Related questions

R-Tree and Quadtree Comparison

I want to compare the R-Tree and the Quadtree for geospatial data. While there is literature out there I struggle to find documents that cover real basic comparison. So I decided to ask this question. In my opinion, the R-Tree …

Read More
Finding the index of an item in a list

Given a list ["foo", "bar", "baz"] and an item in the list "bar", how do I get its index (1) in Python?

Read More
Getting the last element of a list

In Python, how do you get the last element of a list?

Read More