Proximity Search & Geospatial Indexes Explained
🧠 Want more system design content? Head over to https://www.hellointerview.com/youtub...
Join me as we walk through the history and applications of geospatial indexes and efficient proximity search.
We start with the core problem. 1D sort order doesn't preserve 2D closeness, so two cabs a block apart on the street can be a million rows apart in your index. From there we walk the full history. Quadtrees and k-d trees from the 1970s, why their pointer-heavy structure dies on disk, and the BKD-tree wrapper that keeps k-d trees alive inside Elasticsearch today. Then R-trees, Guttman's minimum bounding rectangle idea, and why PostGIS, SQLite, and Oracle Spatial all run R-tree variants.
The second half flips to the other camp, flattening latitude and longitude into a single sortable key so a plain B-tree just works. We cover geohash and the bits-vs-string trick, the boundary problem and the 3x3 fix, Google S2 and equal-area cells on a sphere, and Uber H3 with its hexagons and six equidistant neighbors.
Every production spatial index is either a custom tree tuned to behave like a B-tree, or an encoded key dropped into a B-tree you already have. If you need shapes and exact geometry like whether a highway intersects a county, reach for a custom tree like an R-tree. If you have points at scale with heavy writes like millions of driver pings per second, reach for an encoded key like geohash, S2, or H3, then post-filter by exact distance.
Connect with me on LinkedIn! / evan-king-40072280
Learn more at https://www.hellointerview.com/learn/...
Related videos:
DB Indexing in System Design Interviews - B-tree, Geospatial, Inverted Index, and more! • DB Indexing in System Design Interviews - ...