Crate pgm_extra

Crate pgm_extra 

Source
Expand description

§PGM-Extra

A Rust implementation of the PGM-index, a learned index structure that uses piecewise linear models to approximate the cumulative distribution function of sorted data for fast lookups.

§Quick Start

For most use cases, use Set or Map which own their data:

use pgm_extra::{Set, Map};

// Set (like BTreeSet)
let set: Set<u64> = (0..10000).collect();
assert!(set.contains(&5000));

// Map (like BTreeMap)
let map: Map<u64, &str> = vec![(1, "one"), (2, "two")].into_iter().collect();
assert_eq!(map.get(&1), Some(&"one"));

// Works with strings too!
let words: Set<&str> = vec!["apple", "banana", "cherry"].into_iter().collect();
assert!(words.contains(&"banana"));

§Index Types

  • Set: BTreeSet-like set optimized for read-heavy workloads
  • Map: BTreeMap-like map optimized for read-heavy workloads

§External-keys indices (for advanced use cases)

  • Static: Multi-level recursive index (also available as index::external::Static)
  • OneLevel: Single-level index for smaller datasets
  • Cached: Multi-level with hot-key cache for repeated lookups
  • Dynamic: Mutable index with insert/delete (requires std feature)

§Features

  • std (default): Enables Dynamic index and other std-only features
  • parallel: Enables parallel index construction
  • simd: Enables SIMD-accelerated search routines
  • serde: Enables serialization/deserialization

§Performance

The PGM-index provides O(log n / log epsilon) query time with significantly smaller space overhead compared to traditional B-trees. Construction is O(n).

Re-exports§

pub use collections::map::Map;
pub use collections::set::Set;
pub use error::Error;
pub use index::external::Cached as CachedIndex;
pub use index::external::OneLevel as OneLevelIndex;
pub use index::external::Static as StaticIndex;
pub use index::external::Cached;
pub use index::external::OneLevel;
pub use index::external::Static;
pub use index::owned::Dynamic;
pub use index::owned::Dynamic as DynamicIndex;

Modules§

collections
error
index
PGM-Index implementations.
util