How does MongoDB implement it's spatial indexes?

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.

Does that mean mongodb split the earth into several grids?

Answer 1

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.