Carve the Map or Flatten It: Spatial Indexes

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 56m

On a rainy Friday in Jakarta, new engineer Daniel Okafor discovers that indexing latitude and longitude separately makes every rider lookup take a second. In part thirteen of The Deep End's Data Structures series, dispatch lead Rina Hartono shows him the two great strategies for searching space: carve it into trees, or flatten it onto a clever line. We build a k-d tree by ear, meet Guttman's R-tree, interleave bits into geohashes, put the Earth in a cube with Google's S2, and find out why Uber chose hexagons and hid twelve pentagons in the ocean. Rina and Daniel are fictional; the structures…