Bulk Loading an R-tree Versus Inserting One by One

Two trees over the same data can differ in query cost by a factor of several, purely because of the order the data went in. The difference is one constructor argument, and almost nobody chooses it deliberately.

Prerequisites

Conceptual minimum

An R-tree groups nearby bounding boxes into parent nodes, recursively. Query cost depends almost entirely on how much the sibling nodes overlap: a query descending into a node must also descend into every sibling whose box it intersects, so overlapping nodes multiply the work.

Incremental insertion places each item into whichever existing node grows least, splitting when a node overflows. It cannot see what is coming, so early items dictate a structure that later items must fit into, and the result accumulates overlap. It has one real advantage: the tree accepts further insertions cheaply.

Bulk loading sees everything at once. The standard algorithm sorts items spatially — typically by a space-filling curve or by alternating coordinate sorts — and packs them into full nodes bottom-up. The result has minimal overlap and near-perfect fill, and it is built in roughly the time of a sort rather than of a million insertions.

The trade-off is therefore not about speed on one axis: bulk loading is faster to build and faster to query. What it gives up is mutability.

Bulk loading and incremental insertion compared on the properties that matter A grid of four properties against the two strategies. Build time is roughly that of a sort for bulk loading and substantially longer for insertion, because each insertion descends the tree. Node overlap is minimal for bulk loading and accumulates for insertion, which is what drives query cost. Node fill is near complete for bulk loading and typically around seventy percent for insertion. Mutability is the one advantage of insertion: the tree accepts further items cheaply, while a bulk-loaded tree must be rebuilt. Bulk loading wins on three of four properties Bulk load Insert one by one Build time about a sort substantially longer Node overlap minimal accumulates Node fill near complete around 70% Accepts inserts no, rebuild yes, cheaply The last row is the only reason to choose insertion, and it matters only when the index genuinely changes after construction.
Because bulk loading wins on both build and query, the decision reduces entirely to whether the index must be mutable.

Runnable solution

python 
from __future__ import annotations

import logging
import time
from dataclasses import dataclass

import numpy as np
from rtree import index as rtree_index

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.index.rtree")


@dataclass(frozen=True)
class Measurement:
    strategy: str
    build_seconds: float
    query_seconds: float
    candidates_per_query: float


def build_inserted(boxes: np.ndarray) -> rtree_index.Index:
    """One insertion at a time: the tree cannot see what is coming."""
    tree = rtree_index.Index()
    for i, (minx, miny, maxx, maxy) in enumerate(boxes):
        tree.insert(i, (minx, miny, maxx, maxy))
    return tree


def build_bulk(boxes: np.ndarray) -> rtree_index.Index:
    """Bulk load from a generator: the library packs nodes bottom-up.

    The generator form is what triggers bulk loading; passing the same data
    through repeated insert() calls does NOT, however it is batched.
    """
    def stream():
        for i, (minx, miny, maxx, maxy) in enumerate(boxes):
            yield (i, (minx, miny, maxx, maxy), None)
    return rtree_index.Index(stream())


def measure(boxes: np.ndarray, queries: np.ndarray,
            builder, label: str) -> Measurement:
    started = time.perf_counter()
    tree = builder(boxes)
    build_seconds = time.perf_counter() - started

    started = time.perf_counter()
    total_candidates = 0
    for minx, miny, maxx, maxy in queries:
        hits = list(tree.intersection((minx, miny, maxx, maxy)))
        total_candidates += len(hits)
    query_seconds = time.perf_counter() - started

    result = Measurement(label, build_seconds, query_seconds,
                         total_candidates / max(1, len(queries)))
    logger.info("%-12s build %6.2fs  query %6.2fs  %6.1f candidate(s)/query",
                label, build_seconds, query_seconds, result.candidates_per_query)
    return result


def random_boxes(n: int, seed: int = 0) -> np.ndarray:
    rng = np.random.default_rng(seed)
    # Clustered, like real OSM data: a dense core plus a sparse surround.
    centres = np.vstack([rng.normal(0, 500, size=(int(n * 0.8), 2)),
                         rng.uniform(-20_000, 20_000, size=(n - int(n * 0.8), 2))])
    sizes = np.abs(rng.normal(20, 10, size=(n, 2))) + 1
    return np.hstack([centres - sizes / 2, centres + sizes / 2])


if __name__ == "__main__":
    boxes = random_boxes(200_000)
    queries = random_boxes(2_000, seed=1)
    inserted = measure(boxes, queries, build_inserted, "inserted")
    bulk = measure(boxes, queries, build_bulk, "bulk-loaded")
    logger.info("bulk loading: %.1fx faster to build, %.1fx faster to query",
                inserted.build_seconds / bulk.build_seconds,
                inserted.query_seconds / bulk.query_seconds)

Step-by-step walkthrough

  1. Use the generator form to bulk load. Passing an iterable of items to the index constructor is what triggers the packing algorithm; calling insert in a loop never does, however the loop is batched.
  2. Precompute the bounding boxes. Computing them inside the build loop measures geometry work rather than index construction, which makes the comparison meaningless.
  3. Measure queries, not just build time. The build difference is the headline and the query difference is the one that matters, because a build happens once and queries happen forever.
  4. Count candidates as well as time. The candidate count is the structural measurement: a tree returning more candidates for identical queries has more node overlap, which is the mechanism behind the timing difference.
  5. Test on clustered data. Uniformly distributed boxes understate the difference substantially, because overlap accumulates fastest exactly where density varies — which is what OSM looks like.
  6. Keep the query set fixed. The two trees must answer identical queries, or the comparison measures the queries rather than the trees.
  7. Decide on mutability, not on speed. Since bulk loading wins both timings, the only question is whether the index must accept later insertions.
Typical build and query times for two hundred thousand clustered boxes Four measurements comparing the two strategies on the same clustered dataset. Incremental insertion takes substantially longer to build because each item descends the tree and may trigger a split. Bulk loading builds in roughly the time of a sort. Querying the incrementally built tree is noticeably slower because sibling node overlap forces the search into more branches. Querying the bulk-loaded tree is faster for the same queries and returns fewer candidates for identical search boxes. Same data, same queries, two build strategies Insert: build baseline Bulk load: build about 4.5x faster Insert: 2000 queries query baseline Bulk load: 2000 queries about 2.4x faster On uniformly distributed data the query gap narrows considerably, which is why benchmarks on synthetic uniform boxes are misleading.
Exact ratios vary with clustering and library, but the direction does not: bulk loading wins both measurements.
Why insertion order changes the tree, and what that costs a query Three panels. Under insertion, each item joins whichever existing node grows least, so the structure is fixed by whatever arrived first and later items are squeezed into it, leaving sibling boxes overlapping. Under bulk loading, the whole dataset is sorted spatially and packed bottom-up into full nodes, so siblings are compact and rarely overlap. The query consequence is that an overlapping tree forces a search into several branches at every level, multiplying the nodes visited. Same items, different structure, different query cost Grown by insertion Each item joins the best fit Early arrivals fix the shape Later ones squeeze in Siblings overlap Fill around 70 percent Packed in bulk Whole dataset sorted first Nodes filled bottom-up Siblings compact Overlap minimal Fill near complete Query effect Overlap splits the descent Several branches per level Compounds with depth More candidates returned Same results, more work The third panel is why the candidate count, not the wall-clock time, is the measurement that proves the mechanism.
Nothing reorganises an incrementally built tree afterwards, so the overlap it accumulates is permanent.

Verification

  • Both trees return identical results. For each query, the sorted result sets must match; a difference means a bug, not a strategy effect.
  • The candidate count differs. If both trees return the same number of candidates, the bulk load did not happen — check that the generator form was used.
  • Clustered data shows a larger gap. Re-run on uniform boxes and confirm the difference narrows, which validates that overlap is the mechanism.
  • Build time scales as expected. Doubling the data should roughly double the bulk build and more than double the insertion build.
  • The bulk tree rejects insertion. Confirm your library’s behaviour, since some silently degrade to insertion afterwards.

Common errors and fixes

Symptom Root cause One-line fix
No difference between strategies Insert loop used for both Pass a generator to the constructor to bulk load
Build times dominated by geometry Bounding boxes computed in the loop Precompute boxes before timing
Difference smaller than expected Uniform synthetic data Benchmark on clustered data resembling real extracts
Bulk tree slow after updates Insertions made into a packed tree Rebuild rather than inserting into a bulk-loaded index
Results differ between trees Different item identifiers or boxes Assert identical inputs before comparing
Memory spikes during bulk load Whole dataset materialised Stream the generator rather than building a list
Index rebuilt on every query batch Rebuild placed inside the query loop Build once and reuse across the workload

Specification reference

Bulk loading algorithms for R-trees, such as sort-tile-recursive packing, sort the input spatially and fill nodes to capacity bottom-up, producing a tree with minimal node overlap and near-complete fill. Incremental insertion instead chooses the subtree requiring least enlargement and splits on overflow, which yields lower fill and accumulating overlap. See the libspatialindex documentation for the packing implementation used by the Python bindings.

Frequently Asked Questions

Is bulk loading always faster to query?

For a static dataset, effectively always, because it produces a tree with less sibling overlap and better node fill. The margin depends on how clustered the data is: on uniformly distributed boxes the two are close, and on the heavily clustered distributions real OSM extracts produce the gap is substantial. Since it is also faster to build, there is no speed argument for insertion at all.

When should I insert one at a time?

When the index genuinely has to accept items after construction and rebuilding is impractical — a long-running service maintaining an index over a changing dataset, for instance. That is a real requirement and the only one that justifies the cost. If the data changes in batches, rebuilding the whole index per batch is usually still faster than inserting into an existing one, and it keeps the query performance.

Why does node overlap matter so much?

Because a query must descend into every node whose bounding box it intersects. Where siblings overlap, one query descends into several branches instead of one, and that multiplication compounds at every level of the tree. A tree built by insertion accumulates overlap because early items fix a structure that later items must be squeezed into, and nothing ever reorganises it.

Does the same reasoning apply to other spatial indexes?

The principle does: an index built with knowledge of the whole dataset can be organised better than one grown incrementally. The magnitude varies. A uniform grid, as in Choosing a Grid Cell Size for OSM Spatial Hashing, is insensitive to insertion order by construction, so the question does not arise there.

Up one level: Spatial Indexing for OSM Extracts.