B-Epsilon Trees vs. Write-Optimized B+Trees for High-Ingestion Secondary Indexes

Benchmarking internal node message buffers (Bε-trees) against WiredTiger-style B+Trees and RocksDB LSM trees on 50/50 read-write secondary index workloads.

1. Bridging the Point-Write vs. Range-Scan Trade-off

In a classical B+Tree with 16 KiB leaf pages, inserting a single 64-byte secondary index entry dirty-marks an entire 16 KiB page, yielding a worst-case write amplification of 256. LSM-trees batch writes sequentially but pay multi-level merge iterator overhead on short range scans. Bε-trees allocate a fraction (`1 - ε`) of every internal node as a message buffer, flushing batched updates down a single child branch only when the buffer fills.

Index Structure (500GB dataset, 32GB RAM)Random Upserts/sShort Range Scan (100 keys)Disk WAF
B+Tree (16 KiB page, group commit)28,400 / s112 µs (p99)38.2
LSM-Tree (Leveled, 10 bits/key Bloom)164,000 / s340 µs (p99)6.4
Bε-Tree (256 KiB node, ε = 0.5)131,000 / s185 µs (p99)7.9
← Older Note (2024-10-12)Profiling Hardware TLB Misses with perf stat and 2MiB Hugetlbfs Backing PoolsNewer Note (2025-01-09) →Measuring PCIe Peer-to-Peer DMA Throughput Between NVMe Drives and RDMA NICs

← Back to all notes · View full chronological archive (24)