Advantages of R-trees in comparison to geohashes

Question

Geohashes are being widely used in products like: Lucene, mongodb, etc and have become one of the most important technology of present day.

Have Geohashes replaced the good old R-trees or do R-trees have any advantages as compared to Geohashes?

Answer 1

Geohash are very simple and effective way of indexing spatial features, particularly point features. Line and polygon features are little harder to index, but can be done. Geohash is a static hierarchical fixed size grid, overlayed on top of the earth surface. Grid cells of the same hierarchical level do not overlap. R-Tree is a dynamic grid which cell location and size change depending on the features they are indexing. R-Tree indexes features bounding boxes and cells change every time you insert and update data. Geohash is mostly used for indexing point features and cells do not change with every insert and update of data. Geohash cells do not adopt to the features like with R-tree.

Some of the advantages of geohash (comparing to r-tree) could be:

• easy implementation
• no performance degradation with growing number of features
• proximity searches (partially true)

Some of the disadvantages of geohash (comparing to r-tree) could be:

• arbitrary precision of grid
• harder to index (and query) line and polygon features
• size of the index could be large with some methods of line and polygon indexing
• by the specifications, it can be only used with longitude/latitude coordinate system, although the same method could be applied to other coordinate systems also

Those products (databases) that you mentioned use geohash because geohash is mainly used for indexing points and there are lot of applications that need such a feature. Lines and polygons are not that often used (except for the GIS applications of course), so why bother with it. Other reason, is of course, ease of implementation. Geohash converts two-dimensional coordinate to one-dimensional value. This is called dimensional reduction. One-dimensional value is easy to indexed by standard b-tree which is mostly used in those products.

I have to mention that there are similar algorithms to geohash but most of them are proprietary and require licensing. Geohash is in public domain. This could be also the reason for such a large usage in the recent years.

There are probably some other advantages and disadvantages, but these are first that come to my mind. I hope my explanation helps a little bit.