ChaosTreeMapReadBenchmark — Read-Heavy Benchmark

1. Setup

Comparing java.util.TreeMap against ChaosTree's BTreeMap and BPlusTreeMap under heavy read workloads.

java -jar ct-benchmark/target/benchmarks.jar ChaosTreeMapReadBenchmark \
    -p size=100000 -p seed=42 -wi 10 -w 500ms -i 10 -r 500ms -tu ns -rf text -rff ReadHeavy100K.txt

java -jar ct-benchmark/target/benchmarks.jar ChaosTreeMapReadBenchmark \
    -p size=10000  -p seed=42 -wi 10 -w 500ms -i 10 -r 500ms -tu ns -rf text -rff ReadHeavy10K.txt

Caveats:

Measurements are in strictly nanoseconds (ns/op), average time (avgt), shown as score ± error (JMH 99.9% confidence interval).
10 warmup + 10 measurement iterations of 500 ms each (30 samples per cell: Cnt = 30). GC profiler (-prof gc) is not attached in this run.
Two sizes run: 10,000 and 100,000 entries — same seed (42) across both, ensuring parity in cache scaling boundaries.
preFill=true is implicitly forced for all methods here, as read benchmarks inherently require querying an already populated data structure.
Lower is better.

2. ceilingKey()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	104.113 ± 1.840	103.749 ± 1.486	111.992 ± 7.934
BTreeMap	106.284 ± 0.749	105.011 ± 0.488	110.674 ± 0.312
BPlusTreeMap	104.784 ± 1.120	104.149 ± 0.418	105.350 ± 0.794

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	220.758 ± 3.533	161.532 ± 1.141	216.032 ± 27.020
BTreeMap	191.204 ± 1.651	188.098 ± 1.616	180.164 ± 3.480
BPlusTreeMap	175.192 ± 4.114	181.387 ± 2.267	166.751 ± 1.904

3. containsKey()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	103.693 ± 0.266	105.311 ± 0.556	104.376 ± 1.993
BTreeMap	99.343 ± 0.739	98.972 ± 0.465	99.300 ± 0.335
BPlusTreeMap	101.579 ± 0.871	101.659 ± 4.012	100.650 ± 0.989

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	225.389 ± 4.334	186.226 ± 21.074	230.997 ± 4.349
BTreeMap	175.474 ± 1.009	178.824 ± 2.406	175.594 ± 1.970
BPlusTreeMap	183.437 ± 2.568	184.217 ± 1.137	176.353 ± 3.762

4. firstAndLast()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	24.881 ± 0.120	28.065 ± 0.213	48.467 ± 0.391
BTreeMap	9.741 ± 0.065	10.583 ± 0.119	34.974 ± 0.100
BPlusTreeMap	9.700 ± 0.036	10.486 ± 0.055	32.903 ± 0.238

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	37.425 ± 1.403	44.945 ± 0.475	65.829 ± 0.322
BTreeMap	9.698 ± 0.043	10.449 ± 0.028	37.960 ± 0.072
BPlusTreeMap	9.669 ± 0.033	10.461 ± 0.036	38.685 ± 0.069

5. floorKey()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	105.560 ± 1.109	104.442 ± 0.784	106.569 ± 2.703
BTreeMap	106.352 ± 0.253	106.776 ± 0.354	129.717 ± 0.446
BPlusTreeMap	104.392 ± 1.305	104.136 ± 0.355	108.605 ± 1.117

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	232.312 ± 3.469	165.451 ± 10.086	209.476 ± 12.999
BTreeMap	186.308 ± 0.829	192.617 ± 3.633	197.923 ± 7.215
BPlusTreeMap	173.365 ± 3.861	182.239 ± 3.475	171.394 ± 1.805

6. get()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	106.753 ± 1.950	107.809 ± 0.376	101.441 ± 0.590
BTreeMap	100.100 ± 0.604	99.493 ± 0.653	107.979 ± 0.254
BPlusTreeMap	104.221 ± 0.301	101.777 ± 0.539	105.642 ± 1.169

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	258.974 ± 2.397	204.973 ± 27.733	257.960 ± 16.230
BTreeMap	183.570 ± 4.975	184.059 ± 4.579	183.807 ± 5.338
BPlusTreeMap	190.062 ± 6.158	190.536 ± 8.955	187.670 ± 4.837

7. getMiss()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	36.773 ± 0.273	41.598 ± 0.263	12.878 ± 0.308
BTreeMap	32.558 ± 0.119	30.118 ± 0.091	19.869 ± 1.320
BPlusTreeMap	29.850 ± 0.164	29.271 ± 0.146	15.760 ± 0.159

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	56.364 ± 3.225	52.246 ± 2.438	18.573 ± 0.420
BTreeMap	39.104 ± 0.336	40.498 ± 0.825	23.594 ± 0.484
BPlusTreeMap	41.954 ± 0.470	42.300 ± 1.581	23.054 ± 1.376

8. iterate()

10k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	3.921 ± 0.031	4.421 ± 0.029	4.383 ± 0.038
BTreeMap	7.495 ± 0.033	7.469 ± 0.155	9.387 ± 1.266
BPlusTreeMap	1.596 ± 0.023	1.576 ± 0.037	3.579 ± 0.042

100k

TreeType	TreeMap	descendingMap	subMap
JavaTreeMap	4.370 ± 0.101	6.637 ± 1.016	4.700 ± 0.092
BTreeMap	6.047 ± 1.471	4.380 ± 1.458	8.565 ± 0.252
BPlusTreeMap	1.522 ± 0.007	1.555 ± 0.013	3.574 ± 0.041