Degree Scaling — Random Read @ 1M nodes (ns/op) SWEET SPOT
t=32 wins on latency. LLC misses rise after t=64 as nodes outgrow L1. Diminishing returns plateau after t=100.
Range Scan — B+ Tree vs B-Tree @ 1M, degree=32 (ns/op)
B+ Tree: 334K ns/op vs B-Tree: 474K ns/op. Leaf-chain traversal gives B+ Tree a ~29% advantage on range scans.
Insert/Delete @ 1M nodes — Degree Scaling (ns/op)
Higher degrees generally reduced insert/delete latency in this benchmark. More keys per node = fewer splits = less structural overhead per operation.
Concurrent Benchmark @ degree=32 — Search (ns/op)
Search scales gracefully to 5M nodes. Both engines suffer monitor lock tax on writes (~16,000+ ns/op).
GC Allocation Rate — B+ Tree Construction (bytes/op) across degree & size
t=32 reduces GC pressure by ~7x vs t=4 at 5M nodes. Higher degree = fewer node allocations = less GC churn.
LLC Cache Misses — Degree Scaling @ 1M nodes (B+ Tree Random Read)
t=16 achieves minimum LLC misses (4.2). Beyond t=64, LLC misses climb as nodes exceed L1/L2 capacity.
Zipfian Search — All Trees @ 100k nodes (ns/op) SEARCH
RBT leads at 96 ns/op. Splay (297 ns/op) is 3× slower at 100k — additional restructuring overhead dominates under Zipfian skew
Zipfian Search — Latency Scaling 1k→100k (ns/op)
All trees grow sub-linearly. Splay diverges sharply from 1k→100k as its latency increases more rapidly at larger scales
Insert/Delete @ 1k–100k (ns/op) WRITE COST
Java TreeSet wins insert/delete due to JIT optimizations. Among chaos trees, BST is fastest, Splay is a massive outlier.
Clone Construction @ 1k–100k (ms/op)
At 100k nodes all chaos clones land within ~0.005 ms of each other. Chaos trees are faster or on-par with Java TreeSet.
GC Allocation — Clone (bytes/op) across tree types & sizes
chaos BST uses 40% less memory than TreeSet per cloned node; balanced chaos trees use 20% less.