Quadtree vs fixed grid: an interactive nearest-places search

A quadtree indexes points on a map by splitting the map into four squares, and splitting again any square that holds too many points. Cells end up small where places are dense and large where they are sparse, so a “nearest places” search reads about the same small amount of data downtown and in the countryside. A fixed grid, or a single geohash precision, cannot do that: one cell size has to suit both.

The playground indexes 500 places twice, as a quadtree and as a fixed grid, and finds the 10 nearest to wherever you click. Compare the cells each opens and the places each has to check.

One cell size cannot fit a whole city

Downtown, the 8 by 8 grid’s cells hold up to 90 places each, so finding the 10 nearest means opening 9 cells and checking 299 places. The quadtree, splitting any cell with more than 8, opens 8 small cells and checks 30. In the suburbs the problem flips: a finer 16 by 16 grid, which would help downtown, leaves 136 of its 256 cells empty, and a suburban search opens 56 of them, ring after ring, to find 10 places. The quadtree opens 4 large cells and checks 20.

The search itself is best-first: open the cell closest to the query, then the next closest, and stop once no unopened cell could hold anything nearer than the tenth place found so far. Each step down the tree halves the cell, so a city of millions of places is only around 20 levels deep.

Quadtrees, geohashes, H3 and R-trees

• Geohashes are a fixed grid with a string key per cell, easy to store in any database and to shard by prefix. Pick a precision per query, and read a cell and its 8 neighbours.
• Quadtrees adapt to density, which suits uneven data such as businesses in a city. They usually live in memory, rebuilt or updated as places change, while the places themselves stay in a database.
• H3, Uber’s hexagonal grid, gives every cell neighbours at the same distance, which suits ride matching and surge pricing by area.
• R-trees group nearby shapes into overlapping boxes; PostGIS indexes geometry with one, and Lucene-based engines use a related BKD tree for points.

A quadtree in code

class QuadTree:
    def __init__(self, x, y, size, capacity=8):
        self.x, self.y, self.size, self.capacity = x, y, size, capacity
        self.points, self.children = [], None

    def insert(self, p):
        if self.children:
            return self._child(p).insert(p)
        self.points.append(p)
        if len(self.points) > self.capacity and self.size > 1e-6:   # too crowded: split
            h = self.size / 2
            self.children = [QuadTree(self.x + dx, self.y + dy, h, self.capacity)
                             for dx in (0, h) for dy in (0, h)]
            for q in self.points:
                self._child(q).insert(q)
            self.points = []

    def _child(self, p):
        h = self.size / 2
        return self.children[(p[0] >= self.x + h) * 2 + (p[1] >= self.y + h)]

In a system design interview

For “find nearby restaurants”, say why the index adapts: “Businesses are very uneven, so the search service keeps a quadtree in memory, splitting cells above about 100 businesses. It holds ids and coordinates for 200 million places in a few gigabytes, so each server has a full copy, rebuilt nightly and patched as businesses change. A query walks to the nearest cells and fetches details for the top results from the database.” Expect the follow-ups: how the tree is updated without downtime, how moving objects such as drivers differ, and how results are ranked by more than distance.

Read the guide to geohash vs quadtree vs H3 or geospatial search and proximity, or watch a strong candidate design Yelp.

Questions people ask