# Proximity Search: Geohash vs Quadtree vs S2 "Find restaurants within 2 km" or "match a rider with nearby drivers" needs a spatial index. A plain index on latitude and longitude cannot answer a 2D range query efficiently. Three common answers: ## Geohash Encode a location as a string by repeatedly halving longitude and latitude ranges. Nearby points usually share a prefix, so a normal B-tree or key-value store can find candidates by prefix. Precision 6 gives cells roughly 1.2 km x 0.6 km. Gotcha: two points on either side of a cell boundary can have totally different prefixes, so always query the target cell plus its 8 neighbours, then filter by exact distance. ## Quadtree Recursively split a region into four quadrants until each leaf holds at most N points. Dense cities get deep, small cells; empty oceans stay as one big cell. It adapts to uneven density well, which makes it a natural fit for business listings. Usually kept in memory and rebuilt or updated periodically. ## S2 and H3 Google S2 projects the sphere onto a cube and orders cells along a Hilbert curve, giving cell ids with good locality and accurate coverage of arbitrary regions. Uber H3 uses hexagons, where every neighbour is the same distance away, which is handy for surge pricing and demand heat maps. ## Static vs moving objects - Restaurants rarely move: precompute the index, cache heavily, read-optimized. - Drivers update every few seconds: keep current locations in an in-memory store keyed by cell (for example Redis geo commands), update the cell on each ping, and expire stale entries. ## Interview tip State your cell size and why, mention the neighbour-cell query for boundary cases, and separate the static-places index from the moving-objects index. Those three points cover most follow-up questions. Shared by the Linkjob AI team - Linkjob AI is a real-time AI interview assistant: https://www.linkjob.ai/