"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. **See it in practice:** The [Yelp](/learn/system-design/questions/yelp) question is a classic geohash use case -- restaurants are relatively static, so you index them by geohash prefix and combine that with full-text search for name/category filtering. The [Google Map](/learn/system-design/questions/google-map) question extends geohashing to spatial tile rendering, where each map tile corresponds to a geohash cell at a particular zoom level. ## Quadtrees -- Adaptive Density Handling Geohashing uses a uniform grid: every cell at a given prefix length is the same size. That works well when entities are evenly distributed, but the real world is not even. Manhattan might have 50,000 restaurants in a few square kilometers, while rural Wyoming has 3 restaurants spread over hundreds of kilometers. A uniform grid wastes precision in sparse areas and lacks it in dense ones. A quadtree solves this by recursively subdividing space based on density. Start with one cell covering the entire area. If a cell contains more than a threshold number of entities (say, 100), split it into four equal quadrants. Keep splitting until every leaf cell is below the threshold. The result is a tree where dense urban areas have tiny cells and sparse rural areas have enormous ones. To query a quadtree, start at the root and traverse downward. At each node, check which children overlap with the search radius and recurse into them. Branches that do not overlap are pruned entirely, so you only visit cells that might contain relevant results. **When to choose a quadtree over geohashing:** quadtrees shine when entity density varies dramatically across your service area. They also handle dynamic datasets well -- when a new entity is added, you only need to check if its leaf cell exceeds the threshold and split if necessary, rather than rebuilding an entire index. **Cross-reference:** R-trees are the engine behind PostGIS spatial queries. If your application already uses PostgreSQL, adding the PostGIS extension gives you spatial indexing without introducing a new data store. For the tradeoffs of adding specialized infrastructure vs using what you already have, see the [Distributed Caching](/learn/system-design/design-patterns/distributed-caching) pattern -- similar "build vs extend" decisions apply. ## Redis GEO -- Real-Time Location at Scale For applications where locations change constantly -- drivers in a ride-sharing app, delivery couriers, or fleet vehicles -- you need an index that can handle millions of writes per second *and* answer radius queries with sub-second latency. This is where Redis GEO enters the picture. Redis GEO uses geohashing internally but wraps it in a sorted set, giving you O(log n) inserts and efficient range scans. The API is remarkably simple: GEOADD takes a key name, longitude, latitude, and a member name. Under the hood, Redis computes a 52-bit geohash of the coordinates, uses it as the score in a sorted set, and stores the member. Because sorted sets are backed by skip lists, both insertion and lookup are O(log n). GEOSEARCH (which replaces the older GEORADIUS command) finds all members within a given radius of a point. It computes the geohash range corresponding to the search area, does a sorted set range scan to find candidates, then filters by exact Haversine distance. The result is a list of nearby members with their distances, sorted from nearest to farthest. **Why Redis and not just a database?** Two reasons. First, speed: Redis operates entirely in memory, so a GEOSEARCH over millions of entries completes in under a millisecond. A PostGIS query on the same dataset might take 10-50ms -- fine for static data, but too slow when you need to re-query every few seconds as a rider moves. Second, write throughput: Redis can handle hundreds of thousands of GEOADD operations per second on a single node, which matters when millions of drivers are sending location updates every 3-5 seconds. **See it in practice:** The [Uber](/learn/system-design/questions/uber) question is the canonical Redis GEO problem -- you must handle millions of real-time driver location updates and match riders to nearby drivers with sub-second latency. For handling the write throughput side of this problem, see the [Scaling Writes](/learn/system-design/design-patterns/scaling-writes) pattern (sharding, write buffering). For ensuring Redis stays available under failure, see the [Pushing Realtime Updates](/learn/system-design/design-patterns/pushing-realtime-updates) pattern on Redis Sentinel and replication. ## Putting It Together -- The Uber Architecture Let us walk through how all these pieces fit in a real system. A ride-sharing application needs to solve two problems simultaneously: ingest millions of driver location updates per second, and answer rider queries like "who is the nearest available driver?" in real time. **The write path:** Every active driver sends a GPS update every 3-5 seconds. These updates hit a Location Service, which writes them to Redis GEO using GEOADD. With 1 million active drivers, that is roughly 200,000-300,000 writes per second. A single Redis instance can handle this, but for redundancy you would shard by geographic region (each city gets its own Redis instance) and replicate for failover. The Location Service also fans out updates asynchronously to a time-series database for historical tracking, analytics, and ETA calculations. **The read path:** When a rider requests a ride, the Matching Service receives their location and calls GEOSEARCH on the appropriate Redis instance to find all available drivers within a 5 km radius. This returns a ranked list of candidates sorted by distance. The Matching Service then applies business logic -- driver rating, estimated arrival time, current trip status -- to select the best match. **Why not just use a database for everything?** The key architectural decision is separating the "where is everyone right now" index (Redis) from the "where has everyone been" store (time-series DB). Redis handles the hot, constantly-changing spatial data with microsecond latency. The time-series database handles cold, append-only historical data that is queried much less frequently. Trying to do both in a single system creates a conflict between write optimization and query optimization. **Where this pattern appears:** Beyond [Uber](/learn/system-design/questions/uber), proximity-based services show up in the [Yelp](/learn/system-design/questions/yelp) question (static business locations with radius search), the [Google Map](/learn/system-design/questions/google-map) question (spatial tile rendering and route proximity), and any system that needs geographic filtering. The pattern also connects to [Scaling Reads](/learn/system-design/design-patterns/scaling-reads) (caching frequent proximity queries), [Stream Processing and Realtime Aggregation](/learn/system-design/design-patterns/stream-processing-realtime-aggregation) (processing location update streams), and [Fan-Out and Feed Generation](/learn/system-design/design-patterns/fan-out-feed-generation) (broadcasting driver updates to watching riders). ## Technology Decision Guide Choosing the right geospatial tool depends on your data characteristics and query patterns: The most common architecture combines two tools: Redis GEO for real-time queries (where are things *right now*) and PostGIS or Elasticsearch for historical or complex queries (find all restaurants within this polygon that are open past 10 PM). Do not try to solve both problems with one tool -- the write patterns and query patterns are too different.