davidmoten/rtree: an immutable Java R-tree with a reactive search API

Immutability is achieved by rebuilding the path to the root

rtree is an in-memory, immutable R-tree for 2D geometry, and the mechanism behind the immutability is the part worth understanding. Insertion and deletion recurse down to the required leaf node and then recurse back up to replace the parent nodes on the way to the root. The guts live in Leaf.java and NonLeaf.java under the internal package. Because the tree never changes in place, a search running against a previous version of the tree is unaffected by a later update, and the README describes the structure as thread-safe with structural sharing, so a large unchanged part of the tree is not copied when one entry changes. For a service where many threads read the index while another writes to it, that removes an entire category of concurrency bug.

Search returns an Observable, and cancelling it stops the traversal

The distinguishing API choice is that search returns an RxJava Observable rather than a list. The README lists the consequences: search is cancelled by unsubscription, all search methods return lazy-evaluated streams, and the library supports backpressure. The backpressure support is what forced the design detail the README is candid about, because a position in the tree has to be kept and returned to later to continue traversal. An immutable stack holding the node and child index of the path nodes solved that, and recursion was abandoned in favour of looping to prevent stack overflow, with the note that Java lacks tail recursion. The practical upshot is that a client that stops consuming stops the work, which matters when a spatial query can match thousands of entries and the caller only wants the first page.

Two split heuristics and a third way to build the tree

The library ships Guttman's quadratic split and the R*-tree heuristics, and the README explains the difference in terms of overlap between nodes, showing side-by-side images of a quadratic split, an R*-tree split and an STR bulk loaded tree over a thousand points. The R*-tree shows little overlap compared with the quadratic split, which the README connects to better search performance, while STR bulk loading has somewhat more overlap than R*-tree, which affects search performance to some extent. STR bulk loading is described as ten times faster for index creation. Both the splitter and the selector are customizable interfaces, so a workload with a particular distribution of shapes can substitute its own, rather than being locked into the defaults.

The complexity profile is honest about where the cost sits

The README states that search is O(log(n)) on average, and that insert and delete are O(n) in the worst case, with balanced delete as a separate feature. That asymmetry is the defining constraint of the design. A tree that is written once and queried many times is the ideal case, because the O(n) worst case on write never dominates. A tree that receives a steady stream of updates is a different story, and the library's own next version drops the reactive API and serialization, which suggests the author is treating this line as a mature, stable artifact rather than the active development surface. On the performance side, the README records the R*-tree performing 900,000 searches per second returning 22 entries from a tree of 38,377 Greek earthquake locations on an i7-920 at 2.67 GHz with maxChildren of 4 and minChildren of 1, and insert at 240,000 entries per second. Those are the author's own figures on specific hardware, not a guarantee for your data.

The API is built around generic types and a geometry hierarchy

Construction goes through static builder methods on the RTree class, and the defaults create a quadratic-split tree.

// create an R-tree using Quadratic split with max
// children per node 4, min children 2 (the threshold
// at which members are redistributed)
RTree<String, Geometry> tree = RTree.create();

Parameters such as minChildren, maxChildren, splitter and selector can be set through the builder.

RTree<String, Geometry> tree = RTree.minChildren(3).maxChildren(6).create();

Geometries are created through a separate builder class, with factory methods for rectangle, point, circle and line, and the README notes that line requires the jts-core dependency. The tree is generic over the value type and the geometry type, so an application that always stores points can declare RTree<String, Point> and get type safety that a Geometry-typed tree would lose.

Adding an item returns a new tree, which is the main source of confusion

The README calls this out with an important note. Because the structure is immutable, calling tree.add(item, geometry) does nothing to the original tree, it returns a new RTree containing the addition, and you must use the result of add. The same applies to delete, which takes the item and its geometry to match.

RTree<T,Geometry> tree = RTree.create();
tree = tree.add(item, Geometries.point(10,20));

The item can also be wrapped explicitly with an entries helper.

tree = tree.add(Entries.entry(item, Geometries.point(10,20));

In a loop, the correct pattern is to reassign the variable on each iteration, and a common bug is to call add without keeping the returned value, which silently discards the insertion. For a large bulk load this is also where the STR path earns its place, since constructing a tree by repeated additions is the slow route the bulk loading algorithm exists to avoid.

R*-tree, bulk loading and the successor project

Switching to the R*-tree variant is a one-liner on the builder, and the README explains that the R*-tree uses a topological splitter on minimal margin, overlap area and area, with a selector combining minimal area increase, minimal overlap and area.

RTree<String, Geometry> tree = RTree.star().maxChildren(6).create();

Beyond the core structure, the project carries the surrounding apparatus of a mature library: JMH benchmarks, a visualizer, serialization using FlatBuffers,, a continuous integration workflow, and Coverity Scan and codecov badges. The repository root is small, with pom.xml, src/, a licence file and a script for generating the site. Status is stated as released to Maven Central, and the artifact coordinates are under the com.github.davidmoten groupId, so the dependency is available from any standard Maven repository rather than needing a JitPack coordinate.

Maven coordinates, Java 1.6 baseline and an Apache-2.0 licence

Adding the library to a project is a standard dependency block, with the version filled in by you.

<dependency>
  <groupId>com.github.davidmoten</groupId>
  <artifactId>rtree</artifactId>
  <version>VERSION_HERE</version>
</dependency>

The README states that the library requires Java 1.6 or later, which is a conservative baseline and a good sign for compatibility with older server-side estates. The licence is Apache-2.0, a permissive licence with an express patent grant, which means it can be used in commercial products without source disclosure obligations. The release history shows 0.12 in 2024-08-25, 0.11 in 2023-06-28 and 0.10 in 2022-05-16, and the last push to the repository was on 2026-09-21, so the code is still being worked on even though a new release has not appeared since 2024.

Editorial conclusion

rtree is a good fit for a Java service holding a spatial index that is mostly written once and read many times, since immutability removes locking and structural sharing keeps memory in check, and the reactive search API lets slow queries be cancelled. It does not fit a workload with constant writes, because the README records insert and delete as O(n) worst case, and it is the wrong tool when a PostGIS or MongoDB instance already stores the geometry, since that database owns the index. Verify first whether the reactive API is what you want at all, since the README points to rtree2 as the next version without a reactive API or serialization, and decide whether you are building on 0.12 or moving to its successor.

Frequently asked questions

Official sources

1. davidmoten/rtree on GitHub
2. Issues
3. License: Apache-2.0
4. README
5. Releases