Proximity-Based Services

"Find all restaurants within 5 km." "Show me the nearest available driver." These questions sound simple, but they are fundamentally different from anything a traditional database index can handle well. A B-tree index is built for one-dimensional range queries -- it can efficiently find all users with IDs between 1000 and 2000. But latitude and longitude are two independent dimensions, and a query like WHERE lat BETWEEN x1 AND x2 AND lng BETWEEN y1 AND y2 forces the database to scan one index, then cross-check against the other. For a table with millions of rows, that is painfully slow.

The core insight behind every proximity solution is the same: reduce a 2D problem to a 1D lookup. Whether you use geohashing, quadtrees, or R-trees, the goal is to partition the world into cells so that "find things near me" becomes "find things in my cell and neighboring cells" -- a much smaller search space.

Why Naive Distance Checks Fail#

The brute-force approach is straightforward: for every entity in the database, calculate the Haversine distance to the query point and return anything within the radius. The math works, but the performance does not. If you have 10 million restaurants in your database, every single query computes 10 million distance calculations. That is O(n) per query, and it does not scale.

A spatial index flips the problem. Instead of checking every point, you first determine which grid cells overlap with your search radius, then only examine the points inside those cells. If each cell contains roughly 100 entities and your query touches 4 cells, you go from scanning 10 million rows to checking 400. That is the difference between a query that takes seconds and one that takes milliseconds.

Geohashing -- Turning Coordinates Into Strings#

Geohashing is the most widely used spatial indexing technique, and for good reason: it maps a two-dimensional coordinate to a one-dimensional string that you can store in any ordinary database index.

The algorithm works by recursively bisecting the world. At each step, it divides the current rectangle in half along one axis (alternating between longitude and latitude), assigning a 0 or 1 bit depending on which half the point falls into. After enough bisections, you encode the resulting bit string into a base-32 character sequence. The result is a string like 9q8yyk where each additional character narrows the cell.

The key property is prefix sharing: two locations that are close together will share a long common prefix. A coffee shop at 9q8yyk and another at 9q8yym are in the same neighborhood because they share the 9q8yy prefix. To find all entities near a point, compute the geohash of your query location, then search for all entries whose geohash starts with the same prefix.

The edge-cell problem. There is one gotcha: two locations can be very close physically but fall into different geohash cells if they sit on opposite sides of a cell boundary. The fix is simple -- when querying, always check the target cell and all 8 neighboring cells. This ensures you never miss a nearby entity just because it landed in the adjacent cell.