How Geospatial Indexes Actually Work (R-Trees, GeoHashes, and 'Nearby Restaurants')

Quick Answer

Geospatial indexes solve a problem normal B-tree indexes can't: finding points that are physically close together without scanning the whole table. Geohashes interleave latitude and longitude bits into a single sortable string so nearby points share a text prefix, while R-trees organize data into nested bounding rectangles so a search can discard huge chunks of the map that can't possibly contain a match. Both turn an O(n) distance scan into something closer to O(log n).

Why "Show Me Nearby Restaurants" Breaks a Normal Database Index

A regular database index (a B-tree, the thing behind every CREATE INDEX you've ever run) is built for one-dimensional comparisons: "give me every row where price is between 100 and 500" or "find the row where id = 9281." It works because a B-tree keeps keys in sorted order, so it can binary-search its way down in O(log n).

Latitude and longitude break that assumption. If you index latitude and longitude as two separate B-tree columns and then ask "find restaurants within 2 km of (12.9716, 77.5946)," the database has no single sorted order that keeps nearby points next to each other. Sorting by latitude puts Bengaluru and a random point in Afghanistan at similar index positions if they happen to share a latitude band, while two restaurants 50 metres apart on the same street can land far apart in a latitude-sorted B-tree because their longitudes differ. A composite index on (lat, lon) doesn't fix this either — it just means the database is still sorted primarily by one axis, so a "nearby" query degenerates into scanning a wide latitude band and then filtering almost everything out by longitude and actual distance.

This is the real problem geospatial indexes solve: how do you take two-dimensional (or three-dimensional, if you care about altitude) data and arrange it so that points which are physically close to each other also end up close to each other in whatever structure you're searching. There are two genuinely different families of answer to this, and production systems usually use one or the other depending on what they're optimizing for: space-filling curves (geohashes being the most common) that squash 2D coordinates into a single sortable string, and tree structures built from bounding boxes (R-trees) that organize the data by spatial containment instead of by sort order.

Geohashing: Turning Two Numbers Into One Sortable String

A geohash takes a (latitude, longitude) pair and produces a short string like tdr1vfjve that you can store in a normal, boring, B-tree-indexed text column. The trick is bit interleaving. The algorithm repeatedly bisects the longitude range (-180 to 180) and the latitude range (-90 to 90), alternating between the two axes, and records a 1 if the point is in the upper half of the current range or a 0 if it's in the lower half. Every bisection narrows the box the point could be in. After enough bisections, you have a bitstream that uniquely identifies a small rectangle on Earth, and that bitstream gets packed 5 bits at a time into a base32 alphabet to make it human-readable.

Here's a real, runnable implementation — not pseudocode — and real output from running it:

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

def geohash_encode(latitude, longitude, precision=9):
    lat_range = [-90.0, 90.0]
    lon_range = [-180.0, 180.0]
    geohash = []
    bits = [16, 8, 4, 2, 1]
    bit = 0
    ch = 0
    even_bit = True  # start with longitude
    while len(geohash) < precision:
        if even_bit:
            mid = (lon_range[0] + lon_range[1]) / 2
            if longitude > mid:
                ch |= bits[bit]
                lon_range[0] = mid
            else:
                lon_range[1] = mid
        else:
            mid = (lat_range[0] + lat_range[1]) / 2
            if latitude > mid:
                ch |= bits[bit]
                lat_range[0] = mid
            else:
                lat_range[1] = mid
        even_bit = not even_bit
        if bit < 4:
            bit += 1
        else:
            geohash.append(BASE32[ch])
            bit = 0
            ch = 0
    return "".join(geohash)

Before trusting this on real data, it's worth checking it against a known answer. The geohash algorithm has a well-known public test vector: latitude 57.64911, longitude 10.40744 is documented (including on Wikipedia's geohash page) as encoding to u4pruydqqvj. Running the function above on exactly those coordinates with precision 11 prints u4pruydqqvj — an exact match, which confirms the bit-interleaving logic is correct and not just plausible-looking.

Now the actual point of the exercise — real coordinates for Indian cities, run through the function above, with the real strings it produced:

Mumbai (Gateway of India):  lat=18.922,  lon=72.8347 -> geohash(9)=te7g9ksse
Delhi (India Gate):          lat=28.6129, lon=77.2295 -> geohash(9)=ttnfv2uf1
Bengaluru (MG Road):         lat=12.9758, lon=77.6045 -> geohash(9)=tdr1vfjve

Notice Mumbai starts with t and Delhi starts with t too — that's coincidence at 1 character of precision, Earth only has so many first-letter buckets. What actually matters is what happens when two points are genuinely close together versus genuinely far apart, which is the property the whole structure depends on.

The Shared-Prefix Property — and Where It Honestly Breaks

The useful property of a geohash is that nearby points share a prefix, and the longer the shared prefix, the closer the points are likely to be — because every character you add is another bisection narrowing the box further. This is what makes a geohash column useful in a normal database: a "nearby" query becomes a prefix search (WHERE geohash LIKE 'tdr1%'), which a standard B-tree index handles natively and efficiently, instead of needing a specialized spatial index type.

Testing this for real: MG Road in Bengaluru (12.9758, 77.6045) and a point in Koramangala about 9 km away (12.9352, 77.6245) produce the geohashes tdr1vfjve and tdr1w6u3j. Shared prefix: tdr1 — 4 characters. Two points roughly 70 metres apart near the same MG Road coordinate produce tdr1vfjve and tdr1vfnpz — shared prefix tdr1vf, 6 characters, correctly reflecting that they're far closer together than the Koramangala pair. And Mumbai versus Delhi, roughly 1,150 km apart, share only the single leading t — both cities happen to be in the same enormous northern-hemisphere longitude-ish bucket at the coarsest level, and nothing more. The pattern holds: more shared prefix characters, physically closer points.

But there's a real failure mode you need to know about before reaching for geohashes, and it's not a minor footnote — it's the thing that bites people in production. Because each character represents a bisection of a rectangle, two points that are extremely close together but happen to fall on opposite sides of a bisection boundary get completely different geohashes with almost no shared prefix, even though they might be 2 metres apart. A restaurant at the edge of one geohash cell and a restaurant across the street, just inside the neighbouring cell, can disagree on every character. This is why real "find nearby points" implementations built on geohashes don't just do a prefix match on the point's own geohash — they compute the geohash of the search center, then also check the 8 neighboring cells (the geohash's neighbours in each compass direction) so that boundary-adjacent points aren't missed. Elasticsearch's geo_point queries and most geohash-based proximity search implementations do exactly this under the hood; it's not optional, it's required to get correct results near any cell edge.

R-Trees: Indexing by Containment Instead of by Sort Order

Geohashes squash 2D data into a 1D string so a normal index can handle it. R-trees take the opposite approach: they're a tree structure purpose-built for 2D (or n-dimensional) data, and they never lose the "two-dimensional-ness" of the problem. The R-tree was introduced by Antonin Guttman in 1984 and remains the most widely used spatial index structure in real database systems (PostGIS's GiST indexes, MySQL's spatial indexes, and most GIS software all use R-tree variants).

The core idea: every object being indexed — a point, a restaurant, a building footprint — gets wrapped in the smallest rectangle that fully contains it, called a minimum bounding rectangle (MBR). Nearby objects get grouped together and their individual MBRs get wrapped in a single larger MBR, which becomes a node one level up in the tree. This repeats recursively, so the root of an R-tree is one giant rectangle covering everything, and each level down splits that area into progressively smaller, tighter rectangles, until you reach the leaves, which hold the actual data.

The payoff is in how search works. Say you want everything within a given rectangle (a map viewport, for instance). You start at the root and check: does the query rectangle overlap this node's bounding box at all? If it doesn't overlap, you can discard that entire subtree and everything inside it without looking at a single one of the (possibly thousands of) objects it contains — because if the query doesn't intersect the bounding box, it's mathematically impossible for it to intersect anything inside that box. You only recurse into children whose bounding boxes actually overlap the query. This is the same pruning principle a B-tree uses to skip half the data at every comparison, just adapted to rectangles instead of scalar values. Nearest-neighbor queries work similarly, using a best-first search that keeps a priority queue of unexplored nodes ranked by their minimum possible distance to the query point (MINDIST), expanding the most promising candidate first — in practice this gives roughly O(log n) average-case performance for nearest-neighbor lookups, the same ballpark as a balanced tree lookup, despite working in two dimensions instead of one.

Geohash vs. R-Tree: Different Trade-offs, Not a Strict Upgrade

These aren't two competing implementations of the same idea — they trade off differently, and production systems pick based on what they actually need:

• Geohashes are simple strings, so they slot into any database that already has a B-tree text index — no special index type required. That's why Redis's GEOADD/GEORADIUS commands and MongoDB's legacy 2D geo indexes are built on geohash-like encodings. The cost is the boundary problem above (needing to check neighbor cells) and the fact that geohash cells aren't square — they're wider near the equator and distorted near the poles, so "nearby in geohash space" isn't perfectly "nearby in real distance" everywhere on Earth.
• R-trees handle arbitrary shapes, not just points — polygons, lines, bounding boxes of buildings — because everything ultimately reduces to "does this rectangle overlap that rectangle," which works regardless of the underlying geometry's complexity. They need a dedicated index structure (PostGIS's GiST, for example) rather than reusing a plain B-tree, and they're the right choice when your queries are genuinely about geometric overlap and containment, not just "points near a point."
• In practice, a lot of production "nearby search" (food delivery apps, ride-hailing driver matching, store locators) leans on geohash-family encodings precisely because they're cheap to bolt onto an existing database, and the boundary edge case is a solved, well-understood problem rather than a blocker. Google's S2 geometry library, which Uber and others use internally, is a more sophisticated space-filling-curve approach solving the same equator-distortion problem geohashes have, using a different curve (Hilbert curve on a cube-projected sphere) — same family of idea, more careful math.

What "Nearby Restaurants" Actually Does End to End

Put together, a real "restaurants near me" feature typically does this: the app gets your GPS coordinates, computes the geohash (or S2 cell, or inserts into an R-tree-backed spatial index) for your location, and issues a query that's really a bounding-box or prefix-and-neighbors search against the restaurant table's spatial index — not a brute-force "compute distance to every restaurant in the country and sort," which is what a naive implementation without any spatial index would have to do. The spatial index's entire job is turning "is this point within X km of this other point" from an O(n) full scan into something closer to O(log n), the same way a B-tree turns "find this value" from a linear scan into a binary search.

Once the index has narrowed the candidates down to a small set — a few dozen restaurants near the matching geohash cells, or a handful of R-tree leaf nodes whose bounding boxes overlap your search radius — the application does the precise distance calculation (usually the haversine formula, which accounts for Earth's curvature) only on that small shortlist, not the full dataset. The index's job was never to compute exact distance; it was to cheaply eliminate everything that couldn't possibly be a candidate, leaving a small enough set that exact math is affordable.

Frequently Asked Questions