ChaosTree 1.2.0 is a zero-dependency Java search-tree library targeting JDK 11 and newer. It includes binary trees, AVL trees, red-black trees, splay trees, treaps, B-trees, and B+ trees. The library implements NavigableSet, with unsupported view operations failing fast, and has been tested with more than 500 JUnit 5 cases covering edge conditions and regressions.
The implementation is focused on clean object-oriented design and mechanical sympathy. Benchmarks using JDK 11-compiled bytecode on JDK 11 and JDK 21 show B+ tree operations averaging roughly 100–120 nanoseconds per operation across several node degrees, using shuffled insertion and deletion workloads with 10,000 elements.
In the B+ tree, each linked leaf currently stores only a next pointer. Because of object layout, the node ends up with additional padding and occupies 32 bytes. Would adding a previous pointer be worthwhile to support a more efficient built-in descending iterator, or would the extra reference and maintenance cost usually outweigh the benefit?
2 Answers
I would probably add the previous link if descending iteration is an important part of the API. B+ trees are especially well suited to ordered scans, and having links in both directions keeps reverse traversal predictable. Still, benchmark workloads that never iterate backward will not benefit, so it may be better as an optional design choice or a separate implementation variant. The key measurements are forward versus reverse iteration speed, update cost, memory footprint, and behavior under long-lived workloads.
A previous pointer can make descending iteration straightforward and avoid repeatedly walking down from the root or maintaining a more complicated traversal stack. The trade-off is an extra reference in every leaf, plus more pointer updates during splits, merges, and rebalancing. Since the node already has alignment padding, the memory cost may be smaller than expected, but it is still worth measuring object size and iterator throughput rather than assuming the padding is free.
The project began as a learning exercise, but I am now optimizing for mechanical sympathy in Java. Earlier versions created a large allocation rate because recursive AVL and treap operations produced temporary objects and wrappers. Version 1.2.0 removes most of that overhead. I am also using JMH allocation and performance profilers to compare cache behavior and garbage-collection effects.
I have also experimented with several tree variants, primitive-specialized implementations, visualizers, and an R-tree. The difficult part is not only getting the algorithms correct, but making them robust and fast enough to justify the added complexity. Comparing implementations with the same workloads should make the trade-offs much clearer.