Database Management SystemsSpatial Indexes

Spatial Indexes: Indexing Multi-Dimensional Data

LevelAdvanced

Duration75 mins

TopicSpatial Indexes

3 / 5

MBR: The Heart of Spatial Index Approximation

Why Simple Rectangles Power Complex Spatial Queries

Spatial databases store extraordinarily complex geometries: national boundaries with thousands of vertices, river networks with intricate branching, building footprints with detailed architectural features. Yet the secret to searching these complex shapes quickly is remarkably simple: wrap each object in the smallest axis-aligned rectangle that contains it.

This Minimum Bounding Rectangle (MBR), also called a bounding box or envelope, is a crude approximation—a complex polygon becomes just four numbers (min_x, max_x, min_y, max_y). But this simplification is strategic:

Constant-size storage — MBRs use fixed 32 bytes regardless of geometry complexity
O(1) intersection test — Checking if two rectangles overlap requires only 4 comparisons
Conservative filter — An MBR always contains its geometry, so non-intersecting MBRs guarantee non-intersecting geometries

The MBR trades precision for speed, creating a two-stage query process: fast MBR filtering followed by exact geometry verification on remaining candidates. This filter-and-refine pattern is the foundation of all spatial index performance.

What You Will Learn

By the end of this page, you will master MBR computation for all geometry types, understand how MBR quality affects query performance, learn the mathematical operations used in R-tree algorithms, and appreciate both the power and limitations of this approximation strategy.

MBR Definition and Properties

A Minimum Bounding Rectangle (MBR) is the smallest axis-aligned rectangle that completely encloses a geometric object. More formally:

Definition: For a geometry G, the MBR is defined as:

MBR(G) = [min_x, max_x] × [min_y, max_y]

where:

min_x = minimum x-coordinate of any point in G
max_x = maximum x-coordinate of any point in G
min_y = minimum y-coordinate of any point in G
max_y = maximum y-coordinate of any point in G

Key MBR Properties

•Axis-aligned — MBR edges are always parallel to coordinate axes. This simplifies intersection tests but can poorly fit rotated shapes.
•Minimal — The MBR is the tightest possible axis-aligned rectangle. There is exactly one MBR for any geometry.
•Conservative — Every point of the geometry lies within or on the MBR. G ⊆ MBR(G) always holds.
•Monotonic under union — MBR(G₁ ∪ G₂) = MBR(MBR(G₁), MBR(G₂)). The MBR of a set equals the MBR of component MBRs.
•Degenerate cases — A point has a zero-area MBR (min_x = max_x, min_y = max_y). A horizontal line has zero height.
•Dimension-independent — The concept extends naturally to 3D (bounding boxes) or higher dimensions (hyper-rectangles).

mbr_structure.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Complete MBR implementation
interface MBR {
    minX: number;   // Western-most longitude
    maxX: number;   // Eastern-most longitude
    minY: number;   // Southern-most latitude
    maxY: number;   // Northern-most latitude
}
 
// Factory functions for common geometries
function pointMBR(x: number, y: number): MBR {
    return { minX: x, maxX: x, minY: y, maxY: y };
}
 
function lineMBR(x1: number, y1: number, x2: number, y2: number): MBR {
    return {
        minX: Math.min(x1, x2),
        maxX: Math.max(x1, x2),
        minY: Math.min(y1, y2),
        maxY: Math.max(y1, y2)
    };
}
 
// Validate MBR invariants
function isValid(mbr: MBR): boolean {
    return mbr.minX <= mbr.maxX && 
           mbr.minY <= mbr.maxY &&
           isFinite(mbr.minX) && isFinite(mbr.maxX) &&
           isFinite(mbr.minY) && isFinite(mbr.maxY);
}
 
// Check for degenerate (zero-area) MBR
function isDegenerate(mbr: MBR): boolean {
    return mbr.minX === mbr.maxX || mbr.minY === mbr.maxY;
}

Computing MBRs for All Geometry Types

Different geometry types require different MBR computation strategies. While the principle is always 'find min/max coordinates,' the implementation details matter for both correctness and performance.

MBR Computation by Geometry Type
Geometry Type	MBR Computation	Time Complexity
Point	MBR = point itself (degenerate)	O(1)
LineString (n vertices)	Min/max across all vertices	O(n)
Polygon (n vertices)	Min/max across exterior ring vertices	O(n)
Polygon with holes	Only exterior ring matters	O(n_exterior)
MultiPoint (k points)	Min/max across all points	O(k)
MultiPolygon (k polygons)	Union of component MBRs	O(k + Σvertices)
GeometryCollection	Union of component MBRs	O(total elements)
Circular arc	Must consider extremal points	O(1) per arc

mbr_computation.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Generic MBR computation for any point sequence
function computeMBRFromPoints(points: Array<{x: number, y: number}>): MBR {
    if (points.length === 0) {
        throw new Error("Cannot compute MBR of empty point set");
    }
    
    let minX = Infinity, maxX = -Infinity;
    let minY = Infinity, maxY = -Infinity;
    
    for (const p of points) {
        if (p.x < minX) minX = p.x;
        if (p.x > maxX) maxX = p.x;
        if (p.y < minY) minY = p.y;
        if (p.y > maxY) maxY = p.y;
    }
    
    return { minX, maxX, minY, maxY };
}
 
// Polygon MBR - only needs exterior ring
function polygonMBR(exteriorRing: Array<{x: number, y: number}>): MBR {
    // Holes are by definition inside exterior ring,
    // so they don't affect the MBR
    return computeMBRFromPoints(exteriorRing);
}
 
// Union of two MBRs (used for multi-geometries and R-tree nodes)
function unionMBR(a: MBR, b: MBR): MBR {
    return {
        minX: Math.min(a.minX, b.minX),
        maxX: Math.max(a.maxX, b.maxX),
        minY: Math.min(a.minY, b.minY),
        maxY: Math.max(a.maxY, b.maxY)
    };
}
 
// Multi-geometry MBR
function multiPolygonMBR(polygons: Array<Array<{x: number, y: number}>>): MBR {
    let result = polygonMBR(polygons[0]);
    for (let i = 1; i < polygons.length; i++) {
        result = unionMBR(result, polygonMBR(polygons[i]));
    }
    return result;
}
 
// Circular arc MBR - more complex, must find extremal points
function circularArcMBR(center: {x: number, y: number}, 
                        radius: number, 
                        startAngle: number, 
                        endAngle: number): MBR {
    // Start with endpoints
    let minX = center.x + radius * Math.cos(startAngle);
    let maxX = minX;
    let minY = center.y + radius * Math.sin(startAngle);
    let maxY = minY;
    
    const endX = center.x + radius * Math.cos(endAngle);
    const endY = center.y + radius * Math.sin(endAngle);
    minX = Math.min(minX, endX);
    maxX = Math.max(maxX, endX);
    minY = Math.min(minY, endY);
    maxY = Math.max(maxY, endY);
    
    // Check if arc crosses cardinal directions
    const checkAngles = [0, Math.PI/2, Math.PI, 3*Math.PI/2];  // E, N, W, S
    const extremes = [
        {x: center.x + radius, y: center.y},   // East
        {x: center.x, y: center.y + radius},   // North
        {x: center.x - radius, y: center.y},   // West
        {x: center.x, y: center.y - radius}    // South
    ];
    
    for (let i = 0; i < checkAngles.length; i++) {
        if (angleInArc(checkAngles[i], startAngle, endAngle)) {
            minX = Math.min(minX, extremes[i].x);
            maxX = Math.max(maxX, extremes[i].x);
            minY = Math.min(minY, extremes[i].y);
            maxY = Math.max(maxY, extremes[i].y);
        }
    }
    
    return { minX, maxX, minY, maxY };
}

Circular Geometry Pitfall

The MBR of a circular arc is NOT simply the bounding box of its endpoints. An arc from 45° to 135° extends further north than either endpoint. Always check if the arc crosses any cardinal direction (0°, 90°, 180°, 270°) and include those extremal points. This same principle applies to ellipses, Bezier curves, and splines.

MBR Relationship Tests

R-tree algorithms rely heavily on testing relationships between MBRs. These O(1) tests are the workhorses of spatial queries—executed millions of times during a single query on a large dataset.

mbr_relationships.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Does MBR 'a' intersect MBR 'b' (including touching)?
// This is the most frequently called function in spatial databases
function intersects(a: MBR, b: MBR): boolean {
    // Two rectangles intersect iff they overlap in BOTH dimensions
    return a.maxX >= b.minX && a.minX <= b.maxX &&
           a.maxY >= b.minY && a.minY <= b.maxY;
}
 
// Is MBR 'inner' completely contained within MBR 'outer'?
function contains(outer: MBR, inner: MBR): boolean {
    return outer.minX <= inner.minX && outer.maxX >= inner.maxX &&
           outer.minY <= inner.minY && outer.maxY >= inner.maxY;
}
 
// Does MBR 'a' contain point (x, y)?
function containsPoint(a: MBR, x: number, y: number): boolean {
    return x >= a.minX && x <= a.maxX &&
           y >= a.minY && y <= a.maxY;
}
 
// Are the two MBRs disjoint (no intersection)?
function disjoint(a: MBR, b: MBR): boolean {
    return !intersects(a, b);
}
 
// Do the two MBRs touch (intersect at boundary only)?
function touches(a: MBR, b: MBR): boolean {
    if (!intersects(a, b)) return false;
    // They touch if intersection area is zero
    // (they share an edge or corner but not interior)
    const interX = Math.max(0, Math.min(a.maxX, b.maxX) - Math.max(a.minX, b.minX));
    const interY = Math.max(0, Math.min(a.maxY, b.maxY) - Math.max(a.minY, b.minY));
    return interX === 0 || interY === 0;
}
 
// Compute the intersection MBR (undefined if disjoint)
function intersection(a: MBR, b: MBR): MBR | undefined {
    const minX = Math.max(a.minX, b.minX);
    const maxX = Math.min(a.maxX, b.maxX);
    const minY = Math.max(a.minY, b.minY);
    const maxY = Math.min(a.maxY, b.maxY);
    
    if (minX > maxX || minY > maxY) {
        return undefined;  // No intersection
    }
    
    return { minX, maxX, minY, maxY };
}

Why Separating Axis Theorem Matters:

The intersects() test works because of the Separating Axis Theorem: two convex shapes do NOT intersect if and only if there exists an axis along which their projections don't overlap.

For axis-aligned rectangles, we only need to check the X and Y axes:

If projections on X-axis don't overlap: disjoint
If projections on Y-axis don't overlap: disjoint
Otherwise: intersecting

This reduces a 2D geometric test to two 1D interval overlap checks, each requiring only 2 comparisons.

Performance Critical:

In a query processing billions of candidates:

intersects() may be called 10 million times
Each call: 4 comparisons, no branching (can be vectorized)
Total: ~10ms on modern CPUs for 10M tests
Same exact geometry test: ~10 seconds (1000x slower)

MBR Metrics for R-tree Decisions

R-tree algorithms make critical decisions based on quantitative MBR metrics. Understanding these metrics reveals why certain insertion and splitting strategies perform better than others.

mbr_metrics.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Area: Total space enclosed by MBR
function area(mbr: MBR): number {
    return (mbr.maxX - mbr.minX) * (mbr.maxY - mbr.minY);
}
 
// Perimeter: Total edge length (prefer square-ish MBRs)
function perimeter(mbr: MBR): number {
    return 2 * ((mbr.maxX - mbr.minX) + (mbr.maxY - mbr.minY));
}
 
// Center point of MBR
function center(mbr: MBR): { x: number; y: number } {
    return {
        x: (mbr.minX + mbr.maxX) / 2,
        y: (mbr.minY + mbr.maxY) / 2
    };
}
 
// Distance between MBR centers
function centerDistance(a: MBR, b: MBR): number {
    const ca = center(a);
    const cb = center(b);
    return Math.sqrt((ca.x - cb.x) ** 2 + (ca.y - cb.y) ** 2);
}
 
// Overlap area between two MBRs
function overlapArea(a: MBR, b: MBR): number {
    const inter = intersection(a, b);
    return inter ? area(inter) : 0;
}
 
// Enlargement: How much must MBR 'original' grow to contain 'newObject'?
// Key metric for choosing insertion path
function enlargement(original: MBR, newObject: MBR): number {
    const combined = unionMBR(original, newObject);
    return area(combined) - area(original);
}
 
// Margin (half-perimeter): Used by R*-tree for split axis selection
function margin(mbr: MBR): number {
    return (mbr.maxX - mbr.minX) + (mbr.maxY - mbr.minY);
}
 
// Aspect ratio: Width/Height ratio (1.0 = perfect square)
function aspectRatio(mbr: MBR): number {
    const width = mbr.maxX - mbr.minX;
    const height = mbr.maxY - mbr.minY;
    if (height === 0) return Infinity;
    return Math.max(width/height, height/width);
}
 
// Dead space: Percentage of MBR not covered by contained objects
function deadSpaceRatio(mbrArea: number, containedObjectsArea: number): number {
    if (mbrArea === 0) return 0;
    return (mbrArea - containedObjectsArea) / mbrArea;
}

How Metrics Drive R-tree Decisions
Decision Point	Primary Metric	Secondary Metric	Goal
Choose subtree for insert	Enlargement	Area, then entries	Minimize MBR growth
Choose split axis (R*)	Margin sum	—	Prefer square groups
Choose split distribution	Overlap	Area sum	Minimize query paths
Choose entries to reinsert	Center distance	—	Remove peripheral entries
Evaluate tree quality	Total overlap	Dead space	Assess query efficiency

Why Perimeter/Margin Matters

A long, thin MBR has the same area as a square MBR but a much larger perimeter. The R*-tree prefers square-ish MBRs because they're less likely to intersect random queries. A 100×1 MBR intersects far more horizontal query lines than a 10×10 MBR of equal area.

MBR Quality and Query Performance

The relationship between MBR quality and query performance is direct and measurable. Poor MBRs cause unnecessary work; excellent MBRs enable aggressive pruning.

High-Quality MBR Characteristics

•Tight fit — MBR closely matches contained geometry
•Low dead space — Most MBR area contains actual data
•Square-ish shape — Balanced width and height
•Low overlap — Minimal intersection with sibling MBRs
•Clustered contents — Children are spatially coherent

Low-Quality MBR Characteristics

•Inflated — Much larger than necessary
•High dead space — Mostly empty area
•Elongated — Very thin or stretched
•Heavy overlap — Many intersections with siblings
•Scattered contents — Children are spatially dispersed

Quantifying the Impact:

Consider a query that should return 100 objects from a dataset of 1 million:

Tree Quality	MBR Overlap	Nodes Examined	I/O Cost	Query Time
Excellent	5%	~20	20 reads	2ms
Good	15%	~60	60 reads	6ms
Poor	40%	~500	500 reads	50ms
Terrible	80%	~10,000	10K reads	1000ms

The difference between a well-organized R-tree and a poorly organized one can be 500x in query performance—and the only difference is MBR quality!

analyze_tree_quality.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
-- PostgreSQL/PostGIS: Analyze R-tree quality for a table
-- This query estimates overlap and dead space
 
WITH index_stats AS (
    SELECT 
        idx.indexrelid::regclass AS index_name,
        pg_relation_size(idx.indexrelid) AS index_size,
        n_distinct,
        correlation
    FROM pg_stat_user_indexes idx
    JOIN pg_stats s ON s.tablename = idx.relname
    WHERE idx.indexrelid::regclass::text LIKE '%gist%'
)
SELECT * FROM index_stats;
 
-- Estimate dead space by comparing MBR area to actual geometry area
SELECT 
    AVG(ST_Area(ST_Envelope(geom)) / NULLIF(ST_Area(geom), 0)) AS avg_mbr_inflation,
    MAX(ST_Area(ST_Envelope(geom)) / NULLIF(ST_Area(geom), 0)) AS max_mbr_inflation
FROM spatial_table
WHERE ST_Area(geom) > 0;
 
-- Check for problematic long/thin geometries
SELECT id, 
       ST_Area(geom) AS area,
       ST_Perimeter(geom) AS perimeter,
       ST_Perimeter(geom)^2 / (4 * 3.14159 * ST_Area(geom)) AS circularity
FROM spatial_table 
WHERE ST_Area(geom) > 0
ORDER BY circularity DESC
LIMIT 10;

The Filter-and-Refine Query Pattern

Spatial query processing uses a fundamental two-phase approach that leverages MBRs for efficiency while maintaining correctness. Understanding this pattern is essential for writing efficient spatial queries.

filter_refine_pattern.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
SPATIAL QUERY: Find all parks that intersect the flood zone
 
┌─────────────────────────────────────────────────────────────────────────┐
│                        PHASE 1: FILTER (Fast)                           │
│                                                                         │
│  Use R-tree index to find all parks whose MBRs intersect               │
│  the flood zone's MBR                                                   │
│                                                                         │
│  Query MBR: [x1, x2] × [y1, y2]                                        │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                CANDIDATES (MBR intersects)                       │   │
│  │  Park A ✓    Park B ✓    Park C ✓    Park D ✓    Park E ✓      │   │
│  │  (May or may not actually intersect the flood zone polygon)     │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Statistics: 1,000,000 parks → 5,000 candidates (0.5%)                 │
│  Cost: ~5 index page reads + 5,000 MBR comparisons                     │
│  Time: ~5ms                                                             │
└─────────────────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────────────┐
│                      PHASE 2: REFINE (Accurate)                         │
│                                                                         │
│  For each candidate, perform exact geometric intersection test          │
│  using the actual polygon shapes                                        │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │              EXACT TEST: ST_Intersects(park, flood_zone)        │   │
│  │  Park A: TRUE ✓   (actually intersects)                         │   │
│  │  Park B: FALSE ✗  (MBR overlapped but polygon doesn't)          │   │
│  │  Park C: TRUE ✓   (actually intersects)                         │   │
│  │  Park D: FALSE ✗  (MBR overlapped but polygon doesn't)          │   │
│  │  Park E: TRUE ✓   (actually intersects)                         │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Statistics: 5,000 candidates → 42 results (0.84% of candidates)       │
│  Cost: 5,000 polygon intersection tests                                 │
│  Time: ~50ms                                                            │
└─────────────────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────────────┐
│                        FINAL RESULT: 42 parks                           │
│                        Total time: ~55ms                                │
│                                                                         │
│  Without index: 1,000,000 polygon tests × 10µs = 10,000ms (10 sec)     │
│  With index:    5,000 polygon tests = 50ms + 5ms index = 55ms          │
│                                                                         │
│  SPEEDUP: 180x                                                          │
└─────────────────────────────────────────────────────────────────────────┘

False Positives Are Expected

In the example above, Parks B and D were false positives—their MBRs overlapped the query, but the actual polygons didn't intersect. This is normal and expected. The filter phase is intentionally conservative: it may include false positives but never false negatives. The refine phase eliminates false positives at the cost of geometry computation.

Implications for Query Writing:

Understanding filter-and-refine helps you write faster queries:

-- SLOW: Forces refine on many false positives
SELECT * FROM parks
WHERE ST_Intersects(geom, :complex_flood_zone);

-- FASTER: Explicit two-stage with simplified filter
-- (Sometimes helps optimizer choose better plan)
WITH candidates AS (
    SELECT * FROM parks
    WHERE geom && ST_Envelope(:complex_flood_zone)  -- && = MBR overlap
)
SELECT * FROM candidates
WHERE ST_Intersects(geom, :complex_flood_zone);

Modern query optimizers usually apply this pattern automatically, but for complex queries or non-standard spatial operations, explicit staging can help.

MBR Challenges and Edge Cases

While MBRs are powerful, they have inherent limitations. Understanding these helps you design better schemas and write more robust queries.

Common MBR Challenges

•Diagonal objects — A line from (0,0) to (100,100) has an MBR covering 10,000 square units but actual area of zero. Queries anywhere in this box become false positives.
•Concave shapes — A crescent moon shape has an MBR including lots of empty space where the concavity is. High false positive rate.
•Multi-polygons with spread — An archipelago spanning 1000km has an MBR including thousands of km² of ocean.
•Global geometries — A shipping route from New York to Shanghai has an MBR covering half the planet.
•Anti-meridian crossing — Geometries crossing longitude ±180° require special handling (split or wrap-around MBRs).
•Polar distortion — Near poles, longitude degrees converge; MBRs in lat/lon become increasingly distorted.

mbr_edge_cases.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
-- Problem: Diagonal line creates huge MBR with zero actual area
-- The MBR of this line covers 10,000 square degrees
SELECT ST_Envelope(
    ST_GeomFromText('LINESTRING(0 0, 100 100)', 4326)
);
-- Result: POLYGON((0 0, 100 0, 100 100, 0 100, 0 0))
 
-- Every point query in this 10,000 sq deg area will hit this line's MBR!
 
-- Solution 1: Segment long lines
-- Break the line into smaller segments for tighter MBRs
 
-- Problem: Anti-meridian crossing
-- A line from Japan (140°E) to USA (-120°W) crossing the Pacific
SELECT ST_Envelope(
    ST_GeomFromText('LINESTRING(140 35, -120 35)', 4326)
);
-- WRONG: Creates MBR from -120 to 140 (260 degrees, most of Earth!)
-- Should be: MBR from 140 to 180, then -180 to -120 (100 degrees)
 
-- Solution: Use geography type or split at anti-meridian
SELECT ST_Split(
    ST_GeomFromText('LINESTRING(140 35, -120 35)', 4326),
    ST_GeomFromText('LINESTRING(180 -90, 180 90)', 4326)
);
 
-- Problem: Polar regions
-- At 85°N, one degree of longitude is only ~9.7 km
-- But the MBR treats it the same as at equator (111 km)
-- Result: Massive over-filtering near poles

Strategies for Problematic Geometries

For highly irregular shapes: (1) Store simplified versions for filtering, (2) Decompose into regular pieces, (3) Use convex hull as intermediate approximation, (4) Consider alternative indexes like space-filling curves for extreme cases. The goal is reducing the gap between MBR area and actual geometry area.

Summary: MBR Mastery

We've thoroughly examined the Minimum Bounding Rectangle—the simple yet powerful abstraction that enables efficient spatial indexing. Let's consolidate the essential insights:

Key Takeaways

•MBRs are axis-aligned rectangles — Defined by just 4 values (min_x, max_x, min_y, max_y), regardless of geometry complexity.
•O(1) intersection tests — MBR overlap checking requires only 4 comparisons, enabling filtering of millions of objects in milliseconds.
•Conservative approximation — MBRs never exclude valid results but may include false positives that refine phase eliminates.
•Quality metrics — Area, overlap, enlargement, and perimeter drive R-tree algorithmic decisions.
•Filter-and-refine pattern — MBRs handle fast elimination; exact geometry tests verify remaining candidates.
•Limitations exist — Diagonal, concave, and global geometries reduce MBR effectiveness; mitigation strategies are available.
•MBR quality = query performance — 500x performance differences possible between well-organized and poorly organized R-trees.

What's Next:

With a solid understanding of MBRs, we're ready to explore R-tree operations. The next page covers the complete algorithmic details: search algorithms for range and nearest-neighbor queries, insertion with the ChooseSubtree algorithm, node splitting strategies, and deletion with underflow handling. You'll see how MBR metrics directly drive these algorithmic decisions.

Page Complete

You now have deep understanding of Minimum Bounding Rectangles—their computation, properties, relationship tests, quality metrics, and role in the filter-and-refine pattern. This knowledge is essential for understanding R-tree algorithms and optimizing spatial query performance.

3 / 5

Loading learning content...

Database Management SystemsSpatial Indexes

Spatial Indexes: Indexing Multi-Dimensional Data

LevelAdvanced

Duration75 mins

TopicSpatial Indexes

3 / 5

MBR: The Heart of Spatial Index Approximation

Why Simple Rectangles Power Complex Spatial Queries

Constant-size storage — MBRs use fixed 32 bytes regardless of geometry complexity
O(1) intersection test — Checking if two rectangles overlap requires only 4 comparisons
Conservative filter — An MBR always contains its geometry, so non-intersecting MBRs guarantee non-intersecting geometries

What You Will Learn

MBR Definition and Properties

A Minimum Bounding Rectangle (MBR) is the smallest axis-aligned rectangle that completely encloses a geometric object. More formally:

Definition: For a geometry G, the MBR is defined as:

MBR(G) = [min_x, max_x] × [min_y, max_y]

where:

min_x = minimum x-coordinate of any point in G
max_x = maximum x-coordinate of any point in G
min_y = minimum y-coordinate of any point in G
max_y = maximum y-coordinate of any point in G

Key MBR Properties

•Axis-aligned — MBR edges are always parallel to coordinate axes. This simplifies intersection tests but can poorly fit rotated shapes.
•Minimal — The MBR is the tightest possible axis-aligned rectangle. There is exactly one MBR for any geometry.
•Conservative — Every point of the geometry lies within or on the MBR. G ⊆ MBR(G) always holds.
•Monotonic under union — MBR(G₁ ∪ G₂) = MBR(MBR(G₁), MBR(G₂)). The MBR of a set equals the MBR of component MBRs.
•Degenerate cases — A point has a zero-area MBR (min_x = max_x, min_y = max_y). A horizontal line has zero height.
•Dimension-independent — The concept extends naturally to 3D (bounding boxes) or higher dimensions (hyper-rectangles).

mbr_structure.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Complete MBR implementation
interface MBR {
    minX: number;   // Western-most longitude
    maxX: number;   // Eastern-most longitude
    minY: number;   // Southern-most latitude
    maxY: number;   // Northern-most latitude
}
 
// Factory functions for common geometries
function pointMBR(x: number, y: number): MBR {
    return { minX: x, maxX: x, minY: y, maxY: y };
}
 
function lineMBR(x1: number, y1: number, x2: number, y2: number): MBR {
    return {
        minX: Math.min(x1, x2),
        maxX: Math.max(x1, x2),
        minY: Math.min(y1, y2),
        maxY: Math.max(y1, y2)
    };
}
 
// Validate MBR invariants
function isValid(mbr: MBR): boolean {
    return mbr.minX <= mbr.maxX && 
           mbr.minY <= mbr.maxY &&
           isFinite(mbr.minX) && isFinite(mbr.maxX) &&
           isFinite(mbr.minY) && isFinite(mbr.maxY);
}
 
// Check for degenerate (zero-area) MBR
function isDegenerate(mbr: MBR): boolean {
    return mbr.minX === mbr.maxX || mbr.minY === mbr.maxY;
}

Computing MBRs for All Geometry Types

MBR Computation by Geometry Type
Geometry Type	MBR Computation	Time Complexity
Point	MBR = point itself (degenerate)	O(1)
LineString (n vertices)	Min/max across all vertices	O(n)
Polygon (n vertices)	Min/max across exterior ring vertices	O(n)
Polygon with holes	Only exterior ring matters	O(n_exterior)
MultiPoint (k points)	Min/max across all points	O(k)
MultiPolygon (k polygons)	Union of component MBRs	O(k + Σvertices)
GeometryCollection	Union of component MBRs	O(total elements)
Circular arc	Must consider extremal points	O(1) per arc

mbr_computation.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Generic MBR computation for any point sequence
function computeMBRFromPoints(points: Array<{x: number, y: number}>): MBR {
    if (points.length === 0) {
        throw new Error("Cannot compute MBR of empty point set");
    }
    
    let minX = Infinity, maxX = -Infinity;
    let minY = Infinity, maxY = -Infinity;
    
    for (const p of points) {
        if (p.x < minX) minX = p.x;
        if (p.x > maxX) maxX = p.x;
        if (p.y < minY) minY = p.y;
        if (p.y > maxY) maxY = p.y;
    }
    
    return { minX, maxX, minY, maxY };
}
 
// Polygon MBR - only needs exterior ring
function polygonMBR(exteriorRing: Array<{x: number, y: number}>): MBR {
    // Holes are by definition inside exterior ring,
    // so they don't affect the MBR
    return computeMBRFromPoints(exteriorRing);
}
 
// Union of two MBRs (used for multi-geometries and R-tree nodes)
function unionMBR(a: MBR, b: MBR): MBR {
    return {
        minX: Math.min(a.minX, b.minX),
        maxX: Math.max(a.maxX, b.maxX),
        minY: Math.min(a.minY, b.minY),
        maxY: Math.max(a.maxY, b.maxY)
    };
}
 
// Multi-geometry MBR
function multiPolygonMBR(polygons: Array<Array<{x: number, y: number}>>): MBR {
    let result = polygonMBR(polygons[0]);
    for (let i = 1; i < polygons.length; i++) {
        result = unionMBR(result, polygonMBR(polygons[i]));
    }
    return result;
}
 
// Circular arc MBR - more complex, must find extremal points
function circularArcMBR(center: {x: number, y: number}, 
                        radius: number, 
                        startAngle: number, 
                        endAngle: number): MBR {
    // Start with endpoints
    let minX = center.x + radius * Math.cos(startAngle);
    let maxX = minX;
    let minY = center.y + radius * Math.sin(startAngle);
    let maxY = minY;
    
    const endX = center.x + radius * Math.cos(endAngle);
    const endY = center.y + radius * Math.sin(endAngle);
    minX = Math.min(minX, endX);
    maxX = Math.max(maxX, endX);
    minY = Math.min(minY, endY);
    maxY = Math.max(maxY, endY);
    
    // Check if arc crosses cardinal directions
    const checkAngles = [0, Math.PI/2, Math.PI, 3*Math.PI/2];  // E, N, W, S
    const extremes = [
        {x: center.x + radius, y: center.y},   // East
        {x: center.x, y: center.y + radius},   // North
        {x: center.x - radius, y: center.y},   // West
        {x: center.x, y: center.y - radius}    // South
    ];
    
    for (let i = 0; i < checkAngles.length; i++) {
        if (angleInArc(checkAngles[i], startAngle, endAngle)) {
            minX = Math.min(minX, extremes[i].x);
            maxX = Math.max(maxX, extremes[i].x);
            minY = Math.min(minY, extremes[i].y);
            maxY = Math.max(maxY, extremes[i].y);
        }
    }
    
    return { minX, maxX, minY, maxY };
}

Circular Geometry Pitfall

MBR Relationship Tests

R-tree algorithms rely heavily on testing relationships between MBRs. These O(1) tests are the workhorses of spatial queries—executed millions of times during a single query on a large dataset.

mbr_relationships.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Does MBR 'a' intersect MBR 'b' (including touching)?
// This is the most frequently called function in spatial databases
function intersects(a: MBR, b: MBR): boolean {
    // Two rectangles intersect iff they overlap in BOTH dimensions
    return a.maxX >= b.minX && a.minX <= b.maxX &&
           a.maxY >= b.minY && a.minY <= b.maxY;
}
 
// Is MBR 'inner' completely contained within MBR 'outer'?
function contains(outer: MBR, inner: MBR): boolean {
    return outer.minX <= inner.minX && outer.maxX >= inner.maxX &&
           outer.minY <= inner.minY && outer.maxY >= inner.maxY;
}
 
// Does MBR 'a' contain point (x, y)?
function containsPoint(a: MBR, x: number, y: number): boolean {
    return x >= a.minX && x <= a.maxX &&
           y >= a.minY && y <= a.maxY;
}
 
// Are the two MBRs disjoint (no intersection)?
function disjoint(a: MBR, b: MBR): boolean {
    return !intersects(a, b);
}
 
// Do the two MBRs touch (intersect at boundary only)?
function touches(a: MBR, b: MBR): boolean {
    if (!intersects(a, b)) return false;
    // They touch if intersection area is zero
    // (they share an edge or corner but not interior)
    const interX = Math.max(0, Math.min(a.maxX, b.maxX) - Math.max(a.minX, b.minX));
    const interY = Math.max(0, Math.min(a.maxY, b.maxY) - Math.max(a.minY, b.minY));
    return interX === 0 || interY === 0;
}
 
// Compute the intersection MBR (undefined if disjoint)
function intersection(a: MBR, b: MBR): MBR | undefined {
    const minX = Math.max(a.minX, b.minX);
    const maxX = Math.min(a.maxX, b.maxX);
    const minY = Math.max(a.minY, b.minY);
    const maxY = Math.min(a.maxY, b.maxY);
    
    if (minX > maxX || minY > maxY) {
        return undefined;  // No intersection
    }
    
    return { minX, maxX, minY, maxY };
}

Why Separating Axis Theorem Matters:

The intersects() test works because of the Separating Axis Theorem: two convex shapes do NOT intersect if and only if there exists an axis along which their projections don't overlap.

For axis-aligned rectangles, we only need to check the X and Y axes:

If projections on X-axis don't overlap: disjoint
If projections on Y-axis don't overlap: disjoint
Otherwise: intersecting

This reduces a 2D geometric test to two 1D interval overlap checks, each requiring only 2 comparisons.

Performance Critical:

In a query processing billions of candidates:

intersects() may be called 10 million times
Each call: 4 comparisons, no branching (can be vectorized)
Total: ~10ms on modern CPUs for 10M tests
Same exact geometry test: ~10 seconds (1000x slower)

MBR Metrics for R-tree Decisions

R-tree algorithms make critical decisions based on quantitative MBR metrics. Understanding these metrics reveals why certain insertion and splitting strategies perform better than others.

mbr_metrics.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Area: Total space enclosed by MBR
function area(mbr: MBR): number {
    return (mbr.maxX - mbr.minX) * (mbr.maxY - mbr.minY);
}
 
// Perimeter: Total edge length (prefer square-ish MBRs)
function perimeter(mbr: MBR): number {
    return 2 * ((mbr.maxX - mbr.minX) + (mbr.maxY - mbr.minY));
}
 
// Center point of MBR
function center(mbr: MBR): { x: number; y: number } {
    return {
        x: (mbr.minX + mbr.maxX) / 2,
        y: (mbr.minY + mbr.maxY) / 2
    };
}
 
// Distance between MBR centers
function centerDistance(a: MBR, b: MBR): number {
    const ca = center(a);
    const cb = center(b);
    return Math.sqrt((ca.x - cb.x) ** 2 + (ca.y - cb.y) ** 2);
}
 
// Overlap area between two MBRs
function overlapArea(a: MBR, b: MBR): number {
    const inter = intersection(a, b);
    return inter ? area(inter) : 0;
}
 
// Enlargement: How much must MBR 'original' grow to contain 'newObject'?
// Key metric for choosing insertion path
function enlargement(original: MBR, newObject: MBR): number {
    const combined = unionMBR(original, newObject);
    return area(combined) - area(original);
}
 
// Margin (half-perimeter): Used by R*-tree for split axis selection
function margin(mbr: MBR): number {
    return (mbr.maxX - mbr.minX) + (mbr.maxY - mbr.minY);
}
 
// Aspect ratio: Width/Height ratio (1.0 = perfect square)
function aspectRatio(mbr: MBR): number {
    const width = mbr.maxX - mbr.minX;
    const height = mbr.maxY - mbr.minY;
    if (height === 0) return Infinity;
    return Math.max(width/height, height/width);
}
 
// Dead space: Percentage of MBR not covered by contained objects
function deadSpaceRatio(mbrArea: number, containedObjectsArea: number): number {
    if (mbrArea === 0) return 0;
    return (mbrArea - containedObjectsArea) / mbrArea;
}

How Metrics Drive R-tree Decisions
Decision Point	Primary Metric	Secondary Metric	Goal
Choose subtree for insert	Enlargement	Area, then entries	Minimize MBR growth
Choose split axis (R*)	Margin sum	—	Prefer square groups
Choose split distribution	Overlap	Area sum	Minimize query paths
Choose entries to reinsert	Center distance	—	Remove peripheral entries
Evaluate tree quality	Total overlap	Dead space	Assess query efficiency

Why Perimeter/Margin Matters

MBR Quality and Query Performance

The relationship between MBR quality and query performance is direct and measurable. Poor MBRs cause unnecessary work; excellent MBRs enable aggressive pruning.

High-Quality MBR Characteristics

•Tight fit — MBR closely matches contained geometry
•Low dead space — Most MBR area contains actual data
•Square-ish shape — Balanced width and height
•Low overlap — Minimal intersection with sibling MBRs
•Clustered contents — Children are spatially coherent

Low-Quality MBR Characteristics

•Inflated — Much larger than necessary
•High dead space — Mostly empty area
•Elongated — Very thin or stretched
•Heavy overlap — Many intersections with siblings
•Scattered contents — Children are spatially dispersed

Quantifying the Impact:

Consider a query that should return 100 objects from a dataset of 1 million:

Tree Quality	MBR Overlap	Nodes Examined	I/O Cost	Query Time
Excellent	5%	~20	20 reads	2ms
Good	15%	~60	60 reads	6ms
Poor	40%	~500	500 reads	50ms
Terrible	80%	~10,000	10K reads	1000ms

The difference between a well-organized R-tree and a poorly organized one can be 500x in query performance—and the only difference is MBR quality!

analyze_tree_quality.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
-- PostgreSQL/PostGIS: Analyze R-tree quality for a table
-- This query estimates overlap and dead space
 
WITH index_stats AS (
    SELECT 
        idx.indexrelid::regclass AS index_name,
        pg_relation_size(idx.indexrelid) AS index_size,
        n_distinct,
        correlation
    FROM pg_stat_user_indexes idx
    JOIN pg_stats s ON s.tablename = idx.relname
    WHERE idx.indexrelid::regclass::text LIKE '%gist%'
)
SELECT * FROM index_stats;
 
-- Estimate dead space by comparing MBR area to actual geometry area
SELECT 
    AVG(ST_Area(ST_Envelope(geom)) / NULLIF(ST_Area(geom), 0)) AS avg_mbr_inflation,
    MAX(ST_Area(ST_Envelope(geom)) / NULLIF(ST_Area(geom), 0)) AS max_mbr_inflation
FROM spatial_table
WHERE ST_Area(geom) > 0;
 
-- Check for problematic long/thin geometries
SELECT id, 
       ST_Area(geom) AS area,
       ST_Perimeter(geom) AS perimeter,
       ST_Perimeter(geom)^2 / (4 * 3.14159 * ST_Area(geom)) AS circularity
FROM spatial_table 
WHERE ST_Area(geom) > 0
ORDER BY circularity DESC
LIMIT 10;

The Filter-and-Refine Query Pattern

filter_refine_pattern.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
SPATIAL QUERY: Find all parks that intersect the flood zone
 
┌─────────────────────────────────────────────────────────────────────────┐
│                        PHASE 1: FILTER (Fast)                           │
│                                                                         │
│  Use R-tree index to find all parks whose MBRs intersect               │
│  the flood zone's MBR                                                   │
│                                                                         │
│  Query MBR: [x1, x2] × [y1, y2]                                        │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │                CANDIDATES (MBR intersects)                       │   │
│  │  Park A ✓    Park B ✓    Park C ✓    Park D ✓    Park E ✓      │   │
│  │  (May or may not actually intersect the flood zone polygon)     │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Statistics: 1,000,000 parks → 5,000 candidates (0.5%)                 │
│  Cost: ~5 index page reads + 5,000 MBR comparisons                     │
│  Time: ~5ms                                                             │
└─────────────────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────────────┐
│                      PHASE 2: REFINE (Accurate)                         │
│                                                                         │
│  For each candidate, perform exact geometric intersection test          │
│  using the actual polygon shapes                                        │
│                                                                         │
│  ┌─────────────────────────────────────────────────────────────────┐   │
│  │              EXACT TEST: ST_Intersects(park, flood_zone)        │   │
│  │  Park A: TRUE ✓   (actually intersects)                         │   │
│  │  Park B: FALSE ✗  (MBR overlapped but polygon doesn't)          │   │
│  │  Park C: TRUE ✓   (actually intersects)                         │   │
│  │  Park D: FALSE ✗  (MBR overlapped but polygon doesn't)          │   │
│  │  Park E: TRUE ✓   (actually intersects)                         │   │
│  └─────────────────────────────────────────────────────────────────┘   │
│                                                                         │
│  Statistics: 5,000 candidates → 42 results (0.84% of candidates)       │
│  Cost: 5,000 polygon intersection tests                                 │
│  Time: ~50ms                                                            │
└─────────────────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────────────────┐
│                        FINAL RESULT: 42 parks                           │
│                        Total time: ~55ms                                │
│                                                                         │
│  Without index: 1,000,000 polygon tests × 10µs = 10,000ms (10 sec)     │
│  With index:    5,000 polygon tests = 50ms + 5ms index = 55ms          │
│                                                                         │
│  SPEEDUP: 180x                                                          │
└─────────────────────────────────────────────────────────────────────────┘

False Positives Are Expected

Implications for Query Writing:

Understanding filter-and-refine helps you write faster queries:

-- SLOW: Forces refine on many false positives
SELECT * FROM parks
WHERE ST_Intersects(geom, :complex_flood_zone);

-- FASTER: Explicit two-stage with simplified filter
-- (Sometimes helps optimizer choose better plan)
WITH candidates AS (
    SELECT * FROM parks
    WHERE geom && ST_Envelope(:complex_flood_zone)  -- && = MBR overlap
)
SELECT * FROM candidates
WHERE ST_Intersects(geom, :complex_flood_zone);

Modern query optimizers usually apply this pattern automatically, but for complex queries or non-standard spatial operations, explicit staging can help.

MBR Challenges and Edge Cases

While MBRs are powerful, they have inherent limitations. Understanding these helps you design better schemas and write more robust queries.

Common MBR Challenges

•Diagonal objects — A line from (0,0) to (100,100) has an MBR covering 10,000 square units but actual area of zero. Queries anywhere in this box become false positives.
•Concave shapes — A crescent moon shape has an MBR including lots of empty space where the concavity is. High false positive rate.
•Multi-polygons with spread — An archipelago spanning 1000km has an MBR including thousands of km² of ocean.
•Global geometries — A shipping route from New York to Shanghai has an MBR covering half the planet.
•Anti-meridian crossing — Geometries crossing longitude ±180° require special handling (split or wrap-around MBRs).
•Polar distortion — Near poles, longitude degrees converge; MBRs in lat/lon become increasingly distorted.

mbr_edge_cases.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
-- Problem: Diagonal line creates huge MBR with zero actual area
-- The MBR of this line covers 10,000 square degrees
SELECT ST_Envelope(
    ST_GeomFromText('LINESTRING(0 0, 100 100)', 4326)
);
-- Result: POLYGON((0 0, 100 0, 100 100, 0 100, 0 0))
 
-- Every point query in this 10,000 sq deg area will hit this line's MBR!
 
-- Solution 1: Segment long lines
-- Break the line into smaller segments for tighter MBRs
 
-- Problem: Anti-meridian crossing
-- A line from Japan (140°E) to USA (-120°W) crossing the Pacific
SELECT ST_Envelope(
    ST_GeomFromText('LINESTRING(140 35, -120 35)', 4326)
);
-- WRONG: Creates MBR from -120 to 140 (260 degrees, most of Earth!)
-- Should be: MBR from 140 to 180, then -180 to -120 (100 degrees)
 
-- Solution: Use geography type or split at anti-meridian
SELECT ST_Split(
    ST_GeomFromText('LINESTRING(140 35, -120 35)', 4326),
    ST_GeomFromText('LINESTRING(180 -90, 180 90)', 4326)
);
 
-- Problem: Polar regions
-- At 85°N, one degree of longitude is only ~9.7 km
-- But the MBR treats it the same as at equator (111 km)
-- Result: Massive over-filtering near poles

Strategies for Problematic Geometries

Summary: MBR Mastery

We've thoroughly examined the Minimum Bounding Rectangle—the simple yet powerful abstraction that enables efficient spatial indexing. Let's consolidate the essential insights:

Key Takeaways

•MBRs are axis-aligned rectangles — Defined by just 4 values (min_x, max_x, min_y, max_y), regardless of geometry complexity.
•O(1) intersection tests — MBR overlap checking requires only 4 comparisons, enabling filtering of millions of objects in milliseconds.
•Conservative approximation — MBRs never exclude valid results but may include false positives that refine phase eliminates.
•Quality metrics — Area, overlap, enlargement, and perimeter drive R-tree algorithmic decisions.
•Filter-and-refine pattern — MBRs handle fast elimination; exact geometry tests verify remaining candidates.
•Limitations exist — Diagonal, concave, and global geometries reduce MBR effectiveness; mitigation strategies are available.
•MBR quality = query performance — 500x performance differences possible between well-organized and poorly organized R-trees.

What's Next:

Page Complete

3 / 5