How Does a Geospatial Index Work? [Closed]

How Does a Geospatial Index Work? [Closed]

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.

6

2 Answers

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.

0

According to this other SO question:

The current implementation encodes geographic hash codes atop standard MongoDB B-trees. Results of $near queries are exact. One limitation with this encoding, while fast, is that prefix lookups don't give exact results, especially around bit flip areas. MongoDB solves this by doing a grid-neighbor search after the initial prefix scan to pick up any straggler points. This generally ensures that performance remains very high while providing correct results.

Marcus Vance
Author

Marcus Vance

Marcus Vance is a cybersecurity auditor and technology writer dedicated to educating the public about online safety, data privacy regulations, enterprise security, and emerging cyber threats.