Posted in Cloud & Infrastructure, Engineering

Quadtrees and R-Trees Explained: Spatial Indexing for Maps, Games, and GIS

Ask “which of these ten thousand points are within 500 meters of me” and a database with no spatial structure has only one option: check every single point. That’s a linear scan, and it falls apart fast as data grows. Spatial indexing exists to avoid that — and the two structures that dominate real-world systems, from PostGIS to game engines to mapping platforms, are the quadtree and the R-tree. They solve the same underlying problem — fast 2D range and nearest-neighbor queries — with different tree shapes and different trade-offs. This is not about pathfinding or shortest-path graph traversal (covered elsewhere); it’s about finding which objects exist in a region of space quickly.

At a Glance

StructureSplits Space ByBest ForCommon Real-World Use
QuadtreeFixed quadrants (recursive 2×2 subdivision)Uniformly distributed points, game-world collision broad-phaseGame engine collision culling, image/terrain tiling
R-treeMinimum bounding rectangles grouping nearby objectsIrregularly shaped/sized geometries, clustered real-world dataPostGIS spatial queries, GIS platforms, mapping systems

Short Verdict

Both structures beat a linear scan by orders of magnitude for range and nearest-neighbor queries, but they’re tuned for different data. A quadtree is simpler to implement and works well when data is reasonably uniform in density, which is why it shows up constantly in game physics engines for broad-phase collision detection. An R-tree handles real-world geometries — polygons, lines, clustered points of wildly different sizes — more gracefully, which is why it’s the structure PostGIS and most production GIS systems actually use under the hood.

Why Linear Scans Fail at Scale

A naive “find all points in this box” query without an index has to examine every row and test whether it falls inside the box — O(n) work per query, where n is the total number of objects. The PostGIS project’s own introductory workshop materials describe this concretely: in a join between two 10,000-record tables, an unindexed query can require up to 100 million comparisons, versus as few as 20,000 with a spatial index — a difference of roughly four orders of magnitude. A real-world census-block lookup in the same material dropped from around 300ms unindexed to around 50ms indexed, and that gap widens as the table grows. Spatial indexes solve this by pre-organizing objects so a query only has to inspect a small, relevant subset of the tree.

Quadtrees: Recursive Quadrant Splitting

A quadtree recursively divides 2D space into four equal quadrants. Each node represents a rectangular region; when a node holds more objects than some threshold, it splits into four child quadrants (northwest, northeast, southwest, southeast), and objects are reassigned to whichever child region they fall into. A range query walks the tree starting from the root, descending only into quadrants whose bounding region actually intersects the query area, and skipping entire subtrees that don’t.

This is exactly the pattern used for broad-phase collision detection in 2D game engines: rather than testing every pair of game objects for collision (an O(n²) problem), the engine inserts objects into a quadtree each frame and only tests pairs of objects that land in the same or neighboring quadrant. The structure’s weakness is uneven density — if most objects cluster in one quadrant, that branch keeps splitting deeply while the rest of the tree stays shallow, producing an unbalanced tree that no longer gives even performance across the space.

R-Trees: Grouping by Bounding Rectangle

The R-tree was introduced by Antonin Guttman in the paper “R-Trees: A Dynamic Index Structure for Spatial Searching,” published as a UC Berkeley technical report and at ACM SIGMOD 1984. Rather than subdividing fixed regions of space, an R-tree groups nearby objects together and wraps each group in a minimum bounding rectangle (MBR) — the smallest rectangle that fully contains everything in that group. Those rectangles are themselves grouped into larger bounding rectangles at the next level up, forming a balanced tree where every leaf holds actual data and every internal node holds the MBR of its children.

A range query descends the tree checking only which child MBRs overlap the query region, pruning branches whose bounding rectangle doesn’t intersect it at all. Because grouping is based on actual object proximity rather than a fixed grid, R-trees adapt naturally to irregular, clustered, or variably sized geometries — which is exactly the kind of data real maps and GIS datasets contain: a country border, a road network, and a point-of-interest dataset all have wildly different shapes and densities. This is why PostGIS implements its spatial indexes on top of PostgreSQL’s GiST (Generalized Search Tree) index type using an R-tree structure, and why most commercial GIS platforms (including Oracle Spatial, per PostGIS’s own documentation) use the same underlying approach.

How PostGIS Actually Uses This

PostGIS doesn’t index full geometries directly — it indexes each feature’s bounding box, then runs queries in two passes. The index pass quickly finds candidates whose bounding boxes intersect the query box (an approximate, fast filter); a second, exact pass then runs the real geometric test — such as ST_Intersects or ST_DWithin — only on that smaller candidate set. A minimal example of creating that index:

CREATE INDEX idx_places_geom
  ON places
  USING GIST (geom);

-- Uses the index automatically via the bounding-box filter,
-- then applies the exact distance test:
SELECT name FROM places
WHERE ST_DWithin(geom, ST_MakePoint(-122.42, 37.77)::geography, 500);

Functions like ST_Intersects, ST_Contains, and ST_DWithin use the index automatically. For operations the planner can’t optimize this way, PostGIS documentation recommends adding an explicit bounding-box filter (the && operator) alongside the exact test. It’s also worth noting the planner will skip the index entirely when a query is expected to return most of the table — at that point, a sequential scan is genuinely faster than tree traversal.

Quadtree vs R-Tree: Direct Comparison

DimensionQuadtreeR-Tree
Partitioning logicFixed recursive quadrant splitsBounding rectangles grouped by proximity
Balance guaranteeNot guaranteed — depends on data distributionHeight-balanced by construction/split algorithm
Handles irregular/variable-size geometriesPoorly — assumes point-like, evenly distributed dataWell — designed explicitly for rectangles of varying size
Implementation complexityLowHigher (node-splitting heuristics on insert)
Typical homeGame engines, in-memory spatial structuresDatabase engines (PostGIS/GiST), GIS platforms

Pros and Cons

  • Quadtree pros: simple to implement and reason about; cheap to build and rebuild each frame, which suits real-time games.
  • Quadtree cons: degrades with clustered/uneven data; not the structure most production databases use for persistent spatial indexes.
  • R-tree pros: handles real-world irregular geometry well; the structure actual spatial databases (PostGIS/GiST) are built on.
  • R-tree cons: more complex insert/split logic; rebalancing on insert/delete is costlier than a quadtree’s simpler splits.

Who/What Each Structure Fits Best

Quadtrees fit real-time, in-memory use cases where data is rebuilt frequently and rough uniformity can be assumed — game collision broad-phase, terrain/image tiling, and similar simulation workloads. R-trees fit persistent, disk-backed spatial databases handling real-world geographic data with irregular shapes — which is exactly why PostGIS, most commercial GIS software, and mapping platforms build their spatial indexes around R-tree-style structures rather than quadtrees.

Bottom Line

Both quadtrees and R-trees exist to answer the same question — “what’s near this point or inside this region” — far faster than checking every record. The right choice comes down to your data’s shape: evenly distributed, simulation-style data favors a quadtree’s simplicity; irregular, real-world geographic data favors an R-tree’s adaptive bounding-rectangle grouping, which is why it underpins production spatial databases like PostGIS.

FAQ

Is a quadtree the same as an octree?
No — a quadtree subdivides 2D space into four regions per split; an octree is its 3D analog, subdividing space into eight regions, commonly used in 3D graphics and voxel engines.

Does PostGIS use quadtrees?
No — per PostGIS’s own indexing documentation, its spatial indexes run on PostgreSQL’s GiST index type implementing an R-tree-style structure, not a quadtree.

Are these the same as pathfinding structures like A*?
No. Quadtrees and R-trees answer “what objects exist in this region” (spatial range/nearest-neighbor queries); pathfinding algorithms like Dijkstra and A* answer “what’s the shortest route through a graph” — a different problem entirely, even though both are common in games and mapping software.

Who invented the R-tree?
Antonin Guttman, in a paper published as a UC Berkeley technical report and presented at ACM SIGMOD in 1984.

Sources