R-Trees: The Data Structure That Makes Map Queries Fast

What Is an R-Tree?

An R-tree is a tree data structure designed to index spatial data, things like points, rectangles, roads, or building footprints, so they can be searched efficiently by location. It generalizes the idea behind a B-tree, where each internal node groups a range of sorted keys, into two or more dimensions, where each internal node groups a region of space. Every object stored in an R-tree, whether it is a single point or a complex polygon, is first approximated by its minimum bounding rectangle (MBR), the smallest axis-aligned rectangle that fully contains it. Leaf nodes of the tree hold these bounding boxes for the actual objects. Each level above the leaves groups a handful of child bounding boxes together and stores one larger bounding box that encloses all of them. Climb high enough in the tree and you reach a root node whose single bounding rectangle covers the entire dataset. This nesting means that a small number of large rectangles near the root can represent millions of tiny objects near the leaves, giving the structure a compact, logarithmic-height shape similar to a B-tree, but organized by spatial proximity instead of sorted order.

Why Range Queries Become Fast

The payoff of this nested structure shows up when you run a spatial range query, such as find all restaurants within this rectangle on the map. Instead of checking every restaurant in the dataset, the search starts at the root and asks a simple question at each node: does this child's bounding rectangle overlap the query area at all? If a child's bounding box does not overlap the query rectangle, the algorithm knows with certainty that nothing inside it can possibly match, so it prunes that entire branch and skips it without ever inspecting the objects nested inside. Only branches whose bounding rectangle does overlap the query get descended into, and the process repeats recursively at each level until the search reaches the leaf nodes containing actual objects. Because each pruned branch can represent thousands or millions of underlying objects, a single failed overlap check at a high level of the tree can eliminate enormous portions of the dataset in one step. This is what allows an R-tree to answer what's near me or what's inside this area queries against huge geographic datasets in milliseconds rather than scanning everything linearly.

Insertion and the Splitting Challenge

Building an R-tree well is harder than building a B-tree because there is no natural sort order for two-dimensional data. When a new object is inserted, the algorithm must choose which subtree to place it in, and the standard heuristic is to pick the child whose bounding rectangle would need the smallest enlargement to include the new object, breaking ties by choosing the smaller resulting area. This keeps bounding boxes tight and keeps spatially close objects grouped together. Each node has a maximum capacity, and when adding an entry pushes a node over that limit, the node must be split into two new nodes. The key challenge is deciding how to divide the entries between the two new bounding boxes so that they overlap each other as little as possible and each stays as small and tight as feasible. A poor split produces bounding rectangles that sprawl and overlap heavily, which forces future queries to descend into multiple branches unnecessarily and erodes the pruning power that makes the whole structure fast. Various splitting strategies, from simple quadratic heuristics to more exhaustive linear or R*-tree variants, all aim at this same goal: minimizing overlap and wasted area after a split.

The Key Difference From a B-Tree

The most important conceptual difference between an R-tree and a B-tree comes down to overlap. In a B-tree, keys at each level are strictly sorted and the ranges covered by sibling nodes never overlap, so a search for any given key follows exactly one path from root to leaf. An R-tree cannot offer that same guarantee, because two-dimensional rectangles do not have a single natural ordering the way numbers do. As a result, bounding rectangles at the same level of an R-tree are allowed to overlap one another. This is a deliberate and unavoidable tradeoff of extending tree indexing into multiple dimensions. The practical consequence is that even a query for a single point can require searching more than one branch: if two sibling bounding rectangles both happen to overlap the query point's location, the search must descend into both of them to be sure it finds every matching object. Good insertion and splitting heuristics work to minimize how much overlap occurs, since less overlap means fewer branches need to be checked, but some overlap is generally unavoidable in real-world spatial data, which is why R-tree query performance depends so heavily on how well the tree was built.

Real-World Uses

R-trees and their variants are the backbone of practical spatial indexing across the software industry. PostGIS, the spatial extension for PostgreSQL, uses an R-tree-based index (GiST, generalized search tree, with R-tree-style bounding box logic) to accelerate queries like finding all parcels within a boundary or all sensors within a radius. Other geographic databases and GIS engines, from Oracle Spatial to SQLite's SpatiaLite to MongoDB's geospatial indexes, rely on the same core idea. Mapping applications use R-trees to quickly determine which map tiles, points of interest, or road segments fall within the user's current viewport as they pan and zoom. Spatial games and simulations use them for collision detection and proximity queries, efficiently finding which objects are near a given character or region without checking every object in the world. More broadly, any system that needs to answer what's near me, what's inside this area, or which objects intersect this shape against a large collection of spatial data benefits from an R-tree, making it one of the quiet workhorses underlying modern location-based technology.

Frequently asked questions

Try it live

Everything above runs in your browser — open R-Trees: The Data Structure That Makes Map Queries Fast and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.