6

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.

adamsmith
  • 5,759
  • 4
  • 27
  • 39

2 Answers2

4

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.

RameshVel
  • 64,778
  • 30
  • 169
  • 213
  • 1
    Thank you! This helps a lot. Never heard of Geohashes, seems i need to google and delve into that first~~ – adamsmith Dec 28 '11 at 06:32
3

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.

Tyler Brock
  • 29,626
  • 15
  • 79
  • 79
  • There are also comments on the specifics of the implementation in the C++ source code which is open source and available for download (I have the source code on another computer but I think it's a z-order-b-tree ... from my understanding the end result is basically a quad key algorithm) – Jordan Dec 27 '11 at 23:25