Compare Geohash & R-Tree Indexing

Geohash Indexing vs. R-Tree Indexing

Here we talk about the comparison between Elasticsearch, and PostGIS, so it is always good to look further into how these two different databases perform indexing & geo-searches internally and compare each other.

Elasticsearch uses Geohash indexing primarily to speed up the geo-searches and PostGIS uses GiST indexing which is a variant of R-tree implementation.

Geohash and R-tree are two different indexing approaches used in the context of geospatial data for efficient searching/filtering, here are some differences:

Geohash (e.g Elasticsearch)	R-tree (e.g PostGIS)
Geohash encodes coordinates into a string of characters, it divides the Earth into a grid of cells and represents locations as a combination of characters indicating their positions into the grid.	R-tree is a tree structure used for spatial indexing. It organises spatial objects into a hierarchy of nodes.
Geohash is simple, straightforward to implement and easy to use.	R-tree indexing is capable of handling complex queries ie. intersect, within, or overlap etc.
Geohash is is good for proximity searches and finding nearly by locations efficiently.	R-tree is slower in proximity search as compare to Geohash.
Elasticsearch uses Geohash indexing for simple geo-searches.	Early versions of PostGIS used the PostgreSQL R-Tree indexes. However, PostgreSQL R-Trees have been completely discarded since version 0.6, and spatial indexing is provided with an R-Tree-over-GiST scheme.

GiST Indexes (a variant of the R-Tree index)

GiST stands for Generalized Search Tree. It is a balanced, tree-structured access method, that acts as a base template in which to implement arbitrary indexing schemes. B-tree, R-trees, and many other indexing schemes can be implemented in GiST.

During GiST indexing for GIS data, spatial data is organized in the R-Tree structure by its spatial relationships, such as "adjacency (above, below, to the left, and to the right)", "intersects", and "contains".

GiST is also suitable for facilitating searches for various data types, including spatial data. The GiST index is the most common type of spatial index, which is suitable for most use cases. Other types include SP-GiST, BRIN, and B-tree. In this design, we are going with the GiST index in this design but as we iterate and look for improving performance we can explore other types too ie. SP-GIST etc.