시스템 설계 - 24. 지리적 인덱싱: 우버가 수백만 운전자 중 가장 가까운 사람을 밀리초 안에 찾는다

출처: Dev.to

지리공간 인덱싱: 우버가 수백만 명의 운전자 중 가장 가까운 운전자를 밀리초 안에 찾는 방법

시리즈: 시스템 설계 마스터리 — 15일 중 8일차

읽는 시간: 11분

주제: 쿼드트리, 게오하시, 구글 S2, 우버 H3, 실시간 인덱스 업데이트

---

The Query That SQL Was Never Built For

You open Uber. The app needs to answer: “Which drivers are within 2km of this exact latitude/longitude, right now, out of the millions of drivers active worldwide?”

A naive SQL approach:

SELECT driver_id, latitude, longitude
FROM drivers
WHERE 
  SQRT(POW(latitude  - :user_lat, 2) + POW(longitude  - :user_lng, 2)) < 0.02

Enter fullscreen mode
Exit fullscreen mode

This computes the distance for every single row in the table — every active driver on Earth — for every search. At Uber’s scale (millions of drivers, location updates every 3-5 seconds), this is computationally impossible to run in real time.

The fundamental problem: standard database indexes (B+ trees, hash indexes) are designed for 1-dimensional data — sort by a single value (a timestamp, an ID, a name). Latitude and longitude are 2-dimensional. A B+ tree index on latitude alone, or longitude alone, doesn’t help you efficiently find “nearby” points — nearby in 2D space doesn’t mean nearby in either dimension individually.

Geospatial indexing solves this by transforming 2D space into something that CAN be indexed efficiently in 1D — and there are three major approaches.

---

Approach 1: Quadtrees — Recursive Spatial Division

A Quadtree recursively divides 2D space into four equal quadrants, continuing to subdivide quadrants that contain “too much” data.

Start: entire map (1 region)

┌─────────────┬─────────────┐
│             │             │
│   NW        │    NE       │
│             │             │
├─────────────┼─────────────┤
│             │             │
│   SW        │    SE       │
│             │             │
└─────────────┴─────────────┘

If NE quadrant has too many points (e.g., dense city center), subdivide it further:

┌─────────────┬──────┬──────┐
│             │ NE-NW│ NE-NE│
│   NW        ├──────┼──────┤
│             │ NE-SW│ NE-SE│
├─────────────┼──────┴──────┤
│             │             │
│   SW        │    SE       │
│             │             │
└─────────────┴─────────────┘

This creates a tree structure where densely populated areas (city centers, with thousands of drivers per square km) have many small leaf nodes, while sparsely populated areas (rural regions, with few drivers per 100 square km) have few large leaf nodes.

Finding nearby drivers:

1. Locate the leaf node(s) containing the user's location
2. Drivers in that leaf node are candidates
3. If not enough candidates, check neighboring leaf nodes
   (a leaf representing a small area in a dense city center might need to check 1-2 neighbors; a leaf representing a large rural area might already have all nearby drivers)

Enter fullscreen mode
Exit fullscreen mode

Advantages:

• Naturally adapts to data density — dense areas get fine-grained subdivision automatically

• Conceptually simple — a tree structure most engineers already understand

Disadvantages:

• Tree traversal for neighbor lookups can be complex — finding “all leaves adjacent to this leaf” isn’t trivial when leaves are different sizes

• Rebalancing as data shifts (rush hour moves driver density from residential areas to business districts) requires tree restructuring

Used by: Many GIS (Geographic Information Systems) applications, MongoDB’s older geospatial indexes (2dsphere indexes use a similar recursive subdivision).

---

Approach 2: Geohash — Encoding Location as a String

Geohash takes a completely different approach: encode a latitude/longitude pair into a single string, where the key property is — the longer the shared prefix between two geohashes, the closer the locations are.

How Geohash Encoding Works

Latitude/Longitude: (37.7749, -122.4194) ← San Francisco
The encoding interleaves bits from latitude and longitude ranges, recursively halving the search space:

Step 1: Is longitude in [-180, 0] or [0, 180]?
-122.4194 is in [-180, 0] → bit = 0

Step 2: Is latitude in [-90, 0] or [0, 90]?
37.7749 is in [0, 90] → bit = 1

Step 3: Continue alternating longitude/latitude, halving each time…

After enough bits, group into base32 characters:
Result: “9q8yyk8ytpxr” ← this is the Geohash for San Francisco

Enter fullscreen mode
Exit fullscreen mode

The Prefix Property

"9q8yyk8ytpxr" → San Francisco (precise location)  
"9q8yyk8ytpx"  → San Francisco (slightly larger area, ~1m precision)  
"9q8yyk8yt"    → San Francisco area (~150m precision)  
"9q8yyk"       → San Francisco region (~5km precision)  
"9q8y"         → Bay Area (~80km precision)  
"9q"           → California / Nevada region (~1700km precision)

Each character you remove from the end roughly multiplies the represented area by 32 (since base32 has 32 possible characters per position).

Finding Nearby Points with Geohash

-- Find all locations with geohash starting with "9q8yyk" 
-- (same ~5km grid cell as our target location)
SELECT * FROM drivers WHERE geohash LIKE '9q8yyk%'

This is a prefix match — something B+ tree indexes handle extremely efficiently! You’ve converted a 2D “nearby” query into a 1D “string prefix” query that any standard database index can answer fast.

The Edge Case: Boundary Problem

Two points that are physically VERY close to each other can have COMPLETELY DIFFERENT geohash prefixes if they’re on opposite sides of a grid cell boundary:

Point A: geohash “9q8yyk…” (just inside one grid cell)
Point B: geohash “9q8yym…” (just across the boundary, physically 10 meters from Point A)

A prefix search for “9q8yyk%” would MISS Point B entirely, even though it’s very close.

The fix: When searching, also check the 8 neighboring grid cells (the cells surrounding the cell containing the query point) — not just the cell containing the point itself. Most Geohash implementations include a “neighbors” function for exactly this purpose.

---

Approach 3: Google S2 and Uber H3 — Cell-Based Indexing at Scale

Geohash has a subtle issue: its grid cells are rectangular, and rectangles on a sphere (the Earth) have wildly varying actual sizes depending on latitude — a “1-degree by 1-degree” cell near the equator covers a much larger physical area than the same cell near the poles. This distortion complicates distance calculations.

Google S2: Projecting the Sphere onto a Cube

S2 projects the Earth’s surface onto the 6 faces of a cube, then recursively subdivides each face into a hierarchy of cells — similar in spirit to a Quadtree, but designed specifically to minimize the distortion of spherical geometry.

Earth (sphere) → projected onto cube faces → each face recursively subdivided into a hierarchy of cells (S2 cells)

Each S2 cell has a unique 64-bit ID. Cells at the same “level” have roughly similar areas, regardless of where on Earth they are — solving the rectangular-distortion problem of simple lat/lng grids.

Used by: Google Maps internally for spatial indexing and proximity queries at global scale.

Uber H3: Hexagonal Grid System

Uber open-sourced H3, which divides the Earth into a hierarchical grid of