Struct LearnedMap 

pub struct LearnedMap<K: Key, V> { /* private fields */ }

A sorted key-value map backed by a learned index.

Uses piecewise linear models to predict key positions, achieving O(1) expected lookup time for keys matching the data distribution.

When to use

Best suited for read-heavy, concurrent workloads with sorted keys (time-series queries, lookup tables, analytics indexes). Point lookups are faster than BTreeMap; writes are competitive for sequential and append-only patterns. For random-key insert-heavy workloads, prefer bulk_load over one-by-one insertion.

Concurrency

All operations take &self and are safe to call from multiple threads. Reads are lock-free (atomic loads under an epoch guard). Writes use compare-and-swap retry loops on individual slots. No global lock.

Example

use scry_index::LearnedMap;

let map = LearnedMap::new();
let guard = map.guard();

map.insert(42u64, "hello", &guard);
map.insert(17, "world", &guard);

assert_eq!(map.get(&42, &guard), Some(&"hello"));
assert_eq!(map.get(&99, &guard), None);
assert_eq!(map.len(), 2);

Implementations

impl<K: Key, V: Clone + Send + Sync> LearnedMap<K, V>

pub fn new() -> Self

Create a new empty learned map with default configuration.

pub fn with_config(config: Config) -> Self

Create a new empty learned map with the given configuration.

pub fn bulk_load(pairs: &[(K, V)]) -> Result<Self>

Create a learned map from sorted key-value pairs.

Faster than inserting one-by-one because it builds the tree structure in one pass using FMCD model fitting.

Errors

Returns an error if pairs is empty or not sorted by key.

pub fn bulk_load_with_config(pairs: &[(K, V)], config: Config) -> Result<Self>

Create a learned map from sorted key-value pairs with configuration.

Errors

Returns an error if pairs is empty or not sorted by key.

pub fn bulk_load_dedup(pairs: &[(K, V)]) -> Result<Self>

Create a learned map from sorted key-value pairs, deduplicating keys.

When duplicate keys are present, the last value for each key is kept, matching the semantics of BTreeMap::from_iter. The input must be sorted by key in ascending order but may contain duplicates.

This is equivalent to deduplicating and then calling bulk_load.

Errors

Returns an error if pairs is empty (after dedup) or not sorted by key.

pub fn bulk_load_dedup_with_config( pairs: &[(K, V)], config: Config, ) -> Result<Self>

Create a learned map from sorted key-value pairs with dedup and config.

See bulk_load_dedup for semantics.

Errors

Returns an error if pairs is empty (after dedup) or not sorted by key.

pub fn guard(&self) -> Guard

Acquire an epoch guard for use with operations on this map.

The guard pins the current thread to an epoch, preventing any concurrently retired memory from being reclaimed while the guard is held. Keep guards short-lived.

pub fn pin(&self) -> MapRef<'_, K, V>

Pin the current epoch and return a MapRef convenience handle.

This is equivalent to guard() + passing the guard to every method, but more ergonomic for sequences of operations.

pub fn get<'g>(&self, key: &K, guard: &'g Guard) -> Option<&'g V>

Look up a key, returning a reference to the value if found.

The returned reference is valid for the lifetime of the guard.

pub fn insert(&self, key: K, value: V, guard: &Guard) -> bool

Insert a key-value pair. Returns true if the key was newly inserted, false if an existing key’s value was updated.

When auto_rebuild is enabled, the insert path tracks descent depth and triggers a localized subtree rebuild if the depth exceeds the configured threshold. No global lock is required.

If a concurrent root rebuild replaces the tree, the insert detects the change and retries against the new root. A was_new flag tracks whether the key was newly inserted across retries so len is incremented exactly once.

pub fn remove(&self, key: &K, guard: &Guard) -> bool

Remove a key. Returns true if the key was present and removed.

If a concurrent root rebuild replaces the tree, the remove detects the change and retries against the new root. A was_removed flag tracks whether the key was successfully removed across retries so len is decremented exactly once.

pub fn get_or_insert<'g>(&self, key: K, value: V, guard: &'g Guard) -> &'g V

Atomically get an existing value or insert a new one.

If the key already exists, returns a reference to the existing value without modifying it. If the key is absent, inserts the key-value pair and returns a reference to the newly inserted value.

This is atomic with respect to concurrent operations. There is no TOCTOU race between checking and inserting.

pub fn get_or_insert_with<'g>( &self, key: K, f: impl FnOnce() -> V, guard: &'g Guard, ) -> &'g V

Atomically get an existing value or insert a computed one.

Like get_or_insert, but the value is lazily computed by f only if the key is absent during the initial lookup. Under concurrent inserts, f may be called even if another thread inserts the same key first; in that case the computed value is discarded and the existing value is returned.

pub fn contains_key(&self, key: &K, guard: &Guard) -> bool

Check whether the map contains a key.

pub fn len(&self) -> usize

Return the approximate number of key-value pairs in the map.

Uses a relaxed atomic load internally. Under concurrent inserts or removes the returned value may be slightly stale. It is not linearizable with respect to other operations. For an exact count, call iter and count the entries, which gives a consistent snapshot under the epoch guard.

pub fn is_empty(&self) -> bool

Return true if the map contains no entries.

Subject to the same relaxed-atomic staleness as len.

pub fn iter<'g>(&self, guard: &'g Guard) -> Iter<'g, K, V>

Iterate over all key-value pairs in sorted order.

The returned references are valid for the lifetime of the guard.

pub fn iter_sorted(&self, guard: &Guard) -> Vec<(K, V)>

Collect all key-value pairs in sorted order (cloned).

Performs a full traversal and clones all entries.

pub fn range<'g, R: RangeBounds<K>>( &self, range: R, guard: &'g Guard, ) -> Range<'g, K, V>

Return an iterator over key-value pairs within the given range.

The iterator yields entries in ascending key order. Uses model-guided seek for efficient initialization when a start bound is provided.

Accepts any range syntax: a..b, a..=b, a.., ..b, ..=b, ...

pub fn first_key_value<'g>(&self, guard: &'g Guard) -> Option<(&'g K, &'g V)>

Return the first (minimum) key-value pair in the map.

pub fn last_key_value<'g>(&self, guard: &'g Guard) -> Option<(&'g K, &'g V)>

Return the last (maximum) key-value pair in the map.

pub fn range_count<R: RangeBounds<K>>(&self, range: R, guard: &Guard) -> usize

Count the number of entries within the given range.

pub fn allocated_bytes(&self, guard: &Guard) -> usize

Estimate the total heap memory allocated by this map, in bytes.

Walks the entire tree and sums up node structs, slot arrays, and per-entry allocations. This is an approximation: it does not account for allocator overhead, alignment padding, or epoch-deferred garbage.

pub fn max_depth(&self, guard: &Guard) -> usize

Return the maximum depth of the tree.

A well-fit model keeps depth low (typically 1-3 after bulk load).

pub fn rebuild(&self, guard: &Guard)

Rebuild the tree from scratch using bulk load.

Collects all key-value pairs, sorts them, and rebuilds with optimal FMCD model fitting. This compacts the tree and restores O(1) lookups after many incremental inserts.

The root is frozen (tagged) during the rebuild so concurrent inserts spin-wait and then retry against the new root. In-flight inserts that loaded the old root before the freeze detect the change via post-insert validation in LearnedMap::insert and retry automatically.

pub fn drain(&self, guard: &Guard) -> Vec<(K, V)>

Remove all entries from the map and return them as a sorted Vec.

Uses the same freeze protocol as rebuild to coordinate with concurrent inserts. After draining, the map has a fresh root identical to one created by new.

Returns an empty Vec if the map is already empty or if the freeze CAS fails (another thread is rebuilding concurrently).

pub fn clear(&self, guard: &Guard)

Remove all entries from the map, resetting it to an empty state.

Uses the same freeze protocol as rebuild to coordinate with concurrent inserts. After clearing, the map has a fresh root identical to one created by new.

Trait Implementations

impl<K: Key, V> Debug for LearnedMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: Key, V: Clone + Send + Sync> Default for LearnedMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Key, V> Drop for LearnedMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K: Key, V: Clone + Send + Sync> Extend<(K, V)> for LearnedMap<K, V>

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: Key, V: Clone + Send + Sync> FromIterator<(K, V)> for LearnedMap<K, V>

Note: from_iter inserts elements one at a time into an empty map. For pre-sorted data, LearnedMap::bulk_load is significantly faster because it fits an optimal model in a single pass rather than building incrementally with conflict resolution.

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K: Key, V: Send + Sync> Send for LearnedMap<K, V>

impl<K: Key, V: Send + Sync> Sync for LearnedMap<K, V>