R-Tree and Geospatial / Multidimensional Range Search

Learning outcomes

A B-tree orders keys along one lexicographic dimension. Many spatial/range problems instead ask “which rectangles overlap this rectangle?” R*Tree is SQLite's specialized virtual-table module for that kind of multidimensional candidate search. It is not a complete GIS system, which is precisely why the lesson keeps geometry simple and observable.

Start with rectangles, not maps

Imagine a local coordinate system measured in meters inside North Plant. Each asset occupies a rectangular footprint: min_x to max_x and min_y to max_y. A maintenance planner draws a viewport or work zone and asks which asset rectangles overlap it. That is the native R*Tree problem.

Two rectangles overlap when all four conditions hold:asset.max_x >= query.min_xasset.min_x <= query.max_xasset.max_y >= query.min_yasset.min_y <= query.max_y

Confirm the R*Tree module, then create the index

SELECT nameFROM pragma_module_listWHERE name IN ('rtree','rtree_i32');DROP TABLE IF EXISTS device_bounds;CREATE VIRTUAL TABLE device_bounds USING rtree(  device_id,  min_x, max_x,  min_y, max_y);

The first column is the row identifier. Each dimension is represented by a lower and upper bound. R*Tree supports up to five dimensions, but two dimensions are enough to build the mental model.

Populate FieldNotes asset footprints

INSERT INTO device_bounds VALUES(1, 10.0, 13.5, 20.0, 23.0),  -- PUMP-007(2, 18.0, 22.0, 19.0, 22.0),  -- FAN-014(3, 12.0, 12.4, 28.0, 28.4),  -- SENS-003(4, 30.0, 35.0, 10.0, 15.0),  -- storage skid(5, 21.5, 24.0, 22.0, 26.0);  -- valve stationSELECT * FROM device_bounds ORDER BY device_id;

In a real schema, an ordinary asset/device table owns names, status, foreign keys, and business attributes. The R*Tree owns only the specialized multidimensional search bounds plus an id that lets the result join back to relational data.

Overlap queries are symmetric range constraints

-- Query rectangle: x=11..21, y=18..24SELECT device_id,min_x,max_x,min_y,max_yFROM device_boundsWHERE max_x >= 11.0  AND min_x <= 21.0  AND max_y >= 18.0  AND min_y <= 24.0ORDER BY device_id;

The module can use several bound constraints together. You do not need to constrain every coordinate for an R*Tree query to be useful, although tighter boxes and more applicable constraints usually reduce candidates.

Join candidate ids back to relational facts

SELECT d.device_code,       d.device_name,       d.status,       b.min_x,b.max_x,b.min_y,b.max_yFROM device_bounds AS bJOIN device AS d ON d.device_id=b.device_idWHERE b.max_x >= 11.0  AND b.min_x <= 21.0  AND b.max_y >= 18.0  AND b.min_y <= 24.0ORDER BY d.device_code;

This separation is powerful: R*Tree answers “which ids have bounding boxes that qualify?” while ordinary tables retain the richer relational contract. Do not try to turn the virtual table into the whole application schema.

Point and containment queries are variations of the same bounds

-- Which asset boxes contain the point (12.2, 21.0)?SELECT device_idFROM device_boundsWHERE min_x <= 12.2 AND max_x >= 12.2  AND min_y <= 21.0 AND max_y >= 21.0;-- Which asset boxes are completely inside x=9..25, y=18..30?SELECT device_idFROM device_boundsWHERE min_x >= 9.0 AND max_x <= 25.0  AND min_y >= 18.0 AND max_y <= 30.0ORDER BY device_id;

For exact containment near floating-point boundaries, apply the rounding guidance in the next section instead of assuming decimal text values are represented exactly.

Default R*Tree coordinates are 32-bit floating point

The default rtree module stores coordinates as single-precision floating-point values. When a coordinate cannot be represented exactly, SQLite rounds lower bounds slightly downward and upper bounds slightly upward. This outward rounding is desirable for overlap queries because it avoids false negatives at edges; it can admit a few extra candidates.

Use rtree_i32 when the coordinate domain is truly integer

If your logical bounds are signed 32-bit integers, SQLite also exposes rtree_i32. It stores integer coordinates, though the R-tree algorithm still uses floating-point computations internally. Choosing integer coordinates can be natural for pixel boxes, grid cells, or fixed engineering units—but do not rescale real-world coordinates without documenting units and range limits.

CREATE VIRTUAL TABLE temp.grid_bounds USING rtree_i32(  object_id,  min_col,max_col,  min_row,max_row);

Why a composite B-tree is not the same index

A normal index such as (min_x,max_x,min_y,max_y) is ordered lexicographically: first by min_x, then by the next column among rows sharing the earlier prefix. An overlap query constrains lower and upper bounds across multiple dimensions in both directions. R*Tree is designed around bounding regions rather than one leftmost B-tree ordering.

R*Tree gives candidates, not universal GIS semantics

Core R*Tree does not know that 51.5 means latitude, how to cross the antimeridian, what a polygon hole means, or which Earth projection is appropriate. It indexes numeric bounds. For exact lines/polygons/circles or geodetic distance, you need additional domain logic or a trusted spatial extension and must verify its coordinate-system semantics.

Lab: maintenance work-zone selection

-- Work zone chosen by a planner:--   qminx=17, qmaxx=25, qminy=18, qmaxy=27WITH zone(qminx,qmaxx,qminy,qmaxy) AS (  VALUES(17.0,25.0,18.0,27.0))SELECT b.device_id,b.min_x,b.max_x,b.min_y,b.max_yFROM device_bounds AS b, zone AS zWHERE b.max_x >= z.qminx  AND b.min_x <= z.qmaxx  AND b.max_y >= z.qminy  AND b.min_y <= z.qmaxyORDER BY b.device_id;

Predict the ids before running it, then shrink and move the query rectangle. Use EXPLAIN QUERY PLAN to confirm the query is operating through the virtual table; avoid depending on the exact text of the plan because EQP formatting is not a stable application API.

Verification checkpoint

Production judgment and bridge

R*Tree shows why SQLite's module architecture is valuable: a specialized access method remains queryable through SQL without pretending it is an ordinary B-tree index. Lesson 5 closes the chapter by treating extensions as deployable executable dependencies rather than convenient files to load casually.

Authoritative references

• SQLite R*Tree Module
• SQLite Virtual Table Mechanism
• SQLite EXPLAIN QUERY PLAN