Geospatial Index

Index geographic coordinates using space-partitioning data structures (R-tree, GeoHash, S2, PostGIS GiST) to enable efficient nearest-neighbor and radius queries : finding all records within N kilometers of a point without scanning every record.

Distance-based queries on latitude/longitude columns without a spatial index degrade to full table scans. At scale (millions of records), this produces query latencies of seconds to minutes, making real-time location features (nearby drivers, restaurant search, store locator) operationally impossible.

Geospatial queries: "find all drivers within 2km of this passenger" or "find all restaurants within 5km of this point": are inefficient without a spatial index. A naive approach scans every record and computes the Haversine distance, producing O(n) performance. At millions of records, this takes seconds.

Spatial indexes partition the geographic space into regions, allowing the query to skip large portions of the dataset:

R-tree (PostgreSQL PostGIS GiST index): stores bounding boxes in a tree structure. Each leaf node contains the bounding box of actual geometric objects. Queries prune branches whose bounding boxes don't intersect the search area. O(log n) average case for radius queries. Standard for PostGIS; used by MySQL spatial indexes.

GeoHash: encodes latitude/longitude as a string where longer prefixes denote finer geographic cells. Nearby points share a common prefix. Enables range scan on an indexed GeoHash column: WHERE geohash LIKE 'u4pru%'. Simple to implement in any database with string B-tree indexes but has cell boundary artifacts (nearby points on different cell boundaries don't share a prefix).

S2 cells (Google's S2 library, used by Uber, Google Maps): projects the sphere onto a cube, then recursively subdivides each face. Cells at each level form a covering for any region. Used in DynamoDB-based geospatial systems (partition by S2 cell at an appropriate level) and H3 (Uber's hexagonal hierarchical spatial index).

H3 (Uber): hexagonal grid system where each hexagon has a unique 64-bit index at 15 resolution levels. Efficient for radius queries, aggregation by geographic region, and neighborhood traversal. Available as a library for Python, JavaScript, Go.

For ride-sharing and delivery platforms (Uber, Lyft, DoorDash, Grab), driver location updates arrive thousands of times per second and must be queryable by radius in under 10ms. Redis with the GEOADD / GEOSEARCH commands provides in-memory spatial indexing backed by a sorted set of GeoHash-encoded scores.

PostgreSQL PostGIS: add and populate a geometry column, index it with GiST, then query with ST_DWithin:

SELECT AddGeometryColumn('locations', 'geom', 4326, 'POINT', 2);

UPDATE locations SET geom = ST_SetSRID(ST_MakePoint(longitude, latitude), 4326);

CREATE INDEX locations_geom_idx ON locations USING GIST(geom);

SELECT * FROM locations WHERE ST_DWithin(

geom::geography, ST_MakePoint(-122.4, 37.7)::geography, 1000);

Redis GEOSEARCH: GEOADD drivers:locations 37.7749 -122.4194 "driver:42", then GEOSEARCH drivers:locations FROMLONLAT -122.4194 37.7749 BYRADIUS 2 km ASC COUNT 10.

H3 for Uber-style location indexing computes a cell index and stores it as a shard key or Redis key prefix: h3.latlng_to_cell(lat, lng, resolution=9) yields roughly 174m hexagons at resolution 9.