Skip to main content

Crate scry_index

Crate scry_index 

Source
Expand description

§scry-index

A concurrent sorted key-value map backed by learned index structures.

This crate provides LearnedMap, a sorted map that uses piecewise linear models to predict key positions, achieving O(1) expected lookup time for keys matching the data distribution. A LearnedSet wrapper is also available for key-only use cases.

§Supported key types

Any type implementing Key can be used. Built-in implementations cover:

  • Integer types: u8..u128, i8..i128
  • Byte arrays: [u8; N] for any N (UUIDs, hashes, etc.)
  • Heap-allocated: String, Vec<u8>

For custom key types with a byte representation, the public helpers bytes_to_model_input and bytes_to_exact_ordinal can be used to implement the Key trait.

§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 CAS retry loops on individual slots with no global lock.

§Algorithm

Based on LIPP’s chain method: each node contains a linear model f(key) = slope * key + intercept that maps keys to unique slots in a fixed-size array. Collisions are resolved by creating child nodes (chaining), not by shifting data. This yields zero prediction error and enables fine-grained concurrent access.

§Example

use scry_index::LearnedMap;

let map = LearnedMap::new();
let m = map.pin();

m.insert(42u64, "hello");
m.insert(17u64, "world");

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

For pre-sorted data, LearnedMap::bulk_load builds an optimal tree in one pass:

use scry_index::LearnedMap;

let data: Vec<(u64, &str)> = vec![(1, "a"), (2, "b"), (3, "c")];
let map = LearnedMap::bulk_load(&data).unwrap();
assert_eq!(map.pin().get(&2), Some(&"b"));

§Feature flags

Structs§

Config
Configuration parameters for LearnedMap.
Guard
An epoch guard that keeps the current thread pinned.
Iter
An iterator over the key-value pairs in a learned index in sorted order.
LearnedMap
A sorted key-value map backed by a learned index.
LearnedSet
A sorted set backed by a learned index.
MapRef
A convenience handle that bundles a map reference with an epoch guard.
Range
A range iterator over key-value pairs in a learned index.
SetRef
A convenience handle that bundles a set reference with an epoch guard.

Enums§

Error
Errors that can occur during index operations.

Traits§

Key
A key type usable in a learned index.

Functions§

bytes_to_exact_ordinal
Interpret the first 16 bytes of a byte slice as a big-endian u128, then apply the sign-flip bijection to produce an order-preserving i128.
bytes_to_model_input
Interpret the first 8 bytes of a byte slice as a big-endian u64 -> f64.

Type Aliases§

Result
Result type alias for scry-index operations.