Quad Trees

If you've ever played an open-world game and noticed that trees far away look like green blobs, but trees up close have individual leaves, you've experienced the magic of spatial partitioning. In the world of system design, when we need to manage 2D space dynamically, we use a Quad Tree.

The Problem with Grids

We talked about Geohashes dividing the world into a fixed grid. But think about the real world: Downtown Manhattan is packed with millions of people, businesses, and cars. Meanwhile, the middle of the Sahara Desert is mostly empty sand.

If we use a fixed grid, we waste a ton of memory storing empty squares in the desert, while our squares in Manhattan are so overloaded they become slow to search.

We need a grid that adapts. We need a grid that splits into smaller pieces only when it gets too crowded.

Enter the Quad Tree

Imagine a piece of paper representing a map. You have a rule: No section of the map can contain more than 100 points of interest (restaurants, cars, etc.).

1. You start with the whole map (one big square). You drop your data in.
2. Oh no, there are 5,000 restaurants! That's more than 100.
3. So, you draw a cross in the middle, dividing the map into four equal quadrants (hence the name Quad Tree).
4. You look at the top-left quadrant. It only has 50 restaurants. Great, leave it alone.
5. You look at the bottom-right quadrant (let's say it's Manhattan). It has 3,000 restaurants. Still too many!
6. You divide that quadrant into four smaller quadrants.
7. You keep repeating this process recursively.

The result? Dense areas like cities look like a finely woven mesh of tiny squares, while oceans and deserts remain massive, undivided blocks.

How It Works in System Design

A Quad Tree is a tree data structure where every internal node has exactly four children (Northwest, Northeast, Southwest, Southeast).

When an app like Yelp needs to find restaurants near you:

1. It starts at the root of the tree (the whole world).
2. It asks, "Is the user's search radius intersecting this square?" Yes.
3. It moves down to the four children and asks the same question.
4. It quickly ignores massive chunks of the world that aren't relevant (like the Pacific Ocean).
5. It drills down until it finds the specific leaf nodes containing the restaurants you care about.

Because the tree is balanced based on density, search times remain consistently fast (O(log N)), whether you are in Times Square or rural Montana.

Real-World Examples

• Google Maps: Uses variations of Quad Trees to decide what map tiles and labels to load at different zoom levels.
• Uber: Before switching to H3 (a hexagonal system), early iterations of spatial indexing heavily relied on Quad Tree concepts to manage dense urban clusters of drivers.
• Collision Detection in Gaming: Engines like Unity or Unreal use Quad Trees (or 3D Octrees) so they don't have to check if every bullet hits every wall. They only check objects in the same small quadrant.

Summary

A Quad Tree is a dynamic, tree-based data structure used to partition 2D space. Unlike fixed grids, Quad Trees subdivide space only where data is dense. This ensures that memory is used efficiently and searches remain fast, making it the perfect tool for maps, location-based services, and geospatial queries where data distribution is highly uneven.