# Geospatial Indexing: R-Trees, Quadtrees, Geohash, and H3

I once watched a "why is this spatial query slow" investigation waste two days because everyone involved assumed a regular B-tree index on `latitude` and `longitude` columns was doing something useful. It wasn't, really — an index on latitude alone tells you nothing about longitude, and vice versa, so the query planner ended up scanning a huge slice of one dimension and filtering the other in memory. That's the whole problem in one sentence: [a B-tree indexes one-dimensional, sortable data](btree-vs-lsm-storage-engines), and a point on a map is fundamentally two-dimensional with no single natural sort order that preserves "nearby in the real world" as "nearby in the index." Spatial data needs structures built specifically for that locality property, and there are four worth knowing, each with a genuinely different trade-off.

This is the index layer underneath a problem like [finding the nearest hospital at scale](spark-geospatial-nearest-hospital-emr) — that article solves a concrete nearest-neighbor join; this one explains the structures that make queries like it fast in the first place.

## Why can't you just index latitude and longitude with a B-tree?

Because "sorted by latitude" and "sorted by longitude" are two entirely different orderings, and a query that needs both (a bounding-box or radius search) can only use one of them as an actual index scan — the other dimension has to be filtered after the fact, against a result set that's often far larger than the final answer, because "sorted by latitude" tells you nothing about which of those latitude-matching rows are also close in longitude. A composite B-tree index over both columns doesn't fix this either, because B-tree composite indexes are still fundamentally hierarchical by column order — great for "latitude range, then longitude equality," useless for a genuinely two-dimensional proximity search. Spatial indexes exist specifically to preserve two-dimensional locality: things that are physically near each other need to end up near each other in the index structure too, which none of the structures a B-tree is built from can guarantee.

## How does an R-tree preserve spatial locality?

An **R-tree** organizes spatial objects into a hierarchy of **minimum bounding rectangles (MBRs)** — each leaf holds actual geometries (points, polygons), and each internal node holds a rectangle that tightly bounds everything beneath it. A search (find everything within this area, or nearest to this point) walks down from the root, only descending into child rectangles that could possibly overlap the query region, pruning entire subtrees that clearly don't. R-trees handle more than points natively — bounding boxes and polygons work directly, which is exactly why R-trees are the standard structure inside **PostGIS** and most traditional spatial databases, where geometries are frequently polygons (parcels, boundaries, service areas) rather than bare points.

The real weakness is insertion cost under heavy write load: keeping the bounding-rectangle hierarchy both tight (rectangles that don't overlap much, for efficient pruning) and balanced requires real rebalancing work on insert, and R-trees can degrade meaningfully if that maintenance isn't kept up — a real operational concern for write-heavy spatial workloads, as opposed to the largely read-heavy, mostly-static-geometry workloads (parcel boundaries, road networks) R-trees were originally built to serve well.

## How does a quadtree simplify the same idea?

A **quadtree** recursively divides two-dimensional space into four quadrants, subdividing further only where data density warrants it — a densely populated area gets subdivided many times into small cells, a sparse area stays as one large cell. This is a genuinely simpler structure than an R-tree (fixed, regular subdivision rather than data-driven bounding rectangles that have to be actively maintained and rebalanced), which is exactly why quadtrees are common in mapping and tile systems — web map tile pyramids are essentially a quadtree's structure made visible, with each zoom level corresponding to a subdivision depth. The trade against an R-tree's flexibility: a quadtree's regular grid-based subdivision is a less precise fit for irregularly-shaped or irregularly-distributed geometries than an R-tree's data-adaptive bounding rectangles.

## What is geohashing, and what does it give up for the convenience of a plain string?

**Geohashing** encodes a latitude/longitude pair into a single base32 string by interleaving binary subdivisions of each dimension — the practical payoff is that a geohash is just a string, so it can be indexed with an ordinary B-tree, sorted, and prefix-matched, no specialized spatial index infrastructure required at all. Two points that are physically close usually share a long common prefix, so "find things near here" becomes approximately "find rows whose geohash starts with this prefix" — a query shape any database already knows how to serve efficiently.

The catch is the **edge problem**: geohash cells are rectangular and aligned to a fixed grid, so two points that are physically adjacent but happen to fall on opposite sides of a cell boundary can have completely different geohash prefixes despite being meters apart — naive prefix-based proximity search silently misses them. Real implementations compensate by checking a small set of neighboring cells alongside the exact prefix match, which works but adds real complexity to what geohashing otherwise sells as "just use a string index."

## Why does Uber's H3 use hexagons instead of squares?

**H3**, Uber's hexagonal hierarchical geospatial indexing system (open-sourced in 2018), divides the Earth's surface into a multi-resolution grid of hexagonal cells, each with a stable numeric identifier. The deliberate choice of hexagons over squares solves a specific distortion problem square grids (including geohash's rectangular cells) have: a square cell has two different kinds of neighbors — four that share a full edge and four more that only touch at a corner, with genuinely different distances to the cell's center. A hexagonal cell's six neighbors are all edge-adjacent and roughly equidistant from the center, which means "nearby cells" in a hexagonal grid actually correspond much more consistently to "nearby in real distance" than a square grid's neighbor relationships do. That consistency matters directly for spatial aggregation and joins — bucketing points into H3 cells and aggregating by cell, or joining two datasets by shared cell ID, produces far less directional bias than the equivalent operation on a square or rectangular grid, which is exactly the workload H3 was built for inside modern data platforms doing ride-density analysis, delivery-zone aggregation, or any spatial join at scale.

| Structure | Best for | Weakness |
| --- | --- | --- |
| **R-tree** | Polygons and bounding boxes, PostGIS-style spatial databases, read-heavy workloads | Expensive rebalancing under heavy writes |
| **Quadtree** | Point data with non-uniform density, map tile systems | Less precise fit for irregular geometries than R-trees |
| **Geohash** | Reusing an ordinary B-tree/string index, simple proximity prefix search | Edge problem — physically close points can have unrelated prefixes near cell boundaries |
| **H3** | Spatial aggregation and joins at scale, distributed systems needing shardable cell IDs | Points only — no native support for arbitrary polygons the way R-trees have |

```mermaid
graph TD
    Q["Spatial query need"]
    Q -->|"polygons, boundaries,PostGIS-style workload"| RT["R-tree"]
    Q -->|"map tiles, adaptivepoint density"| QT["Quadtree"]
    Q -->|"want to reuse a plainB-tree/string index"| GH["Geohash"]
    Q -->|"aggregation/join at scale,low directional bias"| H3["H3 hexagonal grid"]
          
```

Four structures for the same underlying problem — preserving two-dimensional locality — chosen by what the workload actually needs: geometry type, index infrastructure already available, or aggregation behavior at scale.

Most mainstream databases now bake one of these in rather than requiring a separate spatial extension for basic cases — PostGIS's R-tree-backed GiST indexes are the standard for Postgres, and MongoDB ships native `2dsphere` geospatial indexing for exactly this class of query without needing an external library.

**Geohash's edge problem is the trap I've seen bite teams hardest, because it fails silently — the query returns results, just not all of them, and nothing errors to tell you a real nearby point got missed.** A "find restaurants within 500m" feature built on naive geohash prefix matching will work correctly in testing (where test points rarely land near a cell boundary by chance) and then quietly under-return in production for users who happen to be near a boundary — which, at scale, is a meaningful fraction of real queries. If you're building proximity search on geohash, implement the neighbor-cell check from day one rather than discovering the gap from a support ticket about a restaurant "not showing up" for a user standing right next to it.

## What to carry away

A B-tree can't index spatial data meaningfully because latitude and longitude are two independent orderings, and a query that needs both loses the locality guarantee an index exists to provide. R-trees preserve that locality through a hierarchy of bounding rectangles and are the right default for polygon-heavy, read-heavy spatial databases like PostGIS; quadtrees trade some of an R-tree's precision for simpler, regular subdivision well-suited to map tile systems; geohash trades genuine spatial precision (the edge problem) for the convenience of reusing an ordinary string index; and H3's hexagonal grid solves the neighbor-distance distortion square-based grids have, which is exactly why it's become the default choice for spatial aggregation and joins at scale rather than point lookups alone.

None of the four is a strictly better choice than the others — match the structure to what the workload actually needs (polygon support, tile-system integration, index-infrastructure reuse, or low-bias aggregation), the same way choosing among B-tree, hash, and bitmap indexes comes down to matching structure to query shape rather than picking a single default and hoping it fits everything.