Designing a Geospatial Search System: Spatial Indexes, Proximity Queries, and Location-Based Services at Scale

Every ride-sharing app, food delivery platform, and social proximity feature runs on the same core primitive: given a point on Earth, find everything within N meters as fast as possible. The query looks deceptively simple. The operational reality is not.

At 10,000 active users, a naive bounding-box query against a Postgres table with a B-tree index on latitude and longitude will work. At 1 million active drivers updating their position every four seconds, the same approach will melt your database. Understanding why requires knowing what happens inside a spatial index, not just which SQL function to call.

This article covers the four dominant spatial indexing strategies, how proximity queries execute against each, and the architecture decisions that separate a working prototype from a production location-based service.

---

The Failure Mode: Why Standard Indexes Break on Spatial Data

A B-tree index on a single dimension orders values linearly. A point at (lat: 37.7749, lng: -122.4194) has no natural single-dimensional ordering that preserves spatial locality. Two points one meter apart in San Francisco can have wildly different B-tree positions depending on whether you index by latitude or longitude.

The result: a query for “all drivers within 500 meters of this intersection” requires the planner to either scan the full index (slow) or intersect two range scans (one on lat, one on lng) and then discard false positives. At low cardinality this is acceptable. At millions of rows being updated every few seconds, you burn through I/O budget on rows that will be filtered out immediately.

Spatial indexes solve this by encoding two-dimensional locality into a one-dimensional structure that can be indexed with a B-tree. The encoding strategy is what distinguishes R-trees, geohash, S2, and H3.

---

Spatial Indexing Strategies

R-Trees

R-trees organize points into nested bounding rectangles (minimum bounding rectangles, or MBRs). A leaf node contains a small set of points. Each internal node stores the MBR that contains all its children. To answer a proximity query, the tree is traversed top-down: if a node’s MBR does not intersect the query region, the entire subtree is pruned.

PostGIS uses the GiST index type, which is an R-tree variant optimized for Postgres page layouts. When you run:

SELECT id, ST_Distance(location, ST_MakePoint(-122.4194, 37.7749)::geography) AS distance_meters
FROM drivers
WHERE ST_DWithin(
  location,
  ST_MakePoint(-122.4194, 37.7749)::geography,
  500  -- meters
)
ORDER BY distance_meters
LIMIT 20;

The planner uses the GiST index to find candidate rows whose MBRs intersect the 500-meter circle, then applies the exact ST_DWithin check to discard false positives. The ratio of candidates to final results depends on how dense and evenly distributed your data is. In a city center at peak hours, that ratio can be 1.2:1. In sparse rural data, it can spike to 50:1.

Where R-trees break down: R-trees perform poorly when data distribution is highly skewed. Dense urban clusters force nodes to overlap heavily, degrading the pruning effectiveness. Updates also require re-balancing (splitting and merging nodes), which is expensive under high write throughput.

Geohash

Geohash maps the globe into a recursive grid. The first character divides Earth into 32 cells. Each subsequent character subdivides the parent cell into 32 more. A geohash of precision 6 (like 9q8yy) covers roughly a 1.2km x 0.6km rectangle.

The critical property: geographically nearby points share a common prefix. 9q8yy4 and 9q8yy5 are adjacent cells. This means you can answer a proximity query by finding the cell that contains your query point, computing the 8 neighboring cells at the same precision, and fetching all rows matching those 9 prefixes.

import Geohash from 'ngeohash';

function getProximityGeohashes(
  lat: number,
  lng: number,
  radiusMeters: number
): string[] {
  // Choose precision based on radius
  // Precision 5: ~5km cells, Precision 6: ~1.2km, Precision 7: ~150m
  const precision = radiusMeters <= 200 ? 7 : radiusMeters <= 1500 ? 6 : 5;

  const center = Geohash.encode(lat, lng, precision);
  const neighbors = Geohash.neighbors(center);

  return [center, ...Object.values(neighbors)];
}

// In Redis: store driver locations as geohash-indexed members
async function updateDriverLocation(
  redis: Redis,
  driverId: string,
  lat: number,
  lng: number
): Promise<void> {
  // Redis GEOADD uses a 52-bit geohash internally
  await redis.geoadd('drivers:active', lng, lat, driverId);
}

async function findNearbyDrivers(
  redis: Redis,
  lat: number,
  lng: number,
  radiusMeters: number,
  limit: number
): Promise<Array<{ id: string; distanceMeters: number }>> {
  const results = await redis.georadius(
    'drivers:active',
    lng,
    lat,
    radiusMeters,
    'm',
    'ASC',
    'COUNT',
    limit,
    'WITHDIST'
  );

  return results.map(([id, dist]) => ({
    id,
    distanceMeters: parseFloat(dist),
  }));
}

Redis’s GEOADD and GEORADIUS commands use a 52-bit geohash stored as a sorted set score. This gives sub-centimeter precision and O(N+log(M)) query complexity where N is results and M is total set size. For a typical city-level deployment, GEORADIUS with COUNT 20 runs in under 1ms.

Where geohash breaks down: Cells near the boundaries of precision zones can be close in physical space but have very different prefix strings. The 9-cell search covers this for most cases, but edge cases exist at the poles and at the cell boundaries of the first geohash character. Also, geohash cells are rectangular, not hexagonal, which means cells near the equator have different physical sizes than cells near the poles at the same precision level.

S2 Cells

S2 (Spherical geometry library from Google) maps the sphere onto six cube faces using a Hilbert curve. The key insight is that the Hilbert curve, unlike a Z-order curve, preserves locality much more consistently: nearby points on the curve are always nearby on the surface, though not all nearby points are adjacent on the curve.

Each S2 cell is identified by a 64-bit integer called a cell ID. Level 0 covers a full cube face. Level 30 covers roughly 1 cm². Proximity search requires computing a “cell covering” of your query region: a set of S2 cell IDs at varying levels that together cover the region.

import { S2 } from 's2-geometry';

interface S2CellCovering {
  cellIds: bigint[];
  minLevel: number;
  maxLevel: number;
}

function getCellCovering(
  lat: number,
  lng: number,
  radiusMeters: number
): S2CellCovering {
  const earthRadiusMeters = 6371000;
  const radiusRadians = radiusMeters / earthRadiusMeters;

  const cap = S2.S2Cap.fromAxisAngle(
    S2.S2LatLng.fromDegrees(lat, lng).toPoint(),
    radiusRadians
  );

  const coverer = new S2.S2RegionCoverer();
  coverer.setMaxCells(8);
  coverer.setMinLevel(10);
  coverer.setMaxLevel(14);

  const covering = coverer.getCovering(cap);
  const cellIds = covering.map(cell => cell.id().id);

  return {
    cellIds,
    minLevel: 10,
    maxLevel: 14,
  };
}

// Postgres query using S2 cell range queries
async function findNearbyPlaces(
  db: Pool,
  lat: number,
  lng: number,
  radiusMeters: number
): Promise<Place[]> {
  const covering = getCellCovering(lat, lng, radiusMeters);

  // Each S2 cell is a range on the cell ID space; fetch all ranges
  const cellRanges = covering.cellIds.map(cellId => {
    const cell = new S2.S2CellId(cellId);
    return { min: cell.rangeMin().id, max: cell.rangeMax().id };
  });

  const conditions = cellRanges
    .map((_, i) => `(s2_cell_id >= $${i * 2 + 3} AND s2_cell_id <= $${i * 2 + 4})`)
    .join(' OR ');

  const params: (number | bigint)[] = [lat, lng];
  cellRanges.forEach(r => params.push(r.min, r.max));

  const result = await db.query<Place>(
    `SELECT *,
       ST_Distance(location::geography, ST_MakePoint($2, $1)::geography) AS distance_m
     FROM places
     WHERE (${conditions})
       AND ST_DWithin(location::geography, ST_MakePoint($2, $1)::geography, ${radiusMeters})
     ORDER BY distance_m
     LIMIT 50`,
    params
  );

  return result.rows;
}

S2 is used in production by Google Maps and Foursquare. Its main advantage is uniform cell area at a given level: an S2 level-14 cell is approximately 600m² anywhere on Earth, whereas a geohash cell varies by latitude. This uniformity simplifies radius estimation and covering logic.

Where S2 breaks down: The library has no native support in most databases. You precompute cell IDs and store them as indexed integer columns, then query using range scans. This is fast but requires a build step and careful precision selection. The covering logic also returns more cells than strictly necessary at boundaries, which can increase the candidate set.

H3 (Uber’s Hexagonal Hierarchy)

H3 divides the globe into hexagonal cells at 16 resolution levels (0 through 15). Hexagons have a key geometric property that rectangles lack: all six neighbors are equidistant from the center. This makes ring-based proximity searches natural.

import * as h3 from 'h3-js';

function getH3Cells(
  lat: number,
  lng: number,
  radiusMeters: number
): string[] {
  // Resolution 9: ~175m edge length (~0.1km²)
  // Resolution 10: ~66m edge length (~0.015km²)
  const resolution = radiusMeters >= 500 ? 9 : 10;

  const centerCell = h3.latLngToCell(lat, lng, resolution);
  const kRings = Math.ceil(radiusMeters / (h3.getHexagonEdgeLengthAvg(resolution, 'm') * 2));

  // gridDisk returns all cells within k rings of the center
  const cells = h3.gridDisk(centerCell, kRings);

  return cells;
}

async function findDriversViaH3(
  db: Pool,
  lat: number,
  lng: number,
  radiusMeters: number
): Promise<Driver[]> {
  const cells = getH3Cells(lat, lng, radiusMeters);

  const result = await db.query<Driver>(
    `SELECT d.*,
       ST_Distance(d.location::geography, ST_MakePoint($1, $2)::geography) AS distance_m
     FROM drivers d
     WHERE d.h3_cell_r9 = ANY($3::text[])
       AND d.status = 'active'
       AND ST_DWithin(d.location::geography, ST_MakePoint($1, $2)::geography, $4)
     ORDER BY distance_m
     LIMIT 20`,
    [lng, lat, cells, radiusMeters]
  );

  return result.rows;
}

H3 is well-suited for density analysis and service area calculations in addition to proximity lookup. Uber uses it across their dispatch, surge pricing, and ETA systems because the hexagonal grid composes cleanly: a resolution-9 cell decomposes into exactly seven resolution-10 cells, which simplifies multi-resolution queries.

---

Architecture for High-Write Throughput

A ride-sharing dispatch system with 50,000 active drivers, each sending a location update every 4 seconds, generates 12,500 writes per second. Writing all of that directly to Postgres will exhaust connection pool and WAL write capacity quickly.

The production architecture separates the write path from the query path:

Driver App -> Location Ingestion Service -> Redis GEOADD (active set)
                                         -> Kafka (location stream)

Kafka -> Location Consumer -> Postgres (history, analytics)
                           -> H3 Cell Updater (precomputed cell assignments)

Rider App -> Dispatch Query -> Redis GEORADIUS (fast proximity)
                            -> Postgres (fallback, enrichment)

Redis handles the real-time proximity queries. Postgres handles the durable store, historical replay, and complex enrichment queries (does this driver have the right vehicle type? is their rating above threshold?). H3 cells stored in Postgres allow batch analytics that Redis sorted sets do not support efficiently.

interface LocationUpdate {
  driverId: string;
  lat: number;
  lng: number;
  heading: number;
  speedKmh: number;
  timestamp: number;
}

class LocationIngestionService {
  constructor(
    private redis: Redis,
    private producer: KafkaProducer
  ) {}

  async ingest(update: LocationUpdate): Promise<void> {
    // Fire-and-forget Redis update for real-time queries
    // Do not await to keep ingestion latency under 5ms
    const redisWrite = this.redis.pipeline()
      .geoadd('drivers:active', update.lng, update.lat, update.driverId)
      .hset(`driver:${update.driverId}:meta`, {
        heading: update.heading,
        speed: update.speedKmh,
        lastSeen: update.timestamp,
      })
      .exec();

    // Durable write to Kafka for downstream processing
    const kafkaWrite = this.producer.send({
      topic: 'location-updates',
      messages: [{
        key: update.driverId,
        value: JSON.stringify(update),
        timestamp: String(update.timestamp),
      }],
    });

    await Promise.all([redisWrite, kafkaWrite]);
  }
}

The Redis pipeline batches the GEOADD and HSET into a single round-trip. The Kafka write is durable and feeds the Postgres writer asynchronously. The ingestion service’s p99 latency stays under 10ms because neither operation involves a blocking database transaction.

---

Tradeoffs Table

Dimension	R-Tree (PostGIS GiST)	Geohash (Redis GEORADIUS)	S2 Cells	H3 Hexagons
Query latency (1M rows)	2-10ms	<1ms	1-5ms	1-5ms
Write throughput	~5K/s per instance	~100K/s per instance	~5K/s (B-tree on cell ID)	~5K/s (B-tree on cell)
Cell shape uniformity	Adaptive MBR	Rectangular, varies by lat	Square (cube projection)	Hexagonal, very uniform
Native DB support	PostGIS, MySQL spatial	Redis built-in	Manual (store cell IDs)	Manual (store cell IDs)
Radius accuracy	Exact (geography type)	Approximate (haversine)	Approximate + DWithin pass	Approximate + DWithin pass
Hierarchical queries	No	Prefix-based (limited)	Yes (cell parent/children)	Yes (7-to-1 decomposition)
Best fit	Complex polygons, joins	Real-time driver dispatch	Global coverage, analytics	Density analysis, routing

---

Production Considerations

Driver TTL and stale data. A driver who closes the app should not appear in search results. Store a lastSeen timestamp in Redis and run a background job every 30 seconds that removes members from the active set whose lastSeen exceeds your staleness threshold. Do not rely on the client to send an explicit “offline” event: mobile apps terminate without notice.

async function evictStaleDrivers(
  redis: Redis,
  maxAgeMs: number = 30_000
): Promise<number> {
  const cutoff = Date.now() - maxAgeMs;
  const allDrivers = await redis.zrange('drivers:active', 0, -1);

  const pipeline = redis.pipeline();
  let evictCount = 0;

  for (const driverId of allDrivers) {
    const meta = await redis.hgetall(`driver:${driverId}:meta`);
    if (!meta.lastSeen || Number(meta.lastSeen) < cutoff) {
      pipeline.zrem('drivers:active', driverId);
      evictCount++;
    }
  }

  await pipeline.exec();
  return evictCount;
}

Sharding the active set. Redis sorted sets are single-threaded per key. At 100K+ active drivers, a single drivers:active key becomes a hotspot. Shard by H3 resolution-4 cell (122 cells globally): drivers:active:8428342bfffffff. Your query function computes the covering cells at resolution 4 and fans out across the relevant shards. For most city deployments this is 1-4 shards per query.

Coordinate precision. Postgres float8 provides 15-16 significant decimal digits. A latitude stored as a double has sub-millimeter precision. Redis stores geohash at 52-bit precision, which gives roughly 0.6mm accuracy at the equator. Both are more than sufficient. The precision you should actually worry about is the device GPS: consumer-grade GPS has 3-5 meter accuracy under open sky, worse in urban canyons. Do not over-engineer coordinate precision when the input is inherently fuzzy.

Index maintenance under high write load. PostGIS GiST indexes accumulate fragmentation under heavy insert/update load. Schedule a weekly VACUUM ANALYZE during low-traffic windows. Monitor pg_stat_user_indexes for index bloat. If idx_blks_hit / (idx_blks_hit + idx_blks_read) drops below 0.95, you have a cache miss problem that vacuuming or increasing shared_buffers can address.

Hot cell problem. A venue hosting 50,000 people, or a city center at peak commute time, will concentrate enormous point density in a small number of H3 or geohash cells. Queries against those cells will be slow because the candidate set is large even with a tight ST_DWithin filter. Two mitigations: first, add a secondary filter early (status = ‘active’ and vehicle_class = ‘suv’) to reduce the scan; second, maintain a separate index on cell ID plus status to allow index-only scans for the most common query patterns.

Observability. Track these metrics per query type:

• geo_query_candidate_rows: rows returned by the spatial index before ST_DWithin filtering
• geo_query_result_rows: rows returned after filtering
• geo_query_selectivity: result/candidate ratio; alert if below 0.1 (too many false positives from the spatial index)
• redis_georadius_latency_p99: should be under 5ms; spikes indicate key hotspot
• driver_location_age_p95: age of the oldest location in your active set; should be under your staleness TTL

---

Choosing the Right Approach

Start with PostGIS GiST if your write rate is under 1,000 location updates per second and your queries involve complex geometries (polygon containment, routing corridors, service area intersections). The geography type gives you exact distance calculations on the sphere without coordinate projection.

Add Redis GEORADIUS in front of PostGIS when your write rate exceeds 1,000/s or your proximity query latency needs to be under 2ms. Redis handles the hot path; Postgres handles enrichment and persistence.

Switch to H3-indexed Postgres if you also need density analysis, surge pricing zones, or supply/demand imbalance calculations at multiple geographic scales. H3’s hierarchical decomposition makes these multi-resolution aggregations natural.

Use S2 cells when you need very precise coverage of irregular regions (service areas that follow road networks or political boundaries) and already have infrastructure for precomputing cell coverings in your build pipeline.

---

The decision is never purely about the index. It is about the write rate, the query shape, and whether your bottleneck is at the spatial lookup stage or at the enrichment stage. A 10ms PostGIS query with a join to the drivers table may be perfectly adequate for a food delivery app with 200 active couriers per city. The same approach at 50,000 concurrent ride-sharing drivers will not survive a busy Friday night. Match the architecture to the actual scale, measure the actual bottlenecks, and do not add Redis sharding complexity until the Postgres write path is genuinely saturated.