Show HN: ChaosTree – A zero-dependency Java tree library (AVL,RBT,B-Tree,B+Tree)
The short version
- ChaosTree is a zero-dependency Java Sorted Set/Map library built around multiple tree implementations.
- It provides implementations of: - AVL Tree - Red-Black Tree - B-Tree - B+Tree I have not made my custom API as it implements NavigableSet, NavigableMap…
- Tail latency behavior is not shown here because it get's truncated into a simple text which made the dat read wrong: https://chaos-vy.github.io/ChaosTree/utils/JMH-Report.html I…
- GitHub: https://github.com/Chaos-vy/ChaosTree https://chaos-vy.github.io/ChaosTree/ I'd especially like feedback on the API design, implementation choices, benchmark methodology.
- I am currently trying to truncate useless and complex branches for performnace tuning.
The story
What is ChaosTree?
ChaosTree is a zero-dependency Java Sorted Set/Map library built around multiple tree implementations.
It provides implementations of: - AVL Tree - Red-Black Tree - B-Tree - B+Tree
I have not made my custom API as it implements NavigableSet, NavigableMap, SequencedSet and SequencedMap. My Custome API are: - buildFromSorted(Iterator> it, float factor) - importFlatMatrix(Object[][] blast, float factor) - Object[][] exportFlatMatrix()
I started ChaosTree because I wanted to explore how far I could learn DS structure, It started as frst release of 7 tree of Set type with Custome API, As i got engrossed into it I moved to Map, During phase of switching from Set to Map there was drastic change and knowledge upgrade where I pushed my Tree limit from jdk11+ support to jdk21+ where paid close attention to dependency-free and memory layout, allocation,JVM behavior, and real-world performance.
Some of the things I experimented with: - Different node layouts and metadata footprints - CRTP/F-bounded polymorphism for tree implementations - Parent-pointer vs parentless nodes - Array-based N-ary tree nodes - B-Tree/B+Tree degree selection - JMH benchmarking and JFR profiling - Differential/randomized testing against java.util.TreeMap/TreeSet
After this rough and tough It also passes these test:
-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.
Tail latency behavior is not shown here because it get's truncated into a simple text which made the dat read wrong:https://chaos-vy.github.io/ChaosTree/utils/JMH-Report.html I have also ran benchmark with official JDK TreeMapUpdate to my N-ary tree.
GitHub: https://github.com/Chaos-vy/ChaosTree https://chaos-vy.github.io/ChaosTree/
I'd especially like feedback on the API design, implementation choices, benchmark methodology. I am currently trying to truncate useless and complex branches for performnace tuning.
Comments URL: https://news.ycombinator.com/item?id=49694404
Points: 6
# Comments: 4
Powered by Gab AI
The Story At A Glance
Reading this article now — analysis appears below
💡 AI analysis provides alternative perspectives on current events
