System Design 7: Design Proximity Search | Quad Tree vs Geohash vs PostGIS vs Elasticsearch | HLD

Proximity search is a fundamental building block frequently required when designing larger location-aware systems—such as hotel booking platforms (e.g., Airbnb), food delivery apps (e.g., Zomato, Swiggy), and ride-sharing networks (e.g., Uber, Rapido). Rather than standing alone as an isolated interview question, candidates must know how proximity search algorithms function under the hood to integrate them seamlessly into broader system design architectures.

1. Why Do We Need Proximity Search? (The Core Problem)

• Contextual Discovery: Modern consumer applications require users to find nearby entities (restaurants, drivers, hotels) constrained within a specific radius (e.g., 5 km) from their current geographical coordinates.
• The Scale Challenge: Iterating through millions of global listings and calculating point-to-point distances on the fly using standard mathematical formulas (like the Haversine formula) results in $O(N)$ computational complexity, which completely collapses under high concurrent read loads.
• System Integration: Proximity search algorithms bridge raw spatial coordinates (latitude and longitude) with high-performance indexing strategies to achieve near-real-time filtering.

2. Core Mental Model & Spatial Indexing Strategies

To avoid scanning every record in the database, we partition the earth's surface into structured spatial indexes. The lecture evaluates four primary design patterns used in industry:

1. Quad Tree: A hierarchical tree data structure dividing the world into four quadrants recursively.
2. Geohash: A hierarchical spatial indexing system that encodes latitude and longitude into compact alphanumeric strings using space-filling curves (Z-order curves).
3. PostGIS (PostgreSQL + GIS Extension): A robust relational database solution augmented with spatial indexing and geometric function support.
4. Elasticsearch: A distributed search engine equipped with native, out-of-the-box geo-spatial querying capabilities.

3. Approach 1: The Quad Tree

How It Works

• A Quad Tree is similar to a binary tree, but instead of two children (left/right), each parent node possesses four children corresponding to geographic quadrants (Northwest, Northeast, Southwest, Southeast).
• The algorithm recursively subdivides the global map into four quadrants, then subdivides those sub-quadrants further, continuing until a leaf node contains a manageable number of data points (e.g., a single restaurant or a tightly clustered group of hotels).

Critical Real-World Drawbacks

• Data Uniformity Assumption Fails: Quad Trees assume data points (restaurants, hotels) are uniformly distributed across the globe. In reality, data points cluster heavily in urban centers while oceans, deserts (like Antarctica, Greenland), and uninhabited regions contain zero entries.
• Unbalanced Tree Heights: Densely populated urban zones undergo thousands of recursive subdivisions, creating extremely deep branches. Sparsely populated zones remain shallow. This results in a severely unbalanced tree structure.
• Tedious Neighbor Searching: When a user queries for locations within a 5 km radius, if their current quadrant lacks results, the system must perform complex, time-consuming backtracking—climbing up to parent nodes and scanning neighboring sibling quadrants recursively.
• Maintenance Overhead: Quad Trees are in-memory data structures, not databases. Inserting a new restaurant requires rebuilding or rebalancing sections of the tree. Production systems require maintaining separate read and write replicas in memory, making it extremely difficult to scale and maintain.

Note: During a system design interview, avoid proposing a Quad Tree due to its high implementation complexity and maintenance overhead in production. (An R-Tree is an enhanced alternative, but still rarely built from scratch in modern architectures).

4. Approach 2: Geohash (The Recommended Geospatial Encoding)

How It Works

• Recursive Grid Partitioning: Like the Quad Tree, the world map is divided into four main quadrants, which are further subdivided into smaller grids. Each grid is assigned a numeric integer.
• Base64 / Base32 Encoding: Long numeric integer strings representing deep grid coordinates are encoded into concise alphanumeric strings.
• Precision Levels: The length of the Geohash string dictates its spatial precision. Shorter strings cover wide areas (country/city level), while longer strings pinpoint hyper-local coordinates (street or building level).

Precision Level vs. Radius Mapping

Why Geohash Wins for Proximity Search

• Neighbor Proximity via String Prefix: In a Geohash, locations that are physically close to one another share identical or nearly identical prefix strings.
• Zero Tree Traversal: Unlike Quad Trees, finding neighboring restaurants does not require complex tree backtracking. The system simply evaluates adjacent hash strings by modifying a single character or bit at the end of the string.

Schema & SQL Implementation

To store and query Geohash data in a relational database:

-- Restaurant Table Schema
CREATE TABLE restaurants (
    id VARCHAR(50) PRIMARY KEY,
    name VARCHAR(100),
    latitude DECIMAL(10, 8),
    longitude DECIMAL(11, 8),
    geohash VARCHAR(12)
);

-- Proximity Query Example using Wildcards
SELECT * FROM restaurants 
WHERE geohash LIKE 'tdr12%';

5. Approach 3: PostGIS (PostgreSQL + GIS Extension)

How It Works

• PostgreSQL combined with the GIS extension (PostGIS) provides robust native support for geographic data types and spatial indexing.
• Once the GIS extension is installed, developers can store geometry/geography data types and execute spatial functions directly within SQL.

Data Insertion and Querying

-- Insert a restaurant location using text-to-geometry functions
INSERT INTO restaurants (id, name, location) 
VALUES ('1', 'McDonalds', ST_GeomFromText('POINT(77.5946 12.9716)', 4326));

-- Query restaurants within a 5km radius using PostGIS ST_DWithin function
SELECT id, name 
FROM restaurants 
WHERE ST_DWithin(
    location, 
    ST_GeomFromText('POINT(77.5946 12.9716)', 4326), 
    5000 -- distance in meters
);

6. Approach 4: Elasticsearch (Plug-and-Play Geo-Search)

How It Works

• Elasticsearch is a distributed search engine capable of handling full-text search and geo-spatial queries out of the box without requiring manual extension installations.
• It is highly optimized for fast document retrieval, making it exceptionally powerful when combining spatial filters with keyword searches.

7. Comparative Synthesis of Proximity Search Approaches

To choose the right tool during an interview, evaluate the specific constraints of the problem statement using the matrix below:

8. Decision Framework: Which Approach to Choose in an Interview?

Summary and Key Takeaways

• Proximity search is a crucial architectural component embedded inside broader system design problems like food delivery apps, hotel booking platforms, and ride-sharing networks.
• Avoid Quad Trees in real-world system design interviews due to data non-uniformity, unbalanced tree heights, complex backtracking, and severe in-memory maintenance overhead.
• Geohash encodes latitude and longitude into alphanumeric strings using space-filling curves, allowing rapid neighboring node lookup by evaluating string prefixes.
• PostGIS extends PostgreSQL with powerful spatial functions (ST_DWithin, ST_GeomFromText) making relational proximity queries straightforward.
• Elasticsearch provides out-of-the-box geo-spatial indexing and search capabilities with zero configuration hurdles.
• Dual-Requirement Strategy: For pure coordinate-matching (drivers/riders), choose Geohash. For combined location and fuzzy text search (restaurants/hotels), choose PostGIS (with fuzzy string match and GIS extensions) or Elasticsearch.