boostree

A fast in-memory R*-tree index over points or axis-aligned bounding boxes, backed by Boost.Geometry via pybind11.

Two surfaces:

1. Native API (boostree.RTree) — a clean, batched, numpy-first interface designed for new code.
2. rtree.index drop-in (boostree.index.Index, boostree.index.Property) — method-for-method compatible with the subset of the PyPI rtree package.

On that subset it's ~6× faster per query and ~4× faster to build than libspatialindex (which the PyPI rtree package wraps), plus:

Native API

import boostree
import numpy as np

# Build from points or boxes
tree = boostree.RTree.from_points(pts)               # zero-volume boxes
tree = boostree.RTree.from_points(pts, ids=eids)     # with ids
tree = boostree.RTree.from_boxes(mins, maxs)         # explicit boxes
tree = boostree.RTree.from_pairs(items, dim=3)       # iterable form

# A point-only tree: entries hold no extent, so it uses less memory
tree = boostree.RTree.from_points(pts, storage="point")

# k-nearest, rows sorted by ascending distance; exactly tied candidates
# are picked and ordered by coordinates and then by id, so the answer
# never depends on the order the tree was built in; optional per-query
# radius cap (radius<=0 disables)
ids, dists = tree.knn(queries, k=8)
ids, dists = tree.knn(queries, k=8, radius=0.5)
ids, dists = tree.knn(queries, k=8, radius=per_query_radii)

# k-nearest under elliptical (Mahalanobis) metrics: transforms maps
# world coordinates into each metric class's frame; radius is then in
# metric-frame units (radius=1.0 keeps hits inside the ellipse)
ids, dists = tree.knn(queries, k=8, transforms=tmats, class_ids=cids)

# Box queries: pass maxs alongside queries (Euclidean only)
ids, dists = tree.knn(qmins, k=4, maxs=qmaxs)

# Bbox-vs-bbox intersection (ids flat, counts per query)
ids, counts = tree.intersect(qmins, qmaxs)

# Existence-only variant: (n,) bool, stops at the first hit per query
hit = tree.intersect_any(qmins, qmaxs)

# All queries are batched — no separate single-query method.  For one
# query, just pass a length-1 array
ids, dists = tree.knn(np.array([[0.5, 0.5, 0.5]]), k=4)

# Mutation — batched and id-based, no need to remember the original
# coordinates the way rtree.index requires
tree.delete(ids_to_drop)                             # by id-set
tree.delete_in(qmins, qmaxs)                         # by bbox-range
tree.update(ids, new_points)                         # upsert by id
tree.add(new_ids, new_points)                        # incremental insert

# copy.copy / copy.deepcopy both produce fully independent trees
import copy
tree2 = copy.deepcopy(tree)

# Pickle round-trips through (ids, mins, maxs), or (ids, points) under
# point storage — independent of host architecture / endianness /
# pointer width
import pickle
blob = pickle.dumps(tree)
tree3 = pickle.loads(blob)

# Or the same arrays directly, e.g. for HDF5 or numpy.savez
ids_arr, mins_arr, maxs_arr = tree.dump()             # box storage
ids_arr, pts_arr = point_tree.dump()                  # point storage

The native API differs from rtree.index in several ways:

• Output shape is fixed (n, k) for both ids and distances, rows sorted by ascending distance and padded with -1 / +inf. No variable-length flat returns.
• Elliptical metrics are first-class: knn(..., transforms=..., class_ids=...) runs an exact best-first search under per-query Mahalanobis metrics — no oversample-and-re-rank workarounds.
• radius does not mutate the caller's array (the rtree-compat shim does, matching libspatialindex; the native API doesn't because callers can read dists instead).
• radius <= 0 disables the cap (matches libspatialindex), so the zero-radius sentinel works without surprises.
• Property is gone. dim is inferred from your input; the rtree capacities are not user-tunable in Boost's rstar.
• Mutation is id-based and batched. rtree.index.delete(id, coords) needs the original bbox alongside the id and removes one entry per call; tree.delete(ids) accepts an array and removes every match in one pass. There's no update in rtree.index at all — callers hand-roll delete + insert; tree.update(ids, points) does it for you with upsert semantics.

rtree.index drop-in

Existing code that uses from rtree.index import Index, Property can switch to boostree without source changes:

import boostree
boostree.install_rtree_compat()        # one-line shim into sys.modules

# from this point onwards the rtree imports resolve to boostree:
from rtree.index import Index, Property
tree = Index((ids, mins, maxs), properties=Property(dimension=3))
nidxs, counts, dists = tree.nearest_v(qpts, qpts, num_results=8)
ids, counts = tree.intersection_v(qmins, qmaxs)

Covered:

• Bulk batched paths — bulk-load (numpy (ids, mins, maxs) or (id, bbox, obj)-iterable), nearest_v with max_dists / return_max_dists, intersection_v.
• Single-query rtree methods — intersection(bbox, objects=False), nearest(point, num_results=1), insert(id, coords), and delete(eid, coordinates=None) (boostree ignores the coordinates argument since it can look the id up directly; rtree requires it).
• copy.copy / copy.deepcopy and pickle — work too, unlike upstream rtree.index where copy aliases the C++ index handle and pickle isn't supported at all.

Plus four boostree-only batched paths exposed on the same Index:

idx.delete_v(ids)                    # bulk delete by id
idx.delete_range_v(pmins, pmaxs)     # bulk delete by bbox intersection
idx.update_v(ids, pmins, pmaxs)      # bulk upsert
idx.intersection_any_v(pmins, pmaxs) # existence test, early exit

Notably not supported by either surface:

• dimension other than 2, 3, or 4
• persistent / disk-backed indexes
• user objects carried through queries (objects=True)
• arbitrary point types other than float64
• nearest_v(strict=False)'s overflow-on-equidistant-ties behaviour (we always return exactly num_results ids, padded with -1)

Property.index_capacity / leaf_capacity are accepted for API compatibility but ignored — Boost picks its own internal layout.

Install

pip install boostree

Wheels are published for Linux (x86_64, aarch64), macOS (x86_64, arm64), and Windows (AMD64) on CPython 3.10–3.14. No Boost or compiler is required at install time — the minimal Boost.Geometry header subset is vendored in the source distribution.

To build from source you only need a C++17 compiler and CMake ≥ 3.18:

pip install .

To rebuild the vendored Boost subset against a newer Boost release, install bcp (e.g. apt install libboost-tools-dev) and run:

python scripts/vendor_boost.py --boost-root /path/to/boost_x_y_z

To build against system Boost instead of the vendored subset, pass -DBOOSTREE_USE_SYSTEM_BOOST=ON to CMake.

OpenMP is auto-detected at build time and used to parallelise batched queries (knn, nearest_v, intersect, intersection_v) across threads — typically ~10× speedup at 16 threads on aircraft-class workloads. macOS clang ships without OpenMP, so the macOS wheels run serial (still faster than libspatialindex).

Development

Source is formatted via black (Python) and clang-format (C++) — a project-local .clang-format and [tool.black] block in pyproject.toml pin the styles.

To run both formatters at once:

pip install pre-commit
pre-commit run --all-files

Or hand-run:

black boostree/ tests/ scripts/
clang-format -i src/*.cc benchmarks/*.cc

Threading

The C++ extension declares itself compatible with PEP 703 free-threaded CPython (py::mod_gil_not_used()), and the batched query methods (nearest_v / intersection_v / knn / intersect) release the GIL so they parallelise across Python threads even on the regular GIL build.

Each tree carries a std::shared_mutex: read methods take a shared lock, mutators (insert_point, delete_*, update_*) take an exclusive lock. Concurrent reads run in parallel; reads block during a write and vice versa. No external synchronisation is required, even on free-threaded CPython.

Benchmarks

On 161 368 wall faces × 1 811 835 query points × k=8:

Changes in 0.3

• CPython 3.14 is supported and gets published wheels.
• Point storage. RTree.from_points(pts, storage="point") holds a bare point per entry rather than a zero-volume box, giving the same answers in less memory. Entries hold no extent, so update() refuses a maxs.
• Order-independent ties. Candidates at exactly equal distances are selected and ordered by coordinates and then by id, so knn no longer depends on the order the tree was built in.
• Non-finite coordinates are refused. A stored NaN read as an exact hit from anywhere along that axis; inserting one now raises.
• Breaking: the keyword naming the far corner of a query or update box is now maxs throughout the native API, matching from_boxes / intersect / delete_in. RTree.knn(..., query_max=) and RTree.update(..., query_max=) are now maxs=. The boostree.index drop-in is unaffected.

License

Boost Software License 1.0 (matches Boost.Geometry).