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/s | Short Range Scan (100 keys) | Disk WAF |
|---|---|---|---|
| B+Tree (16 KiB page, group commit) | 28,400 / s | 112 µs (p99) | 38.2 |
| LSM-Tree (Leveled, 10 bits/key Bloom) | 164,000 / s | 340 µs (p99) | 6.4 |
| Bε-Tree (256 KiB node, ε = 0.5) | 131,000 / s | 185 µs (p99) | 7.9 |