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: $\text{Point} = (\text{Latitude } \phi, \text{Longitude } \lambda)$

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 $> 500\text{ ms}$.

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 mapped to nearby values on the 1D curve, spatial proximity queries can be executed with blazing $O(\log N)$ speed on standard B-Tree indexes.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

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: Longer common prefixes denote closer spatial proximity (e.g. 9q8yy is inside 9q8y).

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 30 hierarchical levels (Level 0 = entire cube face, Level 30 $\approx 1\text{ cm}^2$).
• Highly uniform cell areas across equatorial and polar regions with minimal distortion.

3. Uber H3 (Hexagonal Hierarchical Spatial Index)

• Tessellates the globe into Hexagonal cells across 16 resolution levels.
• 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 identical centroid distances: $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.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

3. Comprehensive Spatial Engine Comparison Matrix