Addenda & thoughts since I do a lot of work along similar lines: It's probably not a bad idea to have the option of a spatial index at the leaves of a geohash,

Addenda & thoughts since I do a lot of work along similar lines: It's probably not a bad idea to have the option of a spatial index at the leaves of a geohash, as the geohash is necessarily of limited precision and will behave badly if someone inserts 100k points all within a 1x1 foot area. ;) (This is equivalent, roughly, to a plain quadtree only with the first N levels of the tree pre-calculated and cached locally.) I'm guessing the riddle at the end ("Does it remind you of anything?") would be gray code. Quad-trees can be used for polygons, although they are less than ideal, by storing a list of polygons for each quad. If a quad is entirely contained by the polygon, add the polygon to its list; if a quad is part in and part out of the polygon, add it to its list if length(poly-list) < heuristic_value; otherwise split the quad and redistribute its list among its leaves. (The same arrangement can be used for line segments only, too.) The "query for a region" image shows how this would work, just change the caption to "insert a region." ;) A reference for this type of index, which is called a PMR-quadtree: http://www.cs.umd.edu/~hjs/pubs/NelsSIGG86.pdf http://www.cs.umd.edu/~hjs/pubs/NelsSIGG86.pdf Another good option for points is a KD-tree. You can't turn it into a hash, at least not straightforwardly, but it gives you some nice queries like n-nearest-neighbours, and can be done with as many dimensions as you like rather than just two. (Example use: accelerating the k-means clustering of big multivariate datasets.)