I'm developing ChaosTree 1.2.0, 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, with a NavigableSet-style API and extensive JUnit 5 coverage.
The B+ tree currently links leaf nodes only in the forward direction with a next pointer. Because of object alignment, the node is padded to 32 bytes by the JVM. Adding a previous pointer may use that otherwise unused space and could make descending iteration more efficient.
Would adding a prev pointer be worthwhile, or is it generally better to implement descending iteration without the extra link? I'm also interested in the trade-offs involving memory usage, cache locality, garbage collection, and iterator performance.
2 Answers
A backward leaf link can make descending iteration straightforward and predictable, especially when iterators need to move repeatedly in reverse. If the pointer fits into existing alignment without increasing the object size, the memory cost may be negligible. Still, measure the actual object layout on the JVMs you support rather than assuming the padding will remain available across all runtimes.
The bigger design question is what you’re optimizing for. Tree nodes create plenty of object references, so allocation rate, indirection, and cache behavior can matter as much as the pointer count. In earlier recursive implementations, temporary objects and wrappers caused a large allocation footprint; removing those allocations gave a much cleaner performance profile. For the B+ tree, compare forward-only traversal with a prev link using realistic workloads, including long-lived processes and descending scans, rather than relying only on isolated lookup timings.
That matches my goal. I’m trying to balance a reusable generic API with mechanical sympathy, so I’ll include GC and longer-running traversal tests in addition to the basic benchmarks.
That’s the main reason I’m considering it: the current layout is already padded, so the extra reference may not increase the node size. I’ll verify the layout and benchmark both iterator designs.