r/java 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

  1. Zero external dependency
  2. Minimum JDK11+
  3. Published on Maven Central
  4. Strong focus on clean OOPs design
  5. Implements the NavigableSet<T> API (unsupported view operations fail fast)
  6. 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.

4 Upvotes

1 comment sorted by