Google Maps & Uber: Geohashing, S2 Geometry, & Quad-Trees

Traditional databases index 1D numbers using B-Trees or LSM-Trees. However, geographical coordinates are 2D floating-point pairs ((Latitude, Longitude)) lying on a spherical Earth (ellipsoid).

Executing a proximity search (e.g., "Find all available taxis within a 2-kilometer radius of my GPS point") using raw SQL:

sql
Copy
SELECT * FROM drivers WHERE 
  (6371 * acos(cos(radians(user_lat)) * cos(radians(driver_lat)) * 
  cos(radians(driver_lng) - radians(user_lng)) + 
  sin(radians(user_lat)) * sin(radians(driver_lat)))) < 2.0;

This query forces a full table scan (O(N)) calculating trigonometric functions for every active driver on Earth. At millions of concurrent drivers, database CPU utilization hits 100\% immediately.

To solve this, geospatial engineers compare three foundational spatial indexing strategies:

1. Geohashing (Base32 Grid Strings)
2. Quad-Trees (2D Spatial Trees)
3. Google S2 Geometry (Hilbert Space-Filling Curves)