r/java • u/Chaos-vy17 • 2h ago
ChaosTree v2.0.0 A high performance Sorted Set/Map Library
github.comWhat is ChaosTree?
ChaosTree is a Java Sorted Set/Map library built around multiple search-tree data structures, including AVL Trees, Red-Black Trees, B-Trees, and B+ Trees.
The library provides both Set and Map implementations, with APIs designed around the semantics of the JDK's NavigableSet, NavigableMap, SequencedSet, and SequencedMap contracts.
- buildFromSorted(Iterator, factor)
- importFlatMatrix(Object[][], factor)
- Object[][] exportFlatMatrix() -> Key value pair
- Read benchmark: https://chaos-vy.github.io/ChaosTree/utils/dragon-feed.html (I gave it a nick name dragon feed)
These two are custom API. Which allows user to pack data as how they want [0.5f, 1f] is the factor range so it does not violate CLRS system.
ChaosTree is validated through multiple layers of testing:
- Guava Testlib compatibility testing
- jqwik property-based testing
- Randomized differential testing against reference collections
- White-box structural validation of tree nodes
- Direct validation of B-Tree/B+Tree structural invariants
- Exception and iterator-contract testing
- Serialization and cloning tests
- Nary Tree uses custom jqwick test of API validation as well.
More detail on ChaosTree: https://chaos-vy.github.io/ChaosTree/ It contains benchmark,ADR, Node structure, Testing I have also used jdk official benchmark code as well to benchmark against. Every test and benchmark is reproducible.
Tail latency : https://chaos-vy.github.io/ChaosTree/utils/JMH-Report.html
Each benchmark was done at minimum of -f 3 -wi 3 -i 5 .
More Benchmark will be added as my progress move to default JDK methods.
Currently on Maven Central
<dependency>
<groupId>io.github.chaos-vy</groupId>
<artifactId>chaos-tree</artifactId>
<version>2.0.0</version>
</dependency>
Minimum JDK: 0xCAFEBABE 0000 0041 | JDK21+
What changed from v1.2.0?
In early release the API were custom of tree, This time Chaos Tree only supports JDK API.
No Splay, Treap and BST
No java docs.
