Struct Tree 

pub struct Tree(/* private fields */);

A log-structured merge tree (LSM-tree/LSMT)

Implementations

impl Tree

pub fn columnar_scan<R: RangeBounds<UserKey>>( &self, projection: &[u16], predicate: Option<&ColumnRangePredicate>, seqno: SeqNo, range: R, ) -> Result<ColumnarScan>

Runs a projected columnar scan across the whole tree.

Iterates the columnar segments intersecting range and visible at seqno, applies each segment’s positional delete-bitmap and the optional predicate (zone-map block-skip + row filter), and yields projected [ColumnBatch]es in ascending key order. Overlapping segments are merged with newest-seqno-wins semantics so an overwritten key is returned once (its newest version); disjoint segments stream without merge overhead.

range bounds the result at row granularity: a segment that only partially overlaps range contributes only the rows whose keys fall inside it (the inclusive / exclusive sense of each bound is honored). A fully unbounded range keeps the zero-copy fast path for an all-visible segment.

projection lists the column ids to decode (value sub-column ids, plus optionally the intrinsic [COL_USER_KEY] / seqno / value-type columns); every other column is stepped over without decoding. Each yielded batch carries exactly the projected columns.

This reads only segments; memtable rows are not consulted (columnar data is written directly to segments via write_columnar_batch).

Errors

Returns an error if a visible non-columnar segment overlaps range (a mixed-mode tree is unsupported here), if the tree carries a merge operator (see below), or — lazily, while iterating — on a block read / decode failure or a layout mismatch between segments of an overlapping group.

impl Tree

pub fn scan_since_seqno( &self, target_seqno: SeqNo, ) -> Result<impl Iterator<Item = ScanSinceEvent> + use<>>

Iterate change events with seqno >= target_seqno.

Returns every change committed at or after target_seqno as a stream of ScanSinceEvents in increasing seqno order. This is the canonical change-data-capture primitive: a downstream consumer (replica, Kafka connector, Debezium-style pipeline) replays the events in order to reconstruct the source’s history. Superseded versions are not collapsed (a key written three times after the target yields three events).

Concurrency

The result is a snapshot of the tree as of the call: the active memtable is captured with writers excluded, so a batch committed concurrently is either wholly in the result or wholly absent, never split across it. This holds even for a caller-chosen sequence number at or below the reported watermark, which the seqno bound alone would not exclude. Writers are blocked only while that capture runs — the sealed memtables and SSTs the scan then reads are immutable.

History retention

The stream carries what the tree still PHYSICALLY HOLDS. A compaction run with a GC watermark (the seqno_threshold passed to compact / major_compact) drops shadowed versions and evicted tombstones below that watermark and may fold merge chains and zero bottommost seqnos — history a later scan cannot resurrect. The result is therefore complete only for a target_seqno at or above the highest GC watermark ever applied: a deployment replaying this stream (an external-WAL consumer, a CDC replica) must keep its compaction watermark at or below the lowest cursor it may still rewind to, exactly as docs/external-wal.md section 4’s GC-coordination rules require. The watermark is caller-supplied and not persisted, so this method cannot detect a violation for you.

Block-skip

On SSTs written with the seqno_bounds section (seqno_in_index), data blocks whose bounds cannot overlap the target window are skipped without being read; SSTs without the section are read and filtered per entry, so mixed trees are handled transparently.

KV-separation

Standard trees never store blob-indirected values. On the inner tree of a KV-separated (blob) tree this returns an Err for indirected entries: blob resolution into ScanSinceEvent::Insert is provided by the blob-tree scan path, which owns the blob files.

Corruption resilience

The per-block seqno-bounds used for skipping live in the optional seqno_bounds SST section, a Block covered by XXH3-128 (+ optional Page ECC) and verified when it is loaded at open, plus a decode that rejects non-ascending offsets and inverted bounds, so a corrupted bound is caught rather than trusted. Even in the impossible case of a fault bypassing those checks, a bad bound can only cause a missed record, never a wrong one. Callers who want defense against that hypothetical can use Self::scan_since_seqno_full_scan, which reads every block (slower, no skip).

Panics

Panics if the internal version-history lock is poisoned.

Errors

Returns Err if reading the index or a data block fails, or if an entry is a KV-separated value (see above).

pub fn scan_since_seqno_full_scan( &self, target_seqno: SeqNo, ) -> Result<impl Iterator<Item = ScanSinceEvent> + use<>>

Paranoid variant of Self::scan_since_seqno that disables the per-block seqno-bounds skip: every data block is read and filtered per entry, even on seqno-indexed SSTs.

When to use

The fast Self::scan_since_seqno trusts each block’s recorded [seqno_min, seqno_max] to skip blocks that cannot hold a qualifying record. Those bounds live in the seqno_bounds SST section, a Block covered by XXH3-128 (and optional Page ECC) and verified at open, so on-disk corruption is caught, not silently trusted. This method exists for callers who want defense even against a fault that somehow bypassed those checks: a corrupted seqno_max can only ever cause a missed record (never a wrong one), and a full scan cannot miss. It is slower (no skip), so prefer Self::scan_since_seqno unless you specifically need this guarantee.

Panics

Panics if the internal version-history lock is poisoned.

Errors

Same as Self::scan_since_seqno.

pub fn scan_since_seqno_in_range<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, target_seqno: SeqNo, range: R, ) -> Result<impl Iterator<Item = ScanSinceEvent> + use<K, R>>

Range-scoped variant of Self::scan_since_seqno: delivers only events whose key falls within range (in the tree comparator’s order); range-deletion events are delivered when their span OVERLAPS it, since a tombstone reaching into the range affects replay within it. SSTs whose key range cannot intersect the bounds are skipped without a single block read.

This is the presence-check primitive for reconciling an external write-ahead log after a repair: RepairReport::lost_coverage names the affected key ranges, and deciding which retained WAL records to re-apply (in particular, which merge operands SURVIVED and must not be folded twice) only needs the events inside those ranges. See docs/external-wal.md § Replay after repair.

The history-retention caveat of Self::scan_since_seqno applies unchanged: the stream is complete only for a target_seqno at or above the highest compaction GC watermark ever applied.

Panics

Panics if the internal version-history lock is poisoned.

Errors

Same as Self::scan_since_seqno.

pub fn update_runtime_config<F>(&self, mutator: F) -> Result<()>

where F: FnOnce(&mut RuntimeConfig),

Update the live crate::runtime_config::RuntimeConfig.

Mutator runs on a clone of the current snapshot; the new snapshot is then atomically swapped in. Subsequent calls to Self::runtime_config observe the new snapshot.

Current scope

This API ships the snapshot + atomic-swap mechanism. No write path in the current tree consults runtime_config yet — that wiring lands with the V5-batch format features (manifest hardening, per-KV protection, scan-since-seqno) which extend RuntimeConfig with their own fields and read it at block write / manifest commit / compaction boundaries.

Designed semantics (effective once wired by V5 features)

• Subsequent write paths load the new snapshot lockless on their next operation.
• Existing on-disk data remains in its original format and reads transparently — every block / manifest is self-describing via its own header.
• Compaction acts as the live-migration mechanism: source blocks are rewritten per the current snapshot over subsequent cycles, so all data converges to the current settings without stop-the-world coordination.

Concurrency

Reader atomicity: concurrent readers observe either the old or the new snapshot, never a torn intermediate state.

Writer semantics: last-writer-wins. Two update calls racing from the same starting snapshot will have the second store overwrite the first — the first writer’s mutation is lost. There is no CAS / RCU merge. Callers that need lost-update avoidance (e.g. two threads concurrently toggling different fields) MUST serialize their update_runtime_config calls, typically via a Mutex around the call site.

Errors

Returns crate::Error::PageEccUnsupported when the mutator leaves page_ecc = true on a binary built without the page_ecc cargo feature. The live snapshot stays at its pre-mutation value on error.

pub fn runtime_config(&self) -> Arc<RuntimeConfig>

Snapshot of the current runtime config. Cheap atomic load — safe to call on hot paths.

pub fn heal_hints(&self) -> Arc<HealHints>

Shared handle to this tree’s ECC heal-hint queue.

A read that recovers a block from Page-ECC parity records the owning SST here (when the on-disk fault is confirmed persistent). Pass the handle to compaction::EccHeal and run that strategy via Tree::compact — leader-only in a clustered deployment — to rewrite the flagged SSTs clean. Check HealHints::is_empty to skip the pass when nothing is queued.

Examples

use lsm_tree::{AbstractTree, AnyTree, Config, SequenceNumberCounter, compaction::EccHeal};
use std::sync::Arc;
let AnyTree::Standard(tree) = Config::new(
    "/tmp/db",
    SequenceNumberCounter::default(),
    SequenceNumberCounter::default(),
)
.open()?
else {
    return Ok(());
};

// Opt into rewrite scheduling; reads that recover a block from parity now
// flag its SST for healing.
tree.update_runtime_config(|c| c.auto_heal = true)?;

// Drain the queue, rewriting each flagged SST clean (leader-only in a
// clustered deployment).
let hints = tree.heal_hints();
while !hints.is_empty() {
    tree.compact(Arc::new(EccHeal::new(tree.heal_hints(), u64::MAX)), 0)?;
}

Trait Implementations

impl AbstractTree for Tree

fn tombstone_count(&self) -> u64

Returns the number of tombstones in the tree.

fn weak_tombstone_count(&self) -> u64

Returns the number of weak tombstones (single deletes) in the tree.

fn weak_tombstone_reclaimable_count(&self) -> u64

Returns the number of value entries that become reclaimable once weak tombstones can be GC’d.

fn table_file_cache_size(&self) -> usize

Returns the number of cached table file descriptors.

fn blob_file_count(&self) -> usize

Returns the number of blob files currently in the tree.

fn create_checkpoint(&self, target_path: &Path) -> Result<CheckpointInfo>

Creates a hard-linked checkpoint of the tree’s on-disk state in target_path for point-in-time recovery (PITR) backup.

fn storage_stats(&self) -> Result<StorageStats>

Returns a read-only snapshot of the tree’s on-disk storage footprint: total used bytes, entry count, the average shape of a stored entry (average key / value bytes), and an estimate of how many more average-shaped entries fit in a byte budget (see StorageStats::estimated_remaining_entries).

fn write_admission(&self) -> Result<()>

Storage admission gate: Ok(()) if a write may proceed, or Error::StorageFull if the tree is over budget and should be treated as read-only.

fn write_backpressure(&self, strategy: &dyn CompactionStrategy) -> Backpressure

Computed write-backpressure verdict from the live L0 table count and the strategy’s pending-compaction bytes, against the configured RuntimeConfig::backpressure thresholds.

fn get_flush_lock(&self) -> MutexGuard<'_, ()>

Acquires the flush lock which is required to call Tree::flush.

fn metrics(&self) -> &Arc<Metrics>

Returns the metrics structure.

fn cache_stats(&self) -> CacheStats

A point-in-time CacheStats snapshot of block-cache effectiveness (cumulative hit / miss counts and rate) and occupancy (current size against capacity).

fn version_free_list_len(&self) -> usize

Gets the length of the version free list.

fn prefix<K: AsRef<[u8]>>( &self, prefix: K, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>

Returns an iterator over a prefixed set of items.

fn range<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>

Returns an iterator over a range of items.

fn range_seekable<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn SeekableGuardIter + 'static>

Returns a range iterator that can reposition (seek) in place without reopening its per-SST readers.

fn batch_range_scan<K: AsRef<[u8]>, R: RangeBounds<K> + 'static, I: IntoIterator<Item = R>>( &self, intervals: I, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn Iterator<Item = IterGuardImpl> + Send + 'static>

where I::IntoIter: Send + 'static,

Scans a sequence of disjoint, ascending key sub-intervals, reusing one set of per-SST readers across all of them.

fn drop_range<K: AsRef<[u8]>, R: RangeBounds<K>>(&self, range: R) -> Result<()>

Drops tables that are fully contained in a given range.

fn clear(&self) -> Result<()>

Drops all tables and clears all memtables atomically.

fn l0_run_count(&self) -> usize

Returns the number of disjoint runs in L0.

fn size_of<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<Option<u32>>

Returns the size of a value if it exists.

fn filter_size(&self) -> u64

Gets the space usage of all filters in the tree.

fn pinned_filter_size(&self) -> usize

Gets the memory usage of all pinned filters in the tree.

fn pinned_block_index_size(&self) -> usize

Gets the memory usage of all pinned index blocks in the tree.

fn sealed_memtable_count(&self) -> usize

Returns the number of sealed memtables.

fn register_tables( &self, tables: &[Table], blob_files: Option<&[BlobFile]>, frag_map: Option<FragmentationMap>, sealed_memtables_to_delete: &[MemtableId], gc_watermark: SeqNo, ) -> Result<()>

Atomically registers flushed tables into the tree, removing their associated sealed memtables.

fn clear_active_memtable(&self)

Clears the active memtable atomically.

fn compact( &self, strategy: Arc<dyn CompactionStrategy>, seqno_threshold: SeqNo, ) -> Result<CompactionResult>

Performs compaction on the tree’s levels, blocking the caller until it’s done.

fn get_next_table_id(&self) -> TableId

Returns the next table’s ID.

fn tree_config(&self) -> &Config

Returns the tree config.

fn active_memtable(&self) -> Arc<Memtable>

Returns the active memtable.

fn rotate_memtable(&self) -> Option<Arc<Memtable>>

Seals the active memtable.

fn table_count(&self) -> usize

Returns the number of tables currently in the tree.

fn level_table_count(&self, idx: usize) -> Option<usize>

Returns the number of tables in levels[idx].

fn approximate_len(&self) -> usize

Approximates the number of items in the tree.

fn disk_space(&self) -> u64

Returns the disk space usage.

fn approximate_range_stats<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, ) -> Result<ApproximateRangeStats>

Estimates the on-disk bytes and entry count contained in range at seqno, WITHOUT reading any data block.

fn approximate_range_cardinality<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, ) -> Result<RangeCardinality>

Estimates the row cardinality and selectivity of range at seqno, WITHOUT reading any data block.

fn get_highest_memtable_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number of the active memtable.

fn get_highest_persisted_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number that is flushed to disk.

fn oldest_retained_seqno(&self) -> SeqNo

Returns the seqno of the oldest version the history still retains: the lower bound of the readable snapshot window.

fn retention_floor(&self) -> SeqNo

Returns the PERSISTED retention boundary: the highest snapshot seqno the tree will refuse after a reopen.

fn get<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<Option<UserValue>>

Retrieves an item from the tree.

fn get_pinned<K: AsRef<[u8]>>( &self, key: K, seqno: SeqNo, ) -> Result<Option<PinnableSlice>>

Retrieves an item from the tree as a PinnableSlice.

fn multi_get<K: AsRef<[u8]>>( &self, keys: impl IntoIterator<Item = K>, seqno: SeqNo, ) -> Result<Vec<Option<UserValue>>>

Reads multiple keys from the tree.

fn apply_batch(&self, batch: WriteBatch, seqno: SeqNo) -> Result<(u64, u64)>

Applies a WriteBatch with the given sequence number.

fn insert<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, value: V, seqno: SeqNo, ) -> (u64, u64)

Inserts a key-value pair into the tree.

fn merge<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, operand: V, seqno: SeqNo, ) -> (u64, u64)

Writes a merge operand for a key.

fn remove<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u64, u64)

Removes an item from the tree.

fn remove_range<K: Into<UserKey>>(&self, start: K, end: K, seqno: SeqNo) -> u64

Deletes all keys in the range [start, end) by inserting a range tombstone.

fn level_segment_stats(&self) -> Result<Vec<LevelStats>>

Per-LSM-level and per-segment size + entry-count stats, for tiering and erasure-coding placement decisions (which level / segment is large enough to demote, EC-encode, or migrate).

fn compaction_debt(&self, strategy: &dyn CompactionStrategy) -> u64

Estimated bytes pending compaction under strategy: on-disk data above its level’s target that must eventually be rewritten downward (a RocksDB estimate-pending-compaction-bytes analog), a compaction-debt signal for a scheduler / tiering consumer.

fn is_read_only(&self) -> bool

true when the admission gate is currently closed (see write_admission). Convenience for callers that want a boolean rather than a Result. Always false unless admission control is enabled and the tree is over budget.

fn verify_checksum(&self) -> BlockVerifyReport

where Self: Sized,

Proactively verifies every block’s XXH3 checksum across every SST in the tree’s current version — a scrubber for catching bit rot before it surfaces as a user-visible read failure (cron / scrub jobs).

fn verify_checksum_with(&self, options: &VerifyOptions) -> BlockVerifyReport

where Self: Sized,

Like Self::verify_checksum but with configurable parallelism and I/O throttle (see VerifyOptions).

fn flush( &self, _lock: &MutexGuard<'_, ()>, seqno_threshold: SeqNo, ) -> Result<Option<u64>>

Synchronously flushes pending sealed memtables to tables.

fn iter( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>

Returns an iterator that scans through the entire tree.

fn major_compact( &self, target_size: u64, seqno_threshold: SeqNo, ) -> Result<CompactionResult>

Performs major compaction, blocking the caller until it’s done.

fn stale_blob_bytes(&self) -> u64

Returns the disk space used by stale blobs.

fn flush_to_tables( &self, stream: impl Iterator<Item = Result<InternalValue>>, ) -> Result<Option<(Vec<Table>, Option<Vec<BlobFile>>)>>

Synchronously flushes a memtable to a table.

fn get_highest_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number.

fn tree_type(&self) -> TreeType

Returns the tree type.

fn len( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<usize>

Scans the entire tree, returning the number of items.

fn is_empty( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<bool>

Returns true if the tree is empty.

fn first_key_value( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Option<IterGuardImpl>

Returns the first key-value pair in the tree. The key in this pair is the minimum key in the tree.

fn last_key_value( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Option<IterGuardImpl>

Returns the last key-value pair in the tree. The key in this pair is the maximum key in the tree.

fn contains_key<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<bool>

Returns true if the tree contains the specified key.

fn contains_prefix<K: AsRef<[u8]>>( &self, prefix: K, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<bool>

Returns true if the tree contains any key with the given prefix.

fn try_insert<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, value: V, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated insert: consults write_admission first and declines with Error::StorageFull when the tree is over budget, otherwise inserts and returns the same (added_bytes, memtable_size) tuple. This is the write entry a space-aware caller uses so over-budget writes are refused up front rather than failing a flush later; bare insert stays infallible for callers that do not opt into admission control.

fn try_merge<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, operand: V, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated merge. See try_insert.

fn try_remove<K: Into<UserKey>>( &self, key: K, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated remove. See try_insert.

fn try_remove_weak<K: Into<UserKey>>( &self, key: K, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated remove_weak. See try_insert.

fn try_remove_range<K: Into<UserKey>>( &self, start: K, end: K, seqno: SeqNo, ) -> Result<u64>

Admission-gated remove_range. See try_insert.

fn remove_prefix<K: AsRef<[u8]>>(&self, prefix: K, seqno: SeqNo) -> u64

Deletes all keys with the given prefix by inserting a range tombstone.

impl Clone for Tree

fn clone(&self) -> Tree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Deref for Tree

type Target = TreeInner

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl From<Tree> for AnyTree

fn from(v: Tree) -> AnyTree

Converts to this type from the input type.

impl TryInto<Tree> for AnyTree

type Error = &'static str

The type returned in the event of a conversion error.

fn try_into(self) -> Result<Tree, <Self as TryInto<Tree>>::Error>

Performs the conversion.