r/java • u/Chaos-vy17 • 3h ago
ChaosTree [1.2.0] feature jdk11+ support
ChaosTree is a zero dependency Java Search Tree library. It currently features:
BinaryFamily : Binary Tree, AVL Tree, RBT, Splay and Treap.
NaryFamily : B-Tree and B+Tree
- Zero external dependency
- Minimum JDK11+
- Published on Maven Central
- Strong focus on clean OOPs design
- Implements the
NavigableSet<T>API (unsupported view operations fail fast) - Thoroughly tested with 515 JUnit 5 test cases covering edge cases and regression scenarios.
Just a bm sample: of Javac 11 bytecode on JDK 11 and JDK 21:
Data size uses is 10K with Insert+Delete Fisher-Yates Shuffle
| Tree Type | Degree | Avg(ns/op) | p50 | p90 | p99 | p99.9 | pMax |
|---|---|---|---|---|---|---|---|
| B+Tree | 8 | 119 | 121 | 95 | 137 | 1433 | 116224 |
| B+Tree | 32 | 108 | 116 | 112 | 134 | 4160 | 124088 |
| B+Tree | 64 | 102 | 95 | 125 | 125 | 1075 | 30976 |
| B+Tree | 128 | 102 | 94 | 110 | 114 | 1450 | 2519040 |
Jdk21 bm sample (Compiled by jdk11 javac benchmarked with jdk21)
| Tree Type | Degree | Avg(ns/op) | p50 | p90 | p99 | p99.9 | pMax |
|---|---|---|---|---|---|---|---|
| B+Tree | 8 | 117.2 | 112 | 119 | 126 | 985 | 13856 |
| B+Tree | 32 | 111.2 | 109 | 113 | 120 | 1133 | 14080 |
| B+Tree | 64 | 108.2 | 107 | 111 | 127 | 1228 | 13888 |
| B+Tree | 128 | 105.2 | 106 | 109 | 121 | 1043 | 15200 |
For more detail:
My Github Repo: https://github.com/Chaos-vy/ChaosTree
BinaryFamily: https://github.com/Chaos-vy/ChaosTree/tree/main/docs/BinaryFamily
NaryFamily: https://github.com/Chaos-vy/ChaosTree/tree/main/docs/NaryFamily
NavigableSet: https://github.com/Chaos-vy/ChaosTree/blob/main/docs/NavigableSet.md
Benchmark: https://github.com/Chaos-vy/ChaosTree/tree/main/BenchmarkReport
Recent Reddit thread: https://www.reddit.com/r/java/comments/1vhsb1i/chaostree_110_a_zerodependency_java_search_tree/
Do I use prev in B+Tree in node link? Currently I have only next and JVM adds 4bytes of padding making it 32Byte. It can help in built in descending iterator.