scry_index/lib.rs
1//! # scry-index
2//!
3//! A concurrent sorted key-value map backed by learned index structures.
4//!
5//! This crate provides [`LearnedMap`], a sorted map that uses piecewise linear
6//! models to predict key positions, achieving O(1) expected lookup time for
7//! keys matching the data distribution. A [`LearnedSet`] wrapper is also
8//! available for key-only use cases.
9//!
10//! # Supported key types
11//!
12//! Any type implementing [`Key`] can be used. Built-in implementations cover:
13//!
14//! - Integer types: `u8`..`u128`, `i8`..`i128`
15//! - Byte arrays: `[u8; N]` for any `N` (UUIDs, hashes, etc.)
16//! - Heap-allocated: `String`, `Vec<u8>`
17//!
18//! For custom key types with a byte representation, the public helpers
19//! [`bytes_to_model_input`] and [`bytes_to_exact_ordinal`] can be used to
20//! implement the [`Key`] trait.
21//!
22//! # Concurrency
23//!
24//! All operations take `&self` and are safe to call from multiple threads.
25//! Reads are lock-free (atomic loads under an epoch guard). Writes use
26//! CAS retry loops on individual slots with no global lock.
27//!
28//! # Algorithm
29//!
30//! Based on LIPP's chain method: each node contains a linear model
31//! `f(key) = slope * key + intercept` that maps keys to unique slots in a
32//! fixed-size array. Collisions are resolved by creating child nodes
33//! (chaining), not by shifting data. This yields zero prediction error and
34//! enables fine-grained concurrent access.
35//!
36//! # Example
37//!
38//! ```
39//! use scry_index::LearnedMap;
40//!
41//! let map = LearnedMap::new();
42//! let m = map.pin();
43//!
44//! m.insert(42u64, "hello");
45//! m.insert(17u64, "world");
46//!
47//! assert_eq!(m.get(&42), Some(&"hello"));
48//! assert_eq!(m.get(&99), None);
49//! assert_eq!(m.len(), 2);
50//! ```
51//!
52//! For pre-sorted data, [`LearnedMap::bulk_load`] builds an optimal tree in
53//! one pass:
54//!
55//! ```
56//! use scry_index::LearnedMap;
57//!
58//! let data: Vec<(u64, &str)> = vec![(1, "a"), (2, "b"), (3, "c")];
59//! let map = LearnedMap::bulk_load(&data).unwrap();
60//! assert_eq!(map.pin().get(&2), Some(&"b"));
61//! ```
62//!
63//! # Feature flags
64//!
65//! - **`serde`**: Enables `Serialize`/`Deserialize` for [`LearnedMap`],
66//! [`LearnedSet`], [`Config`], and [`Error`].
67
68mod build;
69mod config;
70mod error;
71mod insert;
72mod iter;
73mod key;
74mod lookup;
75mod map;
76mod model;
77mod node;
78mod rebuild;
79mod remove;
80mod set;
81
82pub use config::Config;
83pub use error::{Error, Result};
84pub use iter::{Iter, Range};
85pub use key::{bytes_to_exact_ordinal, bytes_to_model_input, Key};
86pub use map::{Guard, LearnedMap, MapRef};
87pub use set::{LearnedSet, SetRef};