ChaosTree
A zero-dependency Java library of sorted Set and Map implementations, including AVL trees, red-black trees, B-trees and B+ trees, built for cache locality and compliant with JDK 21's SequencedCollection interfaces.
ChaosTree implements Java's NavigableMap and NavigableSet as AVL trees, red-black trees, B-trees and B+ trees, choosing between two engines depending on the workload: an N-ary family (BTree, BPlusTree) for high read throughput and large range scans, packing nodes into pre-allocated arrays for cache locality, and a binary family (AVL, RBT) for fast point queries and everyday storage.
Bulk loading is O(N) through buildFromSorted and importFlatMatrix, with a tunable fill factor. The library is fully compliant with JDK 21's SequencedCollection, SequencedSet and SequencedMap interfaces, though addFirst() and addLast() are unsupported and fail fast, since these are strictly sorted structures. It supports serialization and cloning, with O(N) bulk-load restoration on deserialize.
Correctness is checked against more than 214,000 generated Guava Testlib cases for exact TreeMap/TreeSet semantics, plus property-based fuzzing with Jqwik against java.util.TreeMap as a reference. It has no dependencies and is available through Maven or Gradle.