Module split 

Node-split strategies — the type parameter that governs tree shape.

Mirrors boost/geometry/index/parameters.hpp and the index/detail/rtree/{linear,quadratic,rstar}/redistribute_elements.hpp family. When a node overflows, the split strategy decides how to partition its children into two nodes. Boost exposes this as a template parameter; the port uses a SplitParameters trait carried on Rtree<T, Params>.

Four strategies ship: AsymmetricRStarSplit (the crate::Rtree default), symmetric RStarSplit, Quadratic (Boost’s textbook split), and Linear (cheaper inserts, looser trees).

Choosing parameters

Start with Rtree<T>. Its default was selected from uniform and clustered workloads covering bulk loading, insertion, range queries, and nearest-neighbour queries. A different data distribution, payload size, construction method, or query mix can change the best tree shape, so customize the parameters only after benchmarking a representative workload.

The default is AsymmetricRStarSplit<6, 2, 12, 4, 4, 4>. The parameters are positional:

Parameter	Used by	General trade-off
BRANCH_MAX	Rtree::insert	Smaller branches evaluate fewer sibling bounds; larger branches make a shallower tree.
BRANCH_MIN	Branch splitting after insertion	Higher values keep branches denser; lower values give the split more freedom.
LEAF_MAX	Rtree::insert	Smaller leaves test fewer values when reached; larger leaves reduce tree structure.
LEAF_MIN	Leaf splitting after insertion	Controls the minimum fill of each new leaf.
PACKED_BRANCH_MAX	FromIterator	Controls branch fanout in the initial bulk-packed tree.
PACKED_LEAF_MAX	FromIterator	Controls how many values an initial packed leaf may contain.

The packed capacities affect only the layout initially produced by FromIterator. Later insertions use the first four insertion capacities; existing packed nodes are not rebuilt. A zero packed capacity means “inherit the corresponding insertion maximum”, so a four-parameter AsymmetricRStarSplit retains the traditional behavior.

use geometry_rtree::{AsymmetricRStarSplit, Bounds, Rtree};

// Spell out the measured default so each positional parameter is visible.
type Parameters = AsymmetricRStarSplit<
    6,  // insertion branch maximum
    2,  // insertion branch minimum
    12, // insertion leaf maximum
    4,  // insertion leaf minimum
    4,  // bulk-packed branch maximum
    4,  // bulk-packed leaf maximum
>;

let tree: Rtree<Bounds, Parameters> = [
    Bounds::point([0.0, 0.0]),
    Bounds::point([1.0, 1.0]),
]
.into_iter()
.collect();
assert_eq!(tree.len(), 2);

Tuning procedure

• For a read-mostly tree built with collect, tune the two packed maxima first.
• For a frequently modified tree, tune the insertion maxima and minima first.
• Smaller maxima can reduce the work of nearest-neighbour searches, but create more nodes and may increase tree height.
• Larger maxima can reduce structural and traversal overhead, but make each visited branch or leaf more expensive to scan.
• Measure construction together with representative calls to query, nearest, or nearest_iter. Improving one workload can regress another.

The built-in insertion strategies expect both minimums to be non-zero and to leave room for two groups when a node of MAX + 1 entries splits: 2 * BRANCH_MIN <= BRANCH_MAX + 1 and 2 * LEAF_MIN <= LEAF_MAX + 1. Bulk leaf capacity must be non-zero and bulk branch capacity must be at least two; bulk loading checks those two constraints.

Why these defaults

The retained defaults were measured on 2026-07-13 with iai-callgrind, 50,000 two-dimensional points, 100 queries, and k = 8. Candidate configurations were evaluated across inserted and bulk-built trees, uniform and clustered distributions, construction cost, bounded and streaming kNN, and range queries. The insertion capacities 6/2/12/4 and packed capacities 4/4 were retained as the best balanced measured configuration across that matrix. This evidence supports the general default; it is not a guarantee for every workload.

Structs

AsymmetricQuadratic

Quadratic split with independent branch and leaf capacities.

AsymmetricRStarSplit

R*-split selection with independent insertion and bulk capacities.

Linear

Linear split — cheap inserts, looser trees.

Quadratic

Quadratic split — Boost’s textbook default.

RStarSplit

R*-split selection with one capacity for branches and leaves.

Traits

SplitParameters

How a full node is partitioned when it overflows.