A high-performance, cache-aware Java NavigableMap & NavigableSet engineered for the extreme.
ChaosTree is a zero-dependency Java library featuring AVL Trees, Red-Black Trees, B-Trees, and B+ Trees.
Fully compliant with JDK 21 SequencedCollection
Maven
<dependency>
<groupId>io.github.chaos-vy</groupId>
<artifactId>chaos-tree</artifactId>
<version>2.0.1</version>
</dependency>Gradle (Kotlin DSL)
implementation("io.github.chaos-vy:chaos-tree:2.0.1")import chaos.tree.naryMap.BPlusTreeMap;
import java.util.NavigableMap;
public class Main {
public static void main(String[] args) {
// Degree-64 B+Tree, backed by a contiguous leaf-linked list
NavigableMap<Integer, String> map = new BPlusTreeMap<>();
map.put(1, "Chaos");
map.put(2, "Tree");
map.put(3, "Performance");
// Range scans walk the linked leaf layer directly — no tree descent
NavigableMap<Integer, String> subMap = map.subMap(1, true, 3, true);
System.out.println(subMap);
}
}
addFirst()/addLast()are unsupported and fail-fast — these are strictly sorted structures.
Two engines, chosen by workload:
- N-ary family (BTree,BPlusTree) — maximum read throughput and large-scale range scans, zero GC churn.BPlusTreepushes all data into a contiguous doubly-linked (SoA) leaf layer for fast sequential reads.
- Binary family (AVL,RBT) — fast point queries and everyday storage where N-ary's extreme cache optimization isn't needed. Deep dives: Architecture Decision Records · N-ary Tree Architecture · N-ary Complexity Map · Math Behind Bulk Load
ChaosTree is validated through several independent layers:
- Guava Testlib — 214,680 generated test permutations enforcing exact NavigableMap/NavigableSetsemantics againstjava.util.
- Jqwik property-based fuzzing — hundreds of thousands of randomized structural invariant checks against java.util.TreeMapas a source of truth. (N-ary's degree-32 node floor meant Guava's suite never exercised it directly, so a dedicated invariant-verification API was built to cover that gap.)
- Randomized differential testing against reference collections.
- White-box structural validation of B-Tree/B+Tree node invariants.
- Contract tests — fail-fast ConcurrentModificationExceptionsemantics, exact size counting, strict null-guards on custom comparators. The Testing Journey
All results: JMH, 3 forks, i5-13450HX (16c) unless noted otherwise. Full methodology and raw logs are linked per section.
Java 21.0.12,
-Xms4g -Xmx4g -XX:+UseParallelGC -XX:+AlwaysPreTouch, 5 measurement iterations.
Sequential key order
dragonFeed is 168x faster than JDK sequential insertion, 14.9x faster than the JDK's own bulk loader, and allocates 71% less heap.
Random key order (bulk-loading bypasses don't apply here)
Random insertion is the honest worst case — cache-locality gains collapse for both structures. ChaosTree still comes out 2.07x faster with 3.2x less allocation.
Factor is a non-factor here — every value sits within error bars of the others. Cost is dominated by per-entry comparator/split overhead, not node packing. (Contrast with importFlatMatrix above, where factor is a first-order effect.)
Rule of thumb: 0.75f (default) leaves headroom for future writes. 1.0f is for read-only/snapshot data — fastest and smallest, but the first write after load forces a split.
JMH
-bm sample, n = 1K→10M, degree 64,-Xms4g -Xmx4g -XX:+UseParallelGC -XX:+AlwaysPreTouch. Sample mode keeps every invocation, so GC pauses and rebalance cascades show up at p1.00 instead of averaging out.
Over a 10,000x increase in data size, TreeMap's worst case grows ~145x (899 µs → 130 ms) — confirmed against -Xlog:gc as real stop-the-world pauses. ChaosTree's B+Tree and B-Tree grow ~1.3–1.5x, with zero logged GC pauses at any size, on any fork.
Root cause: packed-array nodes (ChaosTree) vs. one heap-allocated Entry object per key (TreeMap) — fewer, larger allocations beat millions of small ones under churn.
JMH
avgt,-prof perfnorm,entrySet()iteration, 1K–1M elements.
BPlusTreeMap overtakes a flat ArrayList past ~280K elements, despite executing ~4.6x more instructions per element — the win is memory locality, not compute. At 1M elements, LLC cache-miss ratio is 38% for BPlusTreeMap vs. 86.8% for ArrayList (nearly every access round-trips to main memory), with ~21x fewer LLC accesses per element and sustained IPC of 3.72 vs. 0.88.
TreeMap is 5–10x slower than both at every size — its parent/left/right pointer traversal touches far more scattered memory per step.
Takeaway: below ~280K entries, a flat array wins on pure iteration. Past that, BPlusTreeMap's cache-friendly leaf layout takes over, and the gap widens with scale.
More reports: Insert-heavy · Read-heavy · Mixed workload · The Amortization Quirk
Full docs, ADRs, and benchmark methodology live on the Documentation Hub.
- Bugs & features: GitHub Issues
- Discussion: GitHub Discussions Pull requests and well-scoped issue reports for compatibility, correctness, and maintenance work are welcome.