Java library ChaosTree offers zero-dependency sorted tree implementations with bulk-load APIs and cache-locality optimizations

ChaosTree introduces a Java library that provides multiple sorted tree implementations without external dependencies. The library targets engineers who need high-performance sorted collections while maintaining compatibility with JDK interfaces like NavigableSet, NavigableMap, SequencedSet, and SequencedMap. This compatibility ensures that existing code using standard Java collections can adopt ChaosTree with minimal changes, reducing migration costs for projects that require specialized tree structures.

The library distinguishes itself with bulk-load APIs that allow engineers to construct N-ary trees from sorted data. These APIs provide control over node occupancy through a configurable factor, which must fall within the range of 0.5 to 1.0. This feature enables optimization of tree structures for specific workloads, particularly those involving large datasets or frequent range scans. However, the bulk-load functionality only works on empty trees, requiring engineers to plan their data loading strategy accordingly.

ChaosTree emphasizes cache locality in its N-ary engine, packing data into pre-allocated arrays to improve CPU cache hit rates. The library claims nearly 40% reduction in memory load stalls during large range scans, which could benefit applications with heavy read workloads. The B+Tree implementation further optimizes range scans by maintaining a contiguous double-linked list at the leaf level. These optimizations come with trade-offs, as the library does not support addFirst() or addLast() operations, which may limit its applicability in certain use cases.

The library undergoes extensive validation through multiple testing layers, including Guava Testlib compatibility testing, property-based testing with jqwik, and randomized differential testing against reference collections. Structural tests inspect internal tree representations to validate node occupancy, ordering, topology, and balancing invariants. While this rigorous testing approach increases confidence in the library's correctness, engineers should note that the library requires JDK 21 or later, which may limit adoption in environments constrained to older Java versions.