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.
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.
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.
