← Back to Notes

Geospatial Indexing: The Quadtree

·2 min read

1. The Background: The Proximity Search

In apps like Uber, Yelp, or Tinder, you frequently need to find objects (cars, restaurants, people) near a specific user. Both the user and the objects are represented by Latitude and Longitude coordinates.

2. The Problem: The Math Nightmare (Full Table Scan)

To find out if a restaurant is within 5 miles of a user, the database must calculate the geometric distance between them. If you write a standard SQL query (SELECT * WHERE distance < 5), the database must perform complex math on every single row in the table. In a database of 50 million restaurants, this $O(N)$ full table scan will instantly melt your servers under concurrent user load.

3. The Solution: Spatial Indexing with Quadtrees

We must avoid searching the whole world by grouping nearby locations together using a dynamic grid called a Quadtree.

How it is built:

  1. The Root: The entire world is represented as one massive square bounding box.
  2. The Limit: We enforce a maximum capacity (e.g., no box can hold more than 100 locations).
  3. The Subdivision: If a box reaches 101 locations, it is instantly split down the middle horizontally and vertically, creating 4 equal quadrants (NW, NE, SW, SE).
  4. Recursion: The locations are sorted into their new, smaller boxes. If a smaller box fills up, it splits again.

The Result: Empty oceans or deserts remain as massive, undivided boxes. Crowded cities (where millions of locations are packed tightly) recursively split into a microscopic grid of tiny boxes.

How the Search Works: When a user searches for a ride, the system traverses the tree to find the exact box the user is standing in. It retrieves the objects in that box (and the immediate bordering boxes), and only performs the heavy distance math on those few hundred objects, turning an $O(N)$ nightmare into an incredibly fast $O(\log N)$ lookup.