Geospatial Indexing (Geohash, Quadtree, S2 & H3)

1. What It Is & Why It Exists

The Core Problem: 2D Coordinates on 1D Database Indexes

Relational and NoSQL databases index 1D scalar values (strings, integers, timestamps) with $O(\log N)$ efficiency using B-Trees or LSM-Trees. Geographic locations, however, are inherently two-dimensional:

Executing proximity bounding box queries on standard separate 1D database indexes:

sqlCopy
SELECT * FROM venues WHERE lat BETWEEN 37.70 AND 37.80 AND lon BETWEEN -122.50 AND -122.40;

Forces the database engine to either scan all records matching the latitude filter and filter longitude in memory, or compute the expensive set intersection of two massive 1D index scans. Under high throughput, this results in high disk I/O and query latency that grows with the size of the latitude band.

The First-Principles Solution: Space-Filling Curves

Geospatial Indexing projects 2-dimensional continuous planetary coordinates onto a 1-dimensional discrete line using Space-Filling Curves (Z-Order Curve or Hilbert Curve). Because points located near each other on the 2D surface are usually mapped to nearby values on the 1D curve (not always: see §5.1), spatial proximity queries become a few $O(\log N)$ range scans on standard B-Tree indexes.

Synthesizing vector architecture diagram...

One point (San Francisco) enters at the top and is encoded four ways, one per branch. Geohash interleaves latitude and longitude bits into a string ('9q8yyk'), so nearby places usually share a prefix and a normal B-tree prefix query finds neighbors, though points just across a cell border may share no prefix, so you also check the 8 surrounding cells. S2 projects the Earth onto a cube and numbers cells along a Hilbert curve, a 64-bit ID with low distortion even near the poles. H3 uses hexagons, whose six neighbors are all the same distance away, which makes radius and ring searches uniform. A quadtree lives in memory and splits a cell into four only where points are dense. The first three give fixed IDs you can store and index in any database; the quadtree adapts to how dense the data is.

2. Core Mechanics & Algorithmic Architectures

1. Geohash (Z-Order Curve Interleaving)

• Mechanics: Recursively divides the world into binary bounding boxes. Latitude $[-90, +90]$ and Longitude $[-180, +180]$ are converted into binary bit sequences and interleaved: $\text{Bitstream} = \lambda_0 \phi_0 \lambda_1 \phi_1 \lambda_2 \phi_2 \dots$
• Grouped into 5-bit chunks and encoded into Base32 characters (0-9, b-z excluding a, i, l, o).
• Prefix Property: A longer common prefix means a smaller shared cell, so the points are closer (e.g. 9q8yy is inside 9q8y). The reverse does not hold: two close points on either side of a cell border can share a short prefix or none (§5.1).

2. Google S2 (Hilbert Curve on Cube Projection)

• Projects the 3D Earth sphere onto the 6 faces of a cube, then maps each face using a 1D Hilbert Curve.
• Provides 64-bit integer Cell IDs across 31 hierarchical levels, 0 to 30 (Level 0 = entire cube face, Level 30 $\approx 0.74\text{ cm}^2$ on average).
• Fairly uniform cell areas across equatorial and polar regions: at any one level the largest cell is only about 2.1 times the smallest.

3. Uber H3 (Hexagonal Hierarchical Spatial Index)

• Tessellates the globe into Hexagonal cells across 16 resolution levels (0 to 15), plus 12 pentagons per resolution, placed over the oceans, which have 5 neighbors.
• The Hexagon Advantage: Unlike squares (where orthogonal neighbors are distance $1$ and diagonal corner neighbors are distance $\sqrt{2}$), every hexagonal cell has 6 equidistant neighbors with the same centroid distance (on the sphere, very nearly the same): $D(\text{Center}, \text{Neighbor}_i) = \text{Constant } \forall i \in [1, 6]$
• Ideal for ride-sharing dispatch radius computations, surge pricing, and spatial smoothing.

Synthesizing vector architecture diagram...