CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 6 of 8 · 2 min read

Quadtree

A map that splits where it is crowded.

A quadtree divides the map into four quadrants, then divides any quadrant that is still too crowded, and repeats. The rule in the book: split a cell until it holds no more than 100 places. A crowded city ends up with many tiny cells, and a desert with one huge cell. The tree lives in memory on each location server, and it is built when the server starts. It is a data structure, not a database.

Memory. The book's figures: 200 million places, at most 100 per leaf, give about 2 million leaf nodes. A leaf holds the corner coordinates (32 bytes) and up to 100 place ids of 8 bytes each (800 bytes), which is 832 bytes. An internal node holds corners and four child pointers, 64 bytes. There are about one third as many internal nodes as leaves, so about 0.67 million. Memory is 2,000,000 × 832 + 670,000 × 64 bytes, which is about 1.7 GB. That fits on one server. Building takes a few minutes.

Search. Walk from the root to the leaf that holds the user. If it has enough places, return them. If not, add places from its neighbours.

Operations. While the tree builds, the server cannot serve. So roll out new versions a few servers at a time. For updates, the simple way is to rebuild the tree on a few servers at a time, and accept that some servers briefly show stale data. Updating live is possible but needs locks and care.

Geohash Quadtree
Build Easy, no tree Harder, a tree
Radius search Yes Yes
Nearest k places Awkward Natural
Cell size by density Fixed per length Adapts
Update Easy, add or delete a row Harder, tree walk, locks
Where it lives A table in the database Memory of each server

The book also mentions Google S2, which maps the sphere to a line with a space-filling curve and is good for geofencing, but advises geohash or quadtree for an interview, since S2 is hard to explain.

Quadtree

A quadtree is a tree where each node is a map area that splits into four child areas whenever it holds too many items.

Example: a map cell with 150 places splits into four, which hold 40, 30, 50 and 30.

Check yourself: 1. When does a quadtree cell split? 2. Why can the whole tree fit in one server? 3. Which index suits "the 5 nearest gas stations" better?