scry-index - project details

Rust's BTreeMap is the standard sorted container. It works well for general use, but at scale two costs dominate: O(log n) comparisons per lookup, and cache misses from pointer-chasing through tree nodes.

Learned indexes replace tree traversal with a math function. If you know the distribution of your keys, a linear model can predict the position of any key in one step. Collisions are handled by small child nodes, but for well-distributed data the tree stays shallow and most lookups resolve in a single prediction.

Each node stores a linear model f(key) = slope * key + intercept fitted using the FMCD algorithm from the SALI paper (SIGMOD 2024). The model maps each key to a unique slot in a fixed-size array. When two keys collide on the same slot, a child node is created to hold both. No data is shifted, no rebalancing required.

Keys always land at their model-predicted slot. There is no prediction error and no correction scan. Conflicts create children, which can themselves have children, but the FMCD fitting keeps the tree shallow. When a subtree grows beyond a depth threshold, it is rebuilt inline by the thread that triggered it.

• Phase 1 Single-threaded prototype. FMCD model fitting, lookup, insert, iterator. All methods take &mut self. Validate the algorithm works in Rust.
• Phase 2 Concurrent. Atomic slots, lock-free reads, CAS writes, epoch-based reclamation via crossbeam. All methods take &self.
• Phase 3 O(n) in-order iteration (DFS is naturally sorted). Range queries: range(start..end), first_key_value(), last_key_value(). Model-guided seek for O(depth) range initialization.
• Phase 4 Depth-triggered localized subtree rebuilds. The inserting thread rebuilds the degraded subtree inline via CAS-swap. Replaced the Phase 2.5 RwLock with fully lock-free operation.
• Phase 5 Production hardening. True FMCD candidate slopes. Adaptive root sizing. Key generalization (String, Vec<u8>, [u8; N]). Entry API. Tombstone compaction. Serde support. Write safety under concurrent rebuilds.

use scry_index::LearnedMap;

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

m.insert(42u64, "the answer");
m.insert(1, "first");
m.insert(100, "last");

assert_eq!(m.get(&42), Some(&"the answer"));

// sorted iteration, range queries
for (k, v) in m.range(1u64..50) {
    println!("{k}: {v}");
}

// atomic check-and-insert
let val = m.get_or_insert(42, "default");
assert_eq!(val, &"the answer"); // existing value, not "default"

For pre-sorted data, bulk_load builds the tree in one pass with optimal model fitting. bulk_load_dedup handles duplicates (keeps the last value per key, matching BTreeMap::from_iter semantics).

// bulk load from sorted data
let data: Vec<(u64, &str)> = vec![(1, "a"), (2, "b"), (3, "c")];
let map = LearnedMap::bulk_load(&data).unwrap();

// supports String, Vec<u8>, [u8; N], and all integer types
let string_map: LearnedMap<String, u64> = LearnedMap::new();

Random-key inserts are slower (~4-6x). When keys arrive in random order, the model cannot predict well and creates deep conflict chains. Use bulk_load when you have sorted data available.

Bulk load is slower than BTreeMap. The FMCD model fitting step adds overhead. The payoff comes at read time.

Memory overhead is higher. Each node allocates arrays with expansion factor headroom (default 2x) to leave space for future inserts. The allocated_bytes() API lets you monitor this at runtime.

Best fit: read-heavy concurrent workloads with sorted or semi-sorted keys. Time-series ingestion, lookup tables, analytics indexes. For write-heavy random workloads with no concurrency requirement, BTreeMap is the simpler choice.