Show HN: Pgm-extra-rs – High-performance learned index structures for Rust (github.com)

Pgm-extra-rs is a new Rust library implementing the PGM-index (learned piecewise linear models) with multiple variants, drop-in Set/Map replacements for BTreeSet/BTreeMap, and a dynamic variant supporting insertions/deletions. It targets read-heavy, large sorted datasets and embedded/WASM contexts (no-std). The author exposes single-level, multi-level recursive, and dynamic indexes, optional parallel construction (Rayon), serde support, and SIMD-enabled linear search (left to LLVM auto-vectorization). The crate is MIT-licensed and available on crates.io. Technically, the index trades space for query speed via epsilon (ε): query time is O(log n / log ε), space is O(n / ε), and construction is O(n). Typical ε choices (32–64 default) balance speed and memory; smaller ε yields more segments and faster cache-critical lookups. Benchmarks on Apple M1 Pro (1M random u64 keys) show PGM variants using ~2.7–3.2x less memory than BTreeSet and delivering 1.3–1.7x faster point queries versus BTreeSet (binary search is faster but uses no extra index). Range scans with PGM+scan were ~1.4x faster. Practical implications: pgm-extra-rs is a compact, high-throughput alternative to B-trees for sorted-key workloads where lower memory and faster point/range queries matter, while dynamic use is supported albeit with rebuilds on mutation.