Reputation: 6009
Anyone knows how the geospatial indexing works, i mean the algorithm to calculate nearest points?
In SQL we may do things like this:
SELECT id, (x-a)*(x-a)+(y-b)*(y-b) as distance FROM table1 ORDER by distance ASC
Sure this is not efficient enough compared with mongodb's geospatial indexing, but how does mongodb calculate and sort?
Many thanks in advance.
Upvotes: 6
Views: 2001
Reputation: 30176
from the 10gen site:
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.
Upvotes: 3
Reputation: 65887
Heart of mongodb geospatial is Geohashes. Geohash is a
Hierarchical spatial data structure which subdivides space into buckets of grid shape.
I couldn't find the appropriate links for the geohash implementations in mongo, but this thread might give some insights.
Upvotes: 4