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.
Does that mean mongodb split the earth into several grids?
This presentation from Greg Studer (10gen) discusses the geospatial indexes in some detail:
Geospatial Indexing with MongoDB.
The standard geospatial implementation as at MongoDB 2.2 uses a 2-D GeoHash approach, with variable bits of precision:
By default, precision is set to 26 bits which is equivalent to approximately
2 feet given (longitude, latitude) location values and default (-180, 180)
bounds.
The GeoHash approach does have edge cases where some points may be spatially close but have different hashes. MongoDB also includes a Geospatial Haystack Index which is specifically tuned for small-region "near" long/lat searches with one additional indexed criteria (for example: "find all restaurants within 25 miles with name 'foo'").
Another interesting presentation from Nicholas Knize (Thermopylae) contrasts the current B-tree / GeoHash approach with R-trees. If you skip ahead to slide 8, there is a visual explanation that may be helpful:
RTree Spatial Indexing with MongoDB - MongoDC.
