nordisk/znippy-zoomies

stree / stree32 — guide

Class: guide · Function: stree. The how-to. Chosen design in stree-design.md; measured numbers + reproduce commands in benchmarks.md.

Pick a width

• Keys fit in 32 bits and aren't OSM/skade ids → stree32::STree32 (denser, faster once RAM-bound).
• Keys are i64 (OSM node ids, skade snapshot ids) → stree::STree64.

Never reach for a generic STree<T> — it does not exist by design (see stree-reasoning.md).

In-RAM lookup

use znippy_zoomies::stree32::STree32;

let mut keys: Vec<u32> = load_keys();
keys.sort_unstable();                 // the tree requires sorted input
let tree = STree32::new(&keys);       // build once (expensive), query many (cheap)

assert_eq!(tree.find_exact(missing), None);
if let Some(idx) = tree.find_exact(q) { /* keys[idx] == q */ }

Batched queries (hide the miss latency)

A single find_exact is latency-bound. For a bulk of queries, use the pipelined batch — P queries in flight, each prefetching its next hop:

// P is the pipeline depth; 16 pegs every core at 100%.
let hits = tree.batch_stream::<16>(&queries);   // Vec<Option<usize>>, one per query

batch_prefetch::<P> and batch_stream::<P> return identical results to a serial find_exact loop (a tested invariant) — the batch is purely a throughput win.

mmap-backed (the on-disk column is the leaf layer)

When keys already live in a sorted on-disk column, build only the internal nodes and let the file be the leaves:

use znippy_zoomies::stree32::STree32Mmap;

// default stride 4 = pure u32 SoA column:
let tree = STree32Mmap::open(path)?;
let hit = tree.find_exact(q);
let hits = tree.lookup_batch_pipeline::<16>(&queries);

// AoS records whose leading 4 bytes are the LE u32 key:
let tree = STree32Mmap::new_with_stride(path, record_size)?;

Verify + bench

cargo test  -p znippy-zoomies --release stree32_bench -- --nocapture           # correctness + in-cache micro-bench
cargo test  -p znippy-zoomies --release stree32_bench_ram -- --ignored --nocapture   # 512 MB RAM-bound (heavy)

Expect ~9× over binary_search in cache, ~21× RAM-bound at 512 MB (full table in benchmarks.md).