Geospatial Indexing: Geohash, Quadtree, S2, and H3

Geospatial indexing organizes locations so a query such as "all restaurants within 2 km of this point" avoids scanning every row. A location is a pair (latitude, longitude). Searching by both coordinates is a two-dimensional problem, and ordinary one-dimensional indexes handle it poorly.

The problem with plain indexes

With a B-tree index on latitude and another on longitude, a bounding-box query selects a wide horizontal band by one index and a wide vertical band by the other, then intersects them. Each band can contain a large fraction of all rows even when the result is small. A composite index (lat, lng) narrows by latitude first and only then longitude, which gives the same band problem.

Geospatial indexes solve this by mapping two-dimensional space to a form that preserves locality: nearby points get nearby keys or the same cell identifier. There are two families:

• Space-filling curve / grid cell indexes: geohash, S2, H3. Each point maps to a cell ID that can be stored in an ordinary index or used as a partition key.
• Tree indexes: quadtree, R-tree, k-d tree, which partition space adaptively.

Geohash

A geohash encodes a point as a string by repeatedly halving the coordinate ranges.

1. Start with longitude [-180, 180] and latitude [-90, 90].
2. Alternate between longitude and latitude. Each step halves the current range and emits bit 0 (lower half) or 1 (upper half).
3. Group the interleaved bits in fives and encode each group as one character of a base-32 alphabet (0123456789bcdefghjkmnpqrstuvwxyz).

Properties:

• Each extra character makes the cell smaller. Length 4 is a cell of roughly 39 km by 20 km, length 6 roughly 1.2 km by 0.6 km, and length 8 roughly 38 m by 19 m at the equator.
• Prefix property: a longer geohash shares its prefix with the containing cell. A prefix query (LIKE 'u4pru%') returns all points in a cell, and it works on any sorted index or as a key range.
• Cells at the same length have the same dimensions at a given latitude, so choosing a length gives a search resolution.

public class Main {
    private static final String ALPHABET = "0123456789bcdefghjkmnpqrstuvwxyz";

    static String geohash(double lat, double lng, int len) {
        double[] latRange = {-90.0, 90.0};
        double[] lngRange = {-180.0, 180.0};
        var out = new StringBuilder();
        int bits = 0;
        int bitCount = 0;
        boolean useLng = true;
        while (out.length() < len) {
            double[] range = useLng ? lngRange : latRange;
            double value = useLng ? lng : lat;
            double mid = (range[0] + range[1]) / 2.0;
            bits <<= 1;
            if (value >= mid) {
                bits |= 1;
                range[0] = mid;
            } else {
                range[1] = mid;
            }
            useLng = !useLng;
            bitCount++;
            if (bitCount == 5) {
                out.append(ALPHABET.charAt(bits));
                bits = 0;
                bitCount = 0;
            }
        }
        return out.toString();
    }

    public static void main(String[] args) {
        String full = geohash(57.64911, 10.40744, 11);
        System.out.println(full);
        System.out.println("length 6 cell: " + full.substring(0, 6));
        // A point about 100 m away falls in the same length-6 cell.
        System.out.println("nearby point:  " + geohash(57.64990, 10.40800, 6));
    }
}

u4pruydqqvj
length 6 cell: u4pruy
nearby point:  u4pruy

Limitations:

• Boundary problem. Two adjacent points can lie on opposite sides of a cell boundary and share no prefix, notably across the prime meridian or equator. A proximity search must therefore query the target cell and its 8 neighbors.
• Cell shape distortion. Cells are rectangles in latitude-longitude space, so they get narrower in ground distance toward the poles.
• Results in the neighbor cells may lie beyond the search radius, so candidates are filtered by exact distance (the haversine formula for great-circle distance).

Quadtree

A quadtree recursively divides a 2D region into four quadrants. A node splits into four children when it holds more than a threshold number of points (for example 100).

• Insert: descend to the leaf covering the point. If the leaf exceeds capacity, split it and redistribute the points.
• Search by radius or box: descend from the root, visiting only nodes whose region intersects the query area. Collect points from the leaves, then filter by exact distance.
• The tree adapts to density: dense cities have deep, small leaves, and oceans stay as single large leaves.

flowchart TD
    root["Root: whole map"] --> nw["NW quadrant: sparse, leaf"]
    root --> ne["NE quadrant: dense, split"]
    root --> sw["SW quadrant: leaf"]
    root --> se["SE quadrant: leaf"]
    ne --> ne1["NE-NW leaf"]
    ne --> ne2["NE-NE leaf"]
    ne --> ne3["NE-SW leaf"]
    ne --> ne4["NE-SE leaf"]

Trade-offs versus geohash:

A quadtree over hundreds of millions of points can be held in memory on a single service instance, and rebuilt or updated periodically. Frequently moving objects (vehicles) cause many updates, so systems often use a grid or a geohash key in an in-memory store instead.

S2 and H3

S2 (Google) projects the Earth's sphere onto the six faces of a cube and subdivides each face as a quadtree. Cells are ordered along a Hilbert curve, so each cell has a 64-bit ID, and cells close on the curve are close in space. Hierarchical levels from 0 to 30 give cell sizes from continent-scale to about a centimeter. A region is covered by a set of cells at mixed levels (a region covering), and each cell in the covering becomes an ID range scan. S2 avoids most of the polar distortion of geohash. It is used by MongoDB's 2dsphere indexes and other systems.

H3 (Uber) divides the globe into hexagonal cells at 16 resolutions (0 to 15), built from an icosahedron projection (with 12 pentagon cells needed to close the sphere). Hexagons have a useful property: all six neighbors of a cell are at a similar distance from its center, unlike square cells where diagonal neighbors are farther. This makes distance-based aggregation and smoothing more uniform. H3 is used for ride-hailing supply and demand aggregation and spatial analytics.

Proximity search approach

To find points within radius r of a query point:

1. Choose the cell size (geohash length, S2 level, or H3 resolution) so that a cell is comparable to r.
2. Compute the cell containing the query point and its neighbors, or the cells covering the query circle.
3. Fetch the candidate points from those cells (index lookup by cell ID or prefix).
4. Compute the exact distance to each candidate and discard those beyond r.
5. Sort the rest by distance and return the top results.

Example: a query for restaurants within 1 km. A geohash of length 6 has cells of about 1.2 km (east-west) by 0.6 km (north-south). A 3 by 3 block of the query cell and its 8 neighbors guarantees only one cell width of coverage in each direction from the query point, which is about 0.6 km north-south. That does not cover a 1 km radius. Length 5 has cells of about 4.9 km by 4.9 km, so the 3 by 3 block covers the radius at the cost of more candidate points. The exact-distance filter in step 4 removes the candidates beyond 1 km.

If too few results return, expand the search to the next larger ring of cells or a coarser level, and repeat.

sequenceDiagram
    participant C as Client
    participant S as Search service
    participant I as Cell index
    C->>S: query (lat, lng, radius)
    S->>S: compute cell and neighbor cells
    S->>I: fetch points for each cell
    I-->>S: candidate points
    S->>S: filter by exact distance, sort
    S-->>C: nearest results

Storage options: a table with an indexed cell_id column; a Redis sorted set with geohash scores (the GEOADD and GEOSEARCH commands are built on this); PostGIS with R-tree style GiST indexes; and Elasticsearch geo fields. Partitioning by cell ID or by the consistent hash of a coarse cell spreads load, though hot cells such as city centers need finer subdivision or replication.

Interview questions

• Why can't a composite (lat, lng) index answer a radius query efficiently? It narrows by latitude only, producing a wide band of rows that must all be checked for longitude. Cell-based indexes map two dimensions to one key that preserves locality.
• Why must a geohash search query neighboring cells? Nearby points can fall on opposite sides of a cell boundary and have different prefixes. Querying the 8 neighbors covers points near the edges.
• Geohash or quadtree for a dense, unevenly distributed data set? A quadtree adapts cell size to density, so each leaf holds a bounded number of points. A geohash grid is uniform, so dense areas have many points per cell unless a longer prefix is used.
• What advantage do H3 hexagons have over square cells? Every neighbor is adjacent by an edge and at a similar distance from the center, so neighbor and distance computations are more uniform.