What is a Quadtree and How Does It Work?

A quadtree is a hierarchical data structure that recursively partitions two dimensional space into four child regions: northwest (NW), northeast (NE), southwest (SW), and southeast (SE). Each internal node represents a spatial region, and leaves hold bounded buckets of actual points. The key insight is localizing work: instead of scanning all 100 million points to find restaurants within 2 km, you only examine points in a few cells covering that area.

Two main variants exist in production. Point region (PR) quadtrees split space into equal quadrants regardless of where points actually lie, making splits deterministic and fast. Point quadtrees split based on actual point distribution (like median splits), which creates more balanced trees under skew but costs more computation during writes. Both maintain a branching factor of 4, so tree height grows as log base 4 of the number of leaf buckets.

The classic query pattern is coarse cover then refine. For a 2 km radius search, you first compute which quadtree cells overlap that circle (maybe 3 to 10 cells depending on level). Fetch all candidate points from those cells using simple cell ID range scans. Finally, refine by computing exact great circle distances to eliminate false positives. This two stage approach keeps latency low because most points are pruned by the spatial hierarchy before any expensive distance calculations.

Capacity planning follows straightforward math. With 100 million points and leaf capacity of 128 points per leaf, you need roughly 781,000 leaves and about 260,000 internal nodes. Tree height reaches approximately 10 levels. Even with metadata, the index structure fits in a few hundred megabytes of memory, though the actual point attributes often dominate total memory usage.

💡 Key Takeaways

•Quadtrees partition 2D space into 4 equal regions recursively, with internal nodes representing regions and leaves holding bounded point buckets

•Tree height grows as log base 4 of leaf count; 100M points with capacity 128 yields height 10, roughly 781k leaves, and 260k internal nodes

•Query pattern is coarse cover then refine: cover search area with minimal cells, fetch candidates via cell ID range scans, then compute exact distances

•PR quadtrees split space equally for fast deterministic writes; point quadtrees split by data distribution for better balance under skew but higher write cost

•Index structure for 100M to 1B points fits in hundreds of MB with compact metadata; point attributes typically dominate total memory footprint

📌 Examples

Google S2 partitions the sphere into 6 faces, each subdivided by factor of 4 per level. At level 12, roughly 100 million cells averaging 5.1 km² each; a 2 km radius query covers approximately 3 to 10 mixed level cells.

Bing Maps uses a canonical PR quadtree over Web Mercator projection. At zoom 15, there are 32,768 × 32,768 tiles (1.07 billion total), enabling hierarchical tile retrieval and CDN caching at global scale.

← Back to Quadtree & Spatial Indexing Overview