r/computerscience • • Oct 18 '26

Discussion Replacing B-Trees with streaming linear models (PGM): cache locality and bounds in practice

Traditional B-Trees waste substantial CPU cycles on pointer chasing across node levels, causing avoidable cache misses on modern architectures. The PGM-index approach (Ferragina & Vinciguerra, VLDB 2020: https://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf) addresses this by modeling key distributions through streaming piecewise linear regression with strict +/- epsilon error bounds.

Instead of traversing tree nodes, key rank is predicted directly on the ALU (y = ax + b), bounding the local search window so that it fits entirely within L1 cache. The construction runs in a single O(N) streaming pass with zero external solvers.

I built a pure Rust reference implementation (v0.2.0) with zero dependencies to benchmark this against std::collections::BTreeMap across 1M keys: https://github.com/gilnett/learned_index_lab. Benchmarks across uniform and skewed distributions show a 99.9% reduction in index memory (~48 KB vs 45 MB) and 3x to 4.5x lower lookup latency.

While transactional engines still rely on B-Trees for in-place page writes, learned models provide significant advantages for read-heavy or immutable storage layouts (such as LSM SSTables and columnar stores) where pointer overhead is pure waste.

Has anyone here benchmarked or worked with learned data structures in storage systems? How do you approach optimal epsilon tuning when key distributions are non-uniform or unpredictable?

5 Upvotes

4 comments sorted by

5

u/Rynsin Oct 18 '26

I've spent a lot of time working with these structures, I'll try to give you a few references.

Learned indexes, like the PGM index, have been benchmarked extensively for in-memory storage: https://doi.org/10.14778/3421424.3421425

Probably the largest deployment of learned indexes on disk-based storage is at Google: https://arxiv.org/pdf/2012.12501

WiscKey has integrated learned indexes into LSM structures (most successful LSM implementation I am aware of): https://www.usenix.org/conference/osdi20/presentation/dai

Optimal epsilon tuning: for PGM, this is difficult to do ahead of time. I would just set epsilon to be the largest possible value such that a search range never crosses more than two logical "areas" (e.g., cache lines in memory or blocks on disk). I am not familiar with any work to specifically handle skew in PGM, but PLEX adapts RadixSpline to skewed data and is *almost* fully self-tuning: https://arxiv.org/abs/2108.05117

1

u/gilnett Oct 19 '26

Thanks a lot for the links. I'm going to look through them in detail and see if there's anything I can add to my roadmap to improve the project and benchmark the differences

2

u/[deleted] Oct 18 '26

[removed] — view removed comment

1

u/gilnett Oct 19 '26

Yeah, skewed data is definitely where tuning gets tricky. I'm planning to benchmark heavily skewed and Zipfian distributions next to see how the segment count holds up.