Geospatial & Location Services • Quadtree & Spatial IndexingMedium⏱️ ~3 min
Quadtree vs Alternatives: R-tree, Geohash, and Hexagonal Grids
Choosing between quadtrees, R-trees, space filling curves, and hexagonal grids depends on your data shape, access patterns, and infrastructure. Quadtrees partition space uniformly and excel with point data, fast prefix based range scans, and simple sharding by cell prefix. R-trees (and R* variants) index minimum bounding rectangles (MBRs) of objects and handle arbitrary polygons and varying object extents better. R-trees can outperform quadtrees for mixed geometries like building footprints or delivery zones because they minimize overlap in skewed distributions through smart rectangle packing and reinsertion heuristics.
Space filling curves like geohash, Z-order, and Hilbert curves linearize two dimensional space into one dimensional keys while preserving locality. This fits systems optimized for range scans and log structured merge (LSM) trees common in distributed databases. Geohash is simpler to implement but suffers from edge artifacts where nearby points get distant keys at cell boundaries. Hilbert and Z-curves offer better locality. Quadtrees provide explicit hierarchical cells more intuitive for region covering; Google S2 combines quadtree hierarchy with curve ordering to get both benefits: hierarchical covering for queries and curve based keys for storage locality.
Hexagonal grids like Uber's H3 offer better neighbor uniformity and lower sampling bias, important for geospatial aggregations and uniform radius expansions. Each H3 hexagon has six equidistant neighbors, while quadtree squares have four edge neighbors and four corner neighbors at different distances. For analytics workloads computing density heatmaps or expanding search rings uniformly, hexagons reduce edge effects. However, quadtrees have simpler bit based addressing and integrate better with existing tile and quadkey ecosystems used in mapping.
Write versus read optimization matters. Point quadtrees with median splits reduce tree depth under skew but cost more on writes due to split computation and potential rebalancing. PR quadtrees have cheap deterministic splits but can deepen under hotspots; mitigate by capping maximum depth and tuning leaf capacity. For heavy write workloads with moving objects updating positions frequently, prefer bounded depth PR quadtrees or hybrid approaches with coarse quadtree cells plus secondary structures inside leaves.
💡 Key Takeaways
•Quadtrees excel at point data, prefix based range scans, and simple sharding; R-trees better for arbitrary polygons and mixed geometry with varying extents
•Space filling curves (geohash, Z-order, Hilbert) linearize 2D space into 1D keys for LSM tree storage; geohash simpler but has edge artifacts, Hilbert offers better locality
•Hexagonal grids like H3 provide uniform six neighbor connectivity and lower sampling bias for aggregations; quadtrees have simpler addressing and better tile ecosystem integration
•PR quadtrees have deterministic cheap splits but deepen under hotspots; point quadtrees balance better under skew but cost more on writes with median split computation
•Choose quadtree/S2 for general geosearch and tile integration, R-tree for polygon heavy workloads, H3 for analytics and uniform expansions, curves for LSM based distributed systems
📌 Examples
Google Maps uses S2 for geosearch, combining quadtree hierarchy on sphere faces with curve ordering for storage. Level 12 cells average 5.1 km², level 15 average 0.079 km² (79,000 m²).
Uber uses H3 hexagonal grid for dispatch and aggregation instead of quadtree because uniform neighbor properties reduce bias in radius expansions and density calculations for matching.