A zero-dependency, cache-aware NavigableSet and NavigableMap engine for Java 21+. v2.0.0 tore out the old custom API in favor of full NavigableSet/Map and SequencedSet/Map compliance — verified against 214,680 Guava testlib permutations and jqwik property tests run at 1M tries. Built for bulk ingestion at scale, without the GC overhead of the JDK's own trees.
GitHub repo link: https://github.com/Chaos-vy/ChaosTree.
A zero-allocation, mechanically sympathetic Java 21 Search Tree engine that mathematically respects the JDK.
Minimum JDK Requirement :0xCAFEBABE 0000 0041 | JDK 21+
| Set | Map |
|---|---|
| Avl Tree Set | Avl Tree Map |
| Red Black Tree Set | Red Black Tree Map |
| B-Tree Set | B-Tree Map |
| B+Tree Set | B+Tree Map |
The engine stands on equal footing with the JDK—and for bulk ingestion, it is 10x+ faster. The custom API surface is strictly minimal. But every custom method unleashes Chaos.
The last 3 API are Nary-Tree Specific.
Read the full Node Structure →
Read Some covered ADR (Architectural Decision Record) →
View N-ary API Time & Space Complexity →
Speed without correctness is useless. ChaosTree perfectly implements subMap(), headMap(),
tailMap(), and descendingMap().
It has been subjected to Google Guava's NavigableSetTestBuilder and NavigableMapTestSuiteBuilder mathematically passes all strict
test permutations including:
| NavigableSetTestBuilder | NavigableMapTestBuilder |
|---|---|
|
|
I have currently 4 set and 4 map which accounts total of
[INFO] Results:
[INFO]
[INFO] Tests run: 214680, Failures: 0, Errors: 0, Skipped: 0
Point to be noted: Every work is done 2x here!. There is no wrapping of set in Map interface. Set work on AbstractBinarySet and AbstractNarySet Engine and Map works on AbstractBinaryMap and AbstractNaryMap Engine.
When I first tested it with Guava it throws many error, but the point was every massive error was simple bug, a line and missing execution.
These test maybe a bottleneck for any library but they do make ensure and highlight many missing cases. A big thanks to Guava testlib <3;
Read the full story of the Testing Journey →
I have currently tested my bulk load testing Dragon feed against TreeMap rigorous testing randomized suite so that it holds true for my by NaryTree and eventually it passed. The test claims are true and further test and bug report are welcome through opening an issue or PR to /test branch
Benchmark environment: Java 21, JMH. Measuring execution time, heap allocation, and GC time for 5,000,000 elements.
| Benchmark (Strategy) | Complexity | Score (ms/op) | Allocated (Bytes/op) | GC Time (ms) |
|---|---|---|---|---|
| B+Tree.dragonFeed (Native, factor(0.8f)) | O(N) | 5.418 | 52,807,339 | 229 |
| B+Tree.bulkLoad (Iterator) | O(N) | 36.649 | 48,498,184 | 36 |
| JDK TreeMap.bulkLoad (SortedMap) | O(N) | 50.638 | 200,000,256 | 740 |
| B+Tree.iterativePut (Standard)(Sequential) | O(N log N) | 217.728 | 86,994,733 | 56 |
| JDK TreeMap.iterativePut (Standard)(sequential) | O(N log N) | 698.918 | 200,002,397 | 347 |
Result: ChaosTree dragon feed is 129x faster than standard JDK insertions, 10x faster
than JDK bulk loading, and uses 74% less JVM heap overhead.
{It depends on factor dev so do read the below article of Dragon feed}
Well, I know this it bit more escalation, but it's the truth. The Dragon feed is fast enough to sweep the complete
array in Milliseconds. Because it uses System.arraycopy().
Read the full Dragon Feed Parameter Sweep →
The running math behind it →
Read the Explicit Benchmark Document →
Tail Latency benchmark in detail →
The reason behind this simple frontend was easy maintenance, because I can maintain this level of frontend.
This library was built through relentless benchmarking and intense mechanical sympathy. If anyone finds further optimizations or edge-case bottlenecks, you are encouraged to open a PR or Issue. I am always ready to make it faster!
⚡ Not built on caffeine, but on Phonk !! ⚡