Struct ConstTree 

pub struct ConstTree<K: Key, const V: usize, H: WriteHook<K> = NoHook> { /* private fields */ }

A tree with fixed-size keys and values. All values are stored inline in SkipList nodes. Reads never touch disk — zero I/O reads.

Each ConstTree owns its storage engine — one tree = one database directory.

Write hooks

Uses WriteHook<K>. on_write fires on put/insert/delete/cas/update. Does not fire inside atomic(). on_init fires once per live entry during migrate() or replay_init(). Old value is always provided in on_write — NEEDS_OLD_VALUE is ignored (value is inline, zero cost).

Usage

let tree = ConstTree::<16, 64>::open("data/users", Config::default())?;
tree.put(&key, &value)?;
tree.close()?;

Iteration

iter(), range(), and prefix_iter() all return ConstIter which implements Iterator + DoubleEndedIterator with Item = (K, [u8; V]). Lock-free, zero disk I/O.

for (key, value) in tree.iter() { }
let latest = tree.prefix_iter(&user_id).take(20).collect::<Vec<_>>();
let oldest = tree.iter().rev().take(5);  // DoubleEndedIterator

Implementations

impl<K: Key, const V: usize> ConstTree<K, V>

pub fn open(path: impl AsRef<Path>, config: Config) -> DbResult<Self>

Open or create a ConstTree at the given path. Recovers the index from existing data files on disk.

impl<K: Key, const V: usize, H: WriteHook<K>> ConstTree<K, V, H>

pub fn open_hooked( path: impl AsRef<Path>, config: Config, hook: H, ) -> DbResult<Self>

Open or create a ConstTree with a write hook for secondary index maintenance.

pub fn close(self) -> DbResult<()>

Graceful shutdown: write hint files (if enabled), flush write buffers + fsync.

pub fn flush_buffers(&self) -> DbResult<()>

Flush all shard write buffers to disk (without fsync).

pub fn config(&self) -> &Config

Get the database configuration.

impl<K: Key, const V: usize, H: WriteHook<K>> ConstTree<K, V, H>

pub fn compact(&self) -> DbResult<usize>

Trigger a background compaction pass across all shards.

pub fn get(&self, key: &K) -> Option<[u8; V]>

Get a value by key. Lock-free, zero disk I/O.

pub fn get_or_err(&self, key: &K) -> DbResult<[u8; V]>

Get a value by key, returning Err(KeyNotFound) if absent.

pub fn put(&self, key: &K, value: &[u8; V]) -> DbResult<Option<[u8; V]>>

Insert or update a key-value pair. Returns the old value if the key existed.

pub fn insert(&self, key: &K, value: &[u8; V]) -> DbResult<()>

Insert a key-value pair only if the key does not exist. Returns Err(KeyExists) if the key is already present.

pub fn delete(&self, key: &K) -> DbResult<Option<[u8; V]>>

Delete a key. Returns the old value if the key existed.

pub fn atomic<R>( &self, shard_key: &K, f: impl FnOnce(&mut ConstShard<'_, K, V, H>) -> DbResult<R>, ) -> DbResult<R>

Atomically execute multiple operations on a single shard. All keys must route to the same shard as shard_key. The closure must be short — shard lock is held for its duration.

pub fn cas( &self, key: &K, expected: &[u8; V], new_value: &[u8; V], ) -> DbResult<()>

Compare-and-swap: if current value == expected, replace with new_value. Returns Ok(()) on success, Err(CasMismatch) if current != expected, Err(KeyNotFound) if key doesn’t exist. Zero I/O — values are inline in SkipList nodes.

pub fn update( &self, key: &K, f: impl FnOnce(&[u8; V]) -> [u8; V], ) -> DbResult<Option<[u8; V]>>

Atomically read-modify-write. Returns Some(new_value) if key existed, None otherwise. Zero I/O — values are inline in SkipList nodes. The closure must not be heavy (shard lock is held).

pub fn fetch_update( &self, key: &K, f: impl FnOnce(&[u8; V]) -> [u8; V], ) -> DbResult<Option<[u8; V]>>

Like update(), but returns Some(old_value) instead of the new one.

pub fn contains(&self, key: &K) -> bool

Check if a key exists.

pub fn first(&self) -> Option<(K, [u8; V])>

Return the first entry in index order, or None if empty. With reversed=true (default): the entry with the largest key. O(1) — follows head’s level-0 pointer, skipping marked nodes.

pub fn last(&self) -> Option<(K, [u8; V])>

Return the last entry in index order, or None if empty. With reversed=true (default): the entry with the smallest key.

pub fn prefix_iter(&self, prefix: &[u8]) -> ConstIter<'_, K, V>

Iterate entries whose keys start with prefix.

reversed=true (default): yields matching keys in DESC order. next() is O(1), next_back() is O(log n).

pub fn iter(&self) -> ConstIter<'_, K, V>

Iterate all entries in index order.

reversed=true (default): DESC. reversed=false: ASC. next() is O(1), next_back() is O(log n).

pub fn range(&self, start: &K, end: &K) -> ConstIter<'_, K, V>

Iterate entries in [start, end) — start inclusive, end exclusive.

reversed=true (default): DESC within range. reversed=false: ASC. next() is O(1), next_back() is O(log n).

pub fn range_bounds( &self, start: Bound<&K>, end: Bound<&K>, ) -> ConstIter<'_, K, V>

Iterate entries in range defined by start and end bounds.

Unlike range(), allows Included, Excluded, or Unbounded for each bound independently.

reversed=true (default): DESC within range. reversed=false: ASC. next() is O(1), next_back() is O(log n).

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn sync_hints(&self) -> DbResult<()>

Write hint files for all active shard files. Call during graceful shutdown.

pub fn migrate( &self, f: impl Fn(&K, &[u8; V]) -> MigrateAction<[u8; V]>, ) -> DbResult<usize>

Iterate all entries and optionally mutate them. Call once at startup.

The callback receives each (key, value) and returns MigrateAction:

• Keep — no change (fires on_init if NEEDS_INIT)
• Update(new_value) — replace value (fires on_init, hook-free write)
• Delete — remove entry (hook-free delete, no on_init)

on_write is never fired during migration. Returns the number of mutated entries.

pub fn shard_for(&self, key: &K) -> usize

Trait Implementations

impl<K: Key, const V: usize, H: WriteHook<K>> CompactionIndex<K> for ConstTree<K, V, H>

fn update_if_match(&self, key: &K, old_loc: DiskLoc, new_loc: DiskLoc) -> bool

If the current index points to old_loc, it is updated to new_loc and returns true.

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

Returns true if the key currently exists in the index (i.e. has a live Put).

fn invalidate_blocks(&self, _shard_id: u8, _file_id: u32, _total_bytes: u64)

Invalidate cached blocks for a file after compaction replaces its contents.

impl<K: Key, const V: usize, H: WriteHook<K>> ReplicationTarget for ConstTree<K, V, H>

Available on crate feature replication only.

fn apply_entry( &self, shard_id: u8, file_id: u32, entry_offset: u64, header: &EntryHeader, key: &[u8], value: &[u8], ) -> DbResult<()>

Apply entry with known key/value split (streaming mode, O(1) routing).

fn try_apply_entry( &self, shard_id: u8, file_id: u32, entry_offset: u64, header: &EntryHeader, raw_after_header: &[u8], ) -> DbResult<bool>

Try to apply entry with CRC matching (catch-up mode). Returns true if CRC matched and entry was applied.

fn key_len(&self) -> usize

The key length (K) for this tree type.