Trait AbstractTree 

pub trait AbstractTree: Sealed {
    // Required methods
    fn table_file_cache_size(&self) -> usize;
    fn write_rate_limiter(&self) -> Arc<RateLimiter> ;
    fn create_checkpoint(&self, target_path: &Path) -> Result<CheckpointInfo>;
    fn pin(&self) -> PinnedVersion;
    fn acknowledge_repair_report(&self, id: u128) -> Result<bool>;
    fn persist_flushes(&self) -> Result<()>;
    fn prefix<K: AsRef<[u8]>>(
        &self,
        prefix: K,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>;
    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>;
    fn range_seekable<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn SeekableGuardIter + 'static>;
    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;
    fn tombstone_count(&self) -> u64;
    fn weak_tombstone_count(&self) -> u64;
    fn weak_tombstone_reclaimable_count(&self) -> u64;
    fn clear(&self) -> Result<()>;
    fn major_compact(
        &self,
        target_size: u64,
        gc_watermark: SeqNo,
    ) -> Result<CompactionResult>;
    fn filter_size(&self) -> u64;
    fn pinned_filter_size(&self) -> usize;
    fn filter_memory(&self) -> FilterMemory;
    fn pinned_block_index_size(&self) -> usize;
    fn metrics(&self) -> &Arc<Metrics> ;
    fn cache_stats(&self) -> CacheStats;
    fn get_flush_lock(&self) -> MutexGuard<'_, ()>;
    fn register_tables(
        &self,
        tables: &[Table],
        blob_files: Option<&[BlobFile]>,
        frag_map: Option<FragmentationMap>,
        sealed_memtables_to_delete: &[MemtableId],
        gc_watermark: SeqNo,
        collected_below_watermark: bool,
    ) -> Result<()>;
    fn clear_active_memtable(&self);
    fn sealed_memtable_count(&self) -> usize;
    fn compact(
        &self,
        strategy: Arc<dyn CompactionStrategy>,
        gc_watermark: SeqNo,
    ) -> Result<CompactionResult>;
    fn get_next_table_id(&self) -> TableId;
    fn tree_config(&self) -> &Config;
    fn active_memtable(&self) -> Arc<Memtable> ;
    fn active_memtable_is_empty(&self) -> bool;
    fn rotate_memtable(&self) -> Option<Arc<Memtable>>;
    fn table_count(&self) -> usize;
    fn level_table_count(&self, idx: usize) -> Option<usize>;
    fn l0_run_count(&self) -> usize;
    fn blob_file_count(&self) -> usize;
    fn approximate_len(&self) -> usize;
    fn disk_space(&self) -> u64;
    fn approximate_range_stats<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
    ) -> Result<ApproximateRangeStats>;
    fn approximate_range_cardinality<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
    ) -> Result<RangeCardinality>;
    fn get_highest_memtable_seqno(&self) -> Option<SeqNo>;
    fn get_highest_persisted_seqno(&self) -> Option<SeqNo>;
    fn oldest_retained_seqno(&self) -> SeqNo;
    fn retention_floor(&self) -> SeqNo;
    fn lower_retention_floor(&self, floor: SeqNo) -> Result<()>;
    fn compaction_rate_limiter(&self) -> Arc<RateLimiter> ;
    fn size_of<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: SeqNo,
    ) -> Result<Option<u32>>;
    fn get<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: SeqNo,
    ) -> Result<Option<UserValue>>;
    fn apply_batch(&self, batch: WriteBatch, seqno: SeqNo) -> Result<(u64, u64)>;
    fn insert<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        value: V,
        seqno: SeqNo,
    ) -> (u64, u64);
    fn remove<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u64, u64);
    fn merge<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        operand: V,
        seqno: SeqNo,
    ) -> (u64, u64);
    fn remove_range<K: Into<UserKey>>(
        &self,
        start: K,
        end: K,
        seqno: SeqNo,
    ) -> u64;

    // Provided methods
    fn storage_stats(&self) -> Result<StorageStats> { ... }
    fn level_segment_stats(&self) -> Result<Vec<LevelStats>> { ... }
    fn compaction_debt(&self, strategy: &dyn CompactionStrategy) -> u64 { ... }
    fn write_backpressure(
        &self,
        _strategy: &dyn CompactionStrategy,
    ) -> Backpressure { ... }
    fn write_backpressure_for(
        &self,
        strategy: &dyn CompactionStrategy,
        bytes: u64,
    ) -> Backpressure { ... }
    fn write_admission(&self) -> Result<()> { ... }
    fn is_read_only(&self) -> bool { ... }
    fn verify_checksum(&self) -> BlockVerifyReport
       where Self: Sized { ... }
    fn verify_checksum_with(&self, options: &VerifyOptions) -> BlockVerifyReport
       where Self: Sized { ... }
    fn flush_active_memtable(&self, gc_watermark: SeqNo) -> Result<()> { ... }
    fn sync_devices(&self) -> Result<()> { ... }
    fn flush(
        &self,
        _lock: &MutexGuard<'_, ()>,
        gc_watermark: SeqNo,
    ) -> Result<Option<u64>> { ... }
    fn iter(
        &self,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static> { ... }
    fn stale_blob_bytes(&self) -> u64 { ... }
    fn flush_to_tables(
        &self,
        stream: impl Iterator<Item = Result<InternalValue>>,
    ) -> Result<Option<(Vec<Table>, Option<Vec<BlobFile>>, WritePin)>> { ... }
    fn get_highest_seqno(&self) -> Option<SeqNo> { ... }
    fn tree_type(&self) -> TreeType { ... }
    fn len(
        &self,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Result<usize> { ... }
    fn is_empty(
        &self,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Result<bool> { ... }
    fn first_key_value(
        &self,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Option<IterGuardImpl> { ... }
    fn last_key_value(
        &self,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Option<IterGuardImpl> { ... }
    fn get_pinned<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: SeqNo,
    ) -> Result<Option<PinnableSlice>> { ... }
    fn contains_key<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<bool> { ... }
    fn contains_prefix<K: AsRef<[u8]>>(
        &self,
        prefix: K,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Result<bool> { ... }
    fn multi_get<K: AsRef<[u8]>>(
        &self,
        keys: impl IntoIterator<Item = K>,
        seqno: SeqNo,
    ) -> Result<Vec<Option<UserValue>>> { ... }
    fn try_insert<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        value: V,
        seqno: SeqNo,
    ) -> Result<(u64, u64)> { ... }
    fn try_merge<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        operand: V,
        seqno: SeqNo,
    ) -> Result<(u64, u64)> { ... }
    fn try_remove<K: Into<UserKey>>(
        &self,
        key: K,
        seqno: SeqNo,
    ) -> Result<(u64, u64)> { ... }
    fn try_remove_weak<K: Into<UserKey>>(
        &self,
        key: K,
        seqno: SeqNo,
    ) -> Result<(u64, u64)> { ... }
    fn try_remove_range<K: Into<UserKey>>(
        &self,
        start: K,
        end: K,
        seqno: SeqNo,
    ) -> Result<u64> { ... }
    fn remove_prefix<K: AsRef<[u8]>>(&self, prefix: K, seqno: SeqNo) -> u64 { ... }
}

Generic Tree API

Required Methods

fn table_file_cache_size(&self) -> usize

Returns the number of cached table file descriptors.

fn write_rate_limiter(&self) -> Arc<RateLimiter>

The limiter writes are paced with under backpressure slowdown: shared with other trees if one was supplied through Config::write_rate_limiter, else the tree’s own. Retune it live with RateLimiter::set_rate; 0 turns byte pacing off.

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.

The checkpoint is a fully functional tree that can be opened independently via Config::open. For the common single-filesystem case all SST files (and blob files, for BlobTree) are hard-linked rather than copied, so the operation is O(1) per file and consumes zero additional disk space until the original files are compacted away — at which point the inode is kept alive by the checkpoint link.

Cross-filesystem / cross-backend fall-back

When a source file lives on a different filesystem than the checkpoint target — e.g. an SST routed to a hot tier via level_routes on a separate volume, or a backup directory on a foreign mount — the hard link cannot be created (Unix EXDEV). In that case the checkpoint silently falls back to a streamed byte copy, which:

• takes time linear in the file size instead of O(1), and
• consumes disk space equal to the copied bytes on the target volume (no inode sharing across filesystems).

Each fall-back call emits one log::debug line (deliberately not warn: a misconfigured tier could trigger this path once per SST and per blob — thousands of times per snapshot — and per-file warnings would drown real signal). Operators wanting hard-visibility of unexpected full copies should enable debug logging on the fs module or watch the CheckpointInfo.total_bytes figure (≫ inode link cost means the fallback fired). The same debug policy applies when source and target use entirely different Fs backends (e.g. MemFs → StdFs in tests).

Durability

Ok means the checkpoint’s files and directories are persisted under Config::sync_mode: durable under SyncMode::Full; under SyncMode::Barrier synced in order, one barrier per file, and durable once a later Fs::sync_device of target_path returns Ok.

Concurrency

While the checkpoint is being built, compaction continues normally but the physical removal of obsolete files is deferred until the checkpoint hard-links are in place. This is implemented by an internal reference-counted deletion gate; callers do not have to pause compaction themselves.

Errors

Returns an error if:

• the active memtable could not be flushed,
• target_path already exists (to prevent accidental overwrites),
• a hard link / copy fall-back could not be created, or
• the manifest files could not be replicated.

On error any partial checkpoint files are removed automatically (best-effort) so callers can safely retry against the same path.

fn pin(&self) -> PinnedVersion

Pins the tree’s current state for a point-in-time copy that costs no file I/O: seals the active memtable and returns a PinnedVersion holding the sealed memtables, tables, blob files and dictionaries as they are now.

Nothing is copied, linked, synced or written. The pinned files stay on disk with unchanged bytes while flushes and compactions supersede them, until the last pin listing them drops; a consumer streams them byte for byte and rebuilds the tree elsewhere with Config::restore_pinned. A restart drops every pin.

Waits for an in-place heal or a tight-space hole punch already under way to finish; new ones on a pinned file wait for the pin.

Examples

use lsm_tree::{AbstractTree, Config, SequenceNumberCounter};

let folder = tempfile::tempdir()?;
let seqno = SequenceNumberCounter::default();
let visible = SequenceNumberCounter::default();
let tree = Config::new(&folder, seqno.clone(), visible.clone()).open()?;
tree.insert("a", "1", seqno.next());
tree.flush_active_memtable(0)?;
tree.insert("b", "2", seqno.next());
// The writes are published: the pin holds every write below this.
visible.set(seqno.get());

let pin = tree.pin();
assert_eq!(pin.tables().len(), 1);
assert_eq!(pin.memtable_entries().count(), 1);

fn acknowledge_repair_report(&self, id: u128) -> Result<bool>

Stops the tree owing the repair report with this RepairReport::id, installing a version that no longer carries it: no later Config::open_or_repair hands it out.

A repair’s report stays in the tree until this call, so a process that ends before the caller acted on it gets it again. Call it once the report’s replay obligation is met. Returns false, changing nothing, when the tree owes no report or owes one with another id.

Errors

Propagates the install’s failure; the report is then still owed, or, on Error::InstallOutcomeUnknown, may be after a power loss.

Examples

use lsm_tree::{AbstractTree, Config, RepairPolicy, SequenceNumberCounter};

let config = Config::new(
    "/var/lib/mydb",
    SequenceNumberCounter::default(),
    SequenceNumberCounter::default(),
);
let (tree, repaired) = config.open_or_repair(RepairPolicy::default())?;
if let Some(report) = repaired {
    // Replay the external log as `report.wal_replay_scope()` requires,
    // then let the tree forget the report.
    tree.acknowledge_repair_report(report.id)?;
}

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

Makes every flush installed before this call durable, under FlushDurability::Deferred: the tables and blob files those flushes wrote are synced, then their folders, then the manifest is written. Once it returns Ok a caller may drop its own log up to the writes those flushes held; under SyncMode::Barrier after sync_devices as well. A no-op when nothing is pending, and under FlushDurability::Synced every flush is durable when it returns.

Every other install (a compaction, an ingestion, a drop) persists the pending flushes with it, and so do a checkpoint and a dropped tree.

Examples

use lsm_tree::{AbstractTree, Config, SequenceNumberCounter, config::FlushDurability};

let tree = Config::new(
    folder.path(),
    SequenceNumberCounter::default(),
    SequenceNumberCounter::default(),
)
.flush_durability(FlushDurability::Deferred)
.open()?;
for i in 0..3_u64 {
    tree.insert(i.to_be_bytes(), "v", i);
    tree.flush_active_memtable(0)?;
}
// One barrier for the three flushes.
tree.persist_flushes()?;

Errors

Returns a sync or manifest write error; the flushes stay installed and readable, and the next persist retries them.

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.

Avoid using an empty prefix as it may scan a lot of items (unless limited).

A snapshot at or below the retention floor (see oldest_retained_seqno) yields Error::SnapshotBelowRetention as the iterator’s first and only item.

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.

Avoid using full or unbounded ranges as they may scan a lot of items (unless limited).

A snapshot at or below the retention floor (see oldest_retained_seqno) yields Error::SnapshotBelowRetention as the iterator’s first and only item.

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.

Unlike range’s boxed DoubleEndedIterator, the returned [SeekableGuardIter] additionally exposes seek_to / seek_to_for_prev, so a consumer can jump a live iterator to any key (RocksDB Seek / SeekForPrev) — enabling data-dependent scans (joins, skip-scan) without reopening per-SST readers per jump.

A snapshot at or below the retention floor (see oldest_retained_seqno) yields Error::SnapshotBelowRetention as the iterator’s first and only item (also through peek_key); seeks on such an iterator are no-ops.

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.

The per-SST setup is paid once (when the underlying seekable iterator is opened); each interval is served by repositioning that iterator. This amortizes the setup across N intervals instead of paying it per interval, so multi-interval scan throughput scales with the total rows returned rather than the interval count.

The interval source is pulled lazily, so intervals may be produced on demand (e.g. computed from rows already returned).

A snapshot at or below the retention floor (see oldest_retained_seqno) yields Error::SnapshotBelowRetention as the iterator’s first and only item.

fn tombstone_count(&self) -> u64

Returns the approximate number of tombstones in the tree.

fn weak_tombstone_count(&self) -> u64

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

fn weak_tombstone_reclaimable_count(&self) -> u64

Returns the approximate number of values reclaimable once weak tombstones can be GC’d.

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

Drops all tables and clears all memtables atomically.

Errors

Will return Err only if an IO error occurs.

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

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

Returns a crate::compaction::CompactionResult describing what action was taken.

GC watermark (gc_watermark)

gc_watermark is the one number that decides what history the engine’s own GC may collect: every snapshot at or above it that is still servable (above the current retention floor) stays readable, and a version only snapshots below it could see may be dropped. It never lowers the floor: a snapshot an earlier run already refused stays refused. Concretely, only entries whose seqno is < gc_watermark are eligible for:

• dropping shadowed versions / GC-ing tombstones, and
• folding merge operands via the crate::MergeOperator: a key written only through Self::merge (no base value) accumulates one operand per call, and reads re-apply the whole chain (O(operands) per read) until compaction folds it. Folding a chain into a single value is only MVCC-safe when no live snapshot reads between the operands, which is exactly what gc_watermark certifies.

The engine does not track snapshots (unlike a RocksDB-style snapshot list); the caller owns snapshot lifecycle and must supply this watermark:

• To fold/GC everything (no active snapshots), pass a value above every live seqno (e.g. the next value from the crate::SequenceNumberCounter).
• With outstanding snapshots, pass the oldest snapshot’s seqno so their reads stay correct.
• gc_watermark == 0 certifies nothing as collapsible, so no folding or GC happens: major_compact(target, 0) only restructures tables and leaves a merge-only key’s full operand chain intact.

A run that collects anything raises the retention floor to gc_watermark - 1 (capped at the install’s own seqno) unless it is already higher. When the opt-in tight-space mode takes over a run (RuntimeConfig::tight_space_compaction), each slice raises it that far whether or not it collected. The floor is the only read boundary: from then on a new read at or below it (see oldest_retained_seqno) fails with Error::SnapshotBelowRetention, which is why the watermark must not exceed the oldest snapshot still in use. A reader opened before the install keeps its own version, and the tables it references, until it is dropped.

A compaction filter is the exception: it acts on whatever version it is shown, regardless of gc_watermark (0 included). A run whose filter removed or rewrote anything raises the floor to the install’s own seqno, so every snapshot up to it is refused from then on, however low the watermark was.

Errors

Will return Err if an IO error occurs.

fn filter_size(&self) -> u64

Gets the space usage of all filters in the tree.

May not correspond to the actual memory size because filter blocks may be paged out.

fn pinned_filter_size(&self) -> usize

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

fn filter_memory(&self) -> FilterMemory

The serialised and the resident bytes of the tree’s filters, and how they stand against a FilterAdvisor budget.

Looks up each live table’s filter blocks in the block cache without counting a hit.

Examples

use lsm_tree::{AbstractTree, Config, config::FilterAdvisor};

let tree = Config::new(&folder, Default::default(), Default::default())
    .filter_advisor(Some(FilterAdvisor::new(64 * 1_024)))
    .open()?;
tree.insert("a", "value", 0);
tree.flush_active_memtable(0)?;

let memory = tree.filter_memory();
assert_eq!(memory.serialised_bytes, tree.filter_size());
assert_eq!(memory.budget_bytes, Some(64 * 1_024));
assert!(!memory.over_budget);

fn pinned_block_index_size(&self) -> usize

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

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).

The stable, owned observability view over the block cache, so a consumer can read cache health without holding the mutable metrics handle. Counts are cumulative since process start; derive a rate over an interval from the delta between two polls.

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

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

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

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

gc_watermark must be the same threshold the stream that produced tables ran with, and collected_below_watermark whether that stream actually dropped a version because of it. Together they are the install’s retention effect: understating either admits reads whose answer the flush already collected, overstating collected_below_watermark refuses reads whose data is still on disk.

Errors

Will return Err if an IO error occurs.

fn clear_active_memtable(&self)

Clears the active memtable atomically.

fn sealed_memtable_count(&self) -> usize

Returns the number of sealed memtables.

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

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

Returns a crate::compaction::CompactionResult describing what action was taken.

gc_watermark has the meaning documented at major_compact: the engine’s own GC collects only versions below it, and a run that collects one raises the retention floor. Before the strategy chooses, the run unlinks every table a flushed range tombstone below the watermark spans whole and is newer than (see remove_range).

Two things act regardless of the watermark: a compaction filter, and a strategy that drops whole tables (FIFO eviction, a custom strategy choosing to drop). Either removes data at any watermark, 0 included, and raises the floor to the install’s own seqno, so a low watermark does not protect a snapshot from them.

Errors

Will return Err if an IO error occurs.

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 active_memtable_is_empty(&self) -> bool

Whether the active memtable holds nothing, so that the next write makes one more flush owed. Sealed memtables do not count.

Under std it takes no lock, unlike active_memtable, so it may be called from inside a version install, as a metered file system’s admission is. A concurrent write can change the answer as it returns.

Examples

use lsm_tree::{AbstractTree, Config, SequenceNumberCounter};
let tree = Config::new(
    &folder,
    SequenceNumberCounter::default(),
    SequenceNumberCounter::default(),
)
.open()?;
assert!(tree.active_memtable_is_empty());

tree.insert("key", "value", 0);
assert!(!tree.active_memtable_is_empty());

tree.rotate_memtable();
assert!(tree.active_memtable_is_empty());

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].

Returns None if the level does not exist (if idx >= 7).

fn l0_run_count(&self) -> usize

Returns the number of disjoint runs in L0.

Can be used to determine whether to write stall.

fn blob_file_count(&self) -> usize

Returns the number of blob files currently in the tree.

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.

The estimate interpolates each overlapping SST’s data-block offsets at the range boundaries (block granularity) and adds the active + sealed memtables’ in-range share. For a KV-separated tree the per-SST blob bytes are apportioned by the same in-range fraction (blob files are not key-indexed, so a finer estimate is impossible without reading data). Intended for query planning (split-point selection, cost-based join ordering), not exact accounting; accuracy is typically within ~10-15% on roughly-uniform data.

Examples

use lsm_tree::{AbstractTree, Config};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default()).open()?;
for i in 0..100u32 {
    tree.insert(format!("k{i:04}"), "value", 0);
}
tree.flush_active_memtable(0)?;

// The full range covers every entry exactly once it is all flushed —
// estimated without reading a single data block.
let all = tree.approximate_range_stats::<&str, _>(.., 1)?;
assert_eq!(all.key_count, tree.approximate_len() as u64);
assert!(all.bytes > 0);

// A range past every key is empty.
let none = tree.approximate_range_stats("zzzz".."zzzzz", 1)?;
assert_eq!(none.key_count, 0);
assert_eq!(none.bytes, 0);

Errors

Returns an error if a block index or table metadata read fails.

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.

Uses the per-data-block zone map (per-block row counts + key ranges) for a block-granularity row count: every data block whose key range overlaps the query contributes its recorded row count, plus the active + sealed memtables’ in-range counts. When a table has no zone map the row count falls back to the byte-fraction estimate of approximate_range_stats. Selectivity is rows / total_rows, monotonic in predicate tightness, for cost-based planning (join ordering, scan-vs-seek). Not exact accounting.

Examples

use lsm_tree::{AbstractTree, Config};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default()).open()?;
for i in 0..100u32 {
    tree.insert(format!("k{i:04}"), "v", 0);
}
tree.flush_active_memtable(0)?;

// The full range covers every row; selectivity is 1.0.
let all = tree.approximate_range_cardinality::<&str, _>(.., 1)?;
assert_eq!(all.rows, tree.approximate_len() as u64);
assert!((all.selectivity - 1.0).abs() < 1e-9);

// A tighter range selects fewer rows.
let part = tree.approximate_range_cardinality("k0000".."k0050", 1)?;
assert!(part.selectivity <= all.selectivity);

Errors

Returns an error if a block index, zone map, or table metadata read fails.

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.

Under FlushDurability::Deferred only the flushes a persist made durable count: a flush that is installed but not yet persisted would be lost by a power loss.

fn oldest_retained_seqno(&self) -> SeqNo

Returns the retention floor: the lower bound of the readable snapshot window.

A snapshot is servable iff it is 0 (sees nothing) or strictly above this seqno; a new read at 0 < seqno <= oldest_retained_seqno() fails with Error::SnapshotBelowRetention. A caller holding a long-lived snapshot (a lagging consumer, a point-in-time query) can validate it here before reading and report “history collected” instead of an unexpected error mid-scan. A reader opened before the floor rose is not affected: it keeps the version it resolved. A fresh tree reports 0.

The install that discards what older snapshots saw raises the floor in the same version edit, so the boundary is the same live and after a reopen: after a GC with watermark w it is w - 1, capped at the install’s own seqno; after a clear, a table drop or a compaction whose filter transformed rows it is that install’s seqno. A manifest rebuilt by Config::repair cannot know what the lost manifest recorded and seeds the boundary from Config::repair_retention_floor (default 0: every snapshot served).

Examples

use lsm_tree::{AbstractTree, Config, Error, SequenceNumberCounter};

let seqno = SequenceNumberCounter::default();
let tree = Config::new(folder, seqno.clone(), Default::default()).open()?;
assert_eq!(tree.oldest_retained_seqno(), 0);

tree.insert("a", "v1", seqno.next());
tree.flush_active_memtable(0)?;
let stale = seqno.get();
tree.insert("a", "v2", seqno.next());
tree.flush_active_memtable(0)?;

// A watermark above every live snapshot lets compaction collect the
// old version; the boundary moves past the stale snapshot.
tree.major_compact(u64::MAX, seqno.get())?;
let oldest = tree.oldest_retained_seqno();
assert!(stale <= oldest);
assert!(matches!(
    tree.get("a", stale),
    Err(Error::SnapshotBelowRetention { .. })
));
assert_eq!(tree.get("a", oldest + 1)?.as_deref(), Some(b"v2".as_slice()));

fn retention_floor(&self) -> SeqNo

Returns the persisted retention floor: the highest snapshot seqno the tree refuses, now and after a reopen. It always equals oldest_retained_seqno.

This is the value a deployment records for a later manifest repair (Config::repair_retention_floor): it already folds in every operation that moved the boundary (GC compactions, clear, table drops, filtering compactions, and lower_retention_floor), so no caller-side bookkeeping of watermarks is needed. 0 until the first such install.

fn lower_retention_floor(&self, floor: SeqNo) -> Result<()>

Lowers the persisted retention floor to floor, so snapshots above it are served again, now and after a reopen.

For a rebuild from a source that kept history above its own floor: clear the tree, reinstall the source’s history at its original seqnos, then lower the floor to the source’s retention_floor. Until this call the clear’s floor refuses every snapshot below it, so a reader never sees the history half reinstalled, and a crash before the call leaves that refusal in place.

The tree cannot check the claim this call makes: that it holds every version above floor a snapshot above floor could see. That includes not collecting any of the reinstalled history with a GC watermark above floor + 1 before the call.

Errors

Error::RetentionFloorRaise when floor is above the current floor, which only GC and the installs that drop data raise; nothing changes. Error::RetentionFloorAboveSeqno when floor is above the seqno counter (one reset on reopen can stand below the current floor); nothing changes. An I/O error persisting the new floor.

Examples

use lsm_tree::{AbstractTree, Config, SequenceNumberCounter};

let tree = Config::new(folder, SequenceNumberCounter::new(100), Default::default()).open()?;
tree.clear()?;
// Reinstall a source's history, which it kept above seqno 5.
tree.insert("k", "v", 10);
tree.lower_retention_floor(5)?;
assert_eq!(tree.get("k", 11)?.as_deref(), Some(b"v".as_slice()));
assert!(tree.get("k", 5).is_err());

fn compaction_rate_limiter(&self) -> Arc<RateLimiter>

Returns the limiter that throttles this tree’s compactions: the one supplied through Config::compaction_rate_limiter, which other trees may share, or the tree’s own built from Config::compaction_rate_limit.

Change the rate while the tree runs, with no restart, through RateLimiter::set_rate: every tree holding the limiter is bounded by the new rate from its next request.

Examples

use lsm_tree::{AbstractTree, Config};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default())
    .compaction_rate_limit(16 * 1_024 * 1_024)
    .open()?;
tree.compaction_rate_limiter().set_rate(64 * 1_024 * 1_024);
assert_eq!(tree.compaction_rate_limiter().rate(), 64 * 1_024 * 1_024);

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

Returns the size of a value if it exists.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
tree.insert("a", "my_value", 0);

let size = tree.size_of("a", 1)?.unwrap_or_default();
assert_eq!("my_value".len() as u32, size);

let size = tree.size_of("b", 1)?.unwrap_or_default();
assert_eq!(0, size);

Errors

Will return Err if an IO error occurs.

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

Retrieves an item from the tree.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
tree.insert("a", "my_value", 0);

let item = tree.get("a", 1)?;
assert_eq!(Some("my_value".as_bytes().into()), item);

Errors

Will return Err if an IO error occurs, or Error::SnapshotBelowRetention when seqno is at or below the retention floor (see oldest_retained_seqno). The same applies to every read that resolves a snapshot: get_pinned, contains_key, size_of, multi_get, len, is_empty, first_key_value, last_key_value, approximate_range_stats and approximate_range_cardinality.

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

Applies a WriteBatch with the given sequence number.

All entries share a single seqno. This is more efficient than individual writes because the version-history lock and memtable size accounting are performed only once for the entire batch.

Visibility: entries become individually visible to concurrent readers as they are inserted. For atomic batch visibility, the caller must publish seqno (via visible_seqno.fetch_max(seqno + 1)) only after this method returns.

Returns the total bytes added and new size of the memtable.

Examples

use lsm_tree::{AbstractTree, Config, Tree, WriteBatch};

let tree = Config::new(&folder, Default::default(), Default::default()).open()?;

let mut batch = WriteBatch::new();
batch.insert("key1", "value1");
batch.insert("key2", "value2");
batch.remove("key3");

let (bytes_added, memtable_size) = tree.apply_batch(batch, 0)?;
assert!(bytes_added > 0);

Errors

Returns Error::MixedOperationBatch if the batch contains mixed operation types for the same user key.

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.

If the key already exists, the item will be overwritten.

Returns the added item’s size and new size of the memtable.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
tree.insert("a", "abc", 0);

Errors

Will return Err if an IO error occurs.

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

Removes an item from the tree.

Returns the added item’s size and new size of the memtable.

Examples

tree.insert("a", "abc", 0);

let item = tree.get("a", 1)?.expect("should have item");
assert_eq!("abc".as_bytes(), &*item);

tree.remove("a", 1);

let item = tree.get("a", 2)?;
assert_eq!(None, item);

Errors

Will return Err if an IO error occurs.

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

Writes a merge operand for a key.

The operand is stored as a partial update that will be combined with other operands and/or a base value via the configured crate::MergeOperator during reads and compaction.

Returns the added item’s size and new size of the memtable.

Examples

tree.merge("counter", 1_i64.to_le_bytes(), 0);

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.

This is much more efficient than deleting keys individually when removing a contiguous range of keys. The deletion is exact at once, whatever tables hold the keys; a snapshot below seqno still reads them.

Space comes back without rewriting: once the tombstone is flushed, every compaction whose gc_watermark is above seqno first unlinks each table the tombstone spans whole and is newer than, before its strategy chooses. Tables that reach past [start, end) keep their bytes until a merge rewrites them. Dropping tables raises the retention floor, at most to seqno: snapshots at or below the floor report Error::SnapshotBelowRetention.

Nothing is rewritten only where the range ends at table boundaries, which holds when keys arrive in the order of the range (a time series expiring its oldest days); a range cutting through tables leaves their survivors to the merge that rewrites them. The deletion covers this tree only: a caller indexing these keys elsewhere removes them there.

To empty the whole tree, clear does it without a tombstone.

Returns the approximate size added to the memtable. Returns 0 if start >= end (invalid interval is silently ignored).

This is a required method on the crate’s sealed tree types.

Provided Methods

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).

Computed from the live version’s table + blob metadata plus one size-stat per live file; it never reads a data block. The default implementation reports StorageStatus::Healthy; the standard tree overrides it to report StorageStatus::CompactionInProgress while a compaction runs.

Examples

use lsm_tree::{AbstractTree, Config};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default()).open()?;

for i in 0..100u64 {
    tree.insert(format!("key{i:04}"), "value", i);
}
tree.flush_active_memtable(0)?;

let stats = tree.storage_stats()?;
assert_eq!(stats.item_count, 100);
// Roughly how many more average-shaped entries fit in another 1 MiB.
let _headroom = stats.estimated_remaining_entries(1024 * 1024);

Errors

Returns an error if a live file’s size cannot be stat-ed, or a table’s blob-link section cannot be read or parsed.

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).

Cheap: derived from the live version’s metadata plus one file-size stat per segment (no data-block scan); in a tree that separates values, each segment’s blob-link section is also read once, then kept. The per-level totals reconcile with storage_stats: summed across levels they equal the SST portion of StorageStats::used_bytes and StorageStats::item_count.

Examples

use lsm_tree::{AbstractTree, Config};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default()).open()?;
for i in 0..100u32 {
    tree.insert(format!("k{i:04}"), "v", 0);
}
tree.flush_active_memtable(0)?;

let levels = tree.level_segment_stats()?;
let total: u64 = levels.iter().map(|l| l.item_count).sum();
assert_eq!(total, tree.storage_stats()?.item_count);

Errors

Returns an error if a segment’s file size cannot be stat-ed, or its blob-link section cannot be read or parsed.

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.

The strategy is supplied by the caller because the engine does not own a configured compaction strategy (it is injected per compaction run); a &dyn keeps this object-safe. Returns 0 for strategies without a size-target notion of debt (FIFO), or when the tree is at or below its target shape. See CompactionStrategy::pending_compaction_bytes.

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

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

Advisory, mirroring write_admission: the caller consults it and throttles in its own write loop (sleep suggested_delay at Slowdown, pause at Stop). The engine never blocks on it, because it does not own the compaction that drains the debt — an internal stall could deadlock the very thread that would compact.

The strategy is supplied by the caller for the same reason as compaction_debt. Returns Backpressure::None by default (no thresholds configured).

fn write_backpressure_for( &self, strategy: &dyn CompactionStrategy, bytes: u64, ) -> Backpressure

The verdict for one write of bytes: write_backpressure, except that a slowdown on a tree with a write rate limit (see Config::write_rate_limit) debits bytes from the tree’s write limiter and suggests waiting until they, and every byte debited before them, are paid off at its rate. Writes honouring it are then bounded by the rate in bytes per second, large and small alike, however many writers share the limiter. Outside the slowdown tier nothing is debited.

Examples

use lsm_tree::{AbstractTree, Backpressure, Config, compaction::Leveled};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default())
    .write_rate_limit(1_024 * 1_024)
    .open()?;
// No threshold set: full speed, nothing debited.
assert_eq!(tree.write_backpressure_for(&Leveled::default(), 4_096), Backpressure::None);

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.

Opt-in: returns Ok(()) unless storage_admission_check is enabled. The predicate is computed (not latched), so once space is freed — the budget raised, a compaction reclaiming space, or disk freed — the next call admits again with no restart.

Intended as a cheap pre-check the caller consults before applying a write batch. The footprint is cached per version, so the check is a constant-time read on the common path and only re-measures when a new version is installed (flush / compaction). Internal flush / compaction are never gated, so the engine can always reclaim.

Errors

Error::StorageFull when the live footprint plus reserved headroom exceeds the effective budget.

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.

Only Error::StorageFull counts as read-only: an unrelated admission error (e.g. an I/O failure while measuring the footprint) is NOT an out-of-space condition and must not be reported as one.

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).

Reports at block granularity and never aborts early. The returned BlockVerifyReport records block-corruption findings with (file, offset), while file-level errors (e.g. BlockVerifyError::SstFileUnreadable) carry the file only (no offset). It does not surface per-entry indices or ECC-correction counts (when ECC-at-rest is enabled a within-budget corrupt block may still be healed on read as a side effect of the scan, but the report does not tally corrections).

Filesystems with native per-block integrity (ZFS, Btrfs, ReFS, S3 — see Fs::capabilities) already detect corruption on read; this scrub is the portable check for the rest.

Use Self::verify_checksum_with for parallelism / throttle control.

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_active_memtable(&self, gc_watermark: SeqNo) -> Result<()>

Seals the active memtable and flushes it, with every memtable sealed before it, to tables: the durability barrier for a caller that keeps its own journal of the writes.

Ok means the tables, their directories and the manifest edits that name them are persisted under Config::sync_mode for the memtable active at the call and for every memtable sealed before it, in sealing order, including one another thread began flushing: the call waits for that flush and, should it fail, flushes the memtable itself. A caller may release the journal entries those memtables hold once the call returns Ok; under SyncMode::Barrier the writes are only ordered then, and the entries may go once sync_devices has returned Ok too.

gc_watermark has the meaning documented at major_compact; pass 0 to collect nothing.

Errors

Returns the error of flush; the memtables it could not persist stay sealed, and the next call flushes them.

Examples

use lsm_tree::{AbstractTree, Config, SequenceNumberCounter};

let folder = tempfile::tempdir()?;
let tree = Config::new(
    &folder,
    SequenceNumberCounter::default(),
    SequenceNumberCounter::default(),
)
.open()?;
tree.insert("key", "value", 0);
// The write is on disk now (the default sync mode is not `Barrier`): a
// journal that holds it can drop it.
tree.flush_active_memtable(0)?;
assert_eq!(tree.table_count(), 1);

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

Makes durable everything this tree synced on each device it lies on: the tree folder’s, that of every level’s tables, that of the dictionaries folder and, with KV separation, that of the blobs folder.

Under SyncMode::Barrier a flush_active_memtable that returns Ok has its writes ordered, and they are durable once this returns Ok; a caller releases its journal after both. Under any other mode the flush alone is durable and this only flushes the device caches.

Errors

Returns the error of a device flush that failed; the devices not yet flushed are not.

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

Synchronously flushes pending sealed memtables to tables.

Returns the sum of flushed memtable sizes that were flushed.

The function may not return a result, if nothing was flushed.

gc_watermark has the meaning documented at major_compact: the flush folds away versions below it exactly as a compaction does, and when it does, the install raises the retention floor (retention_floor) to match. Pass 0 to collect nothing.

Errors

Returns Err on an I/O error, or on a memtable residence-verification failure under KvChecksumComputePoint::AtInsert: a sealed memtable whose insert-time per-KV digests do not verify before flush surfaces crate::Error::MemtableKvChecksumMismatch, crate::Error::MemtableKvChecksumCorruptAlgorithm, or crate::Error::InvalidTag (corrupt value_type).

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.

Avoid using this function, or limit it as otherwise it may scan a lot of items.

A snapshot at or below the retention floor (see oldest_retained_seqno) yields Error::SnapshotBelowRetention as the iterator’s first and only item.

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>>, WritePin)>>

Synchronously flushes a memtable to a table.

This method will not make the table immediately available, use AbstractTree::register_tables for that.

Alongside the files comes a WritePin on the compression dictionaries they were written against. Keep it until register_tables returns: until then no installed file names those dictionaries, and a collection in between would take them.

Errors

Will return Err if an IO error occurs.

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.

Caution

This operation scans the entire tree: O(n) complexity!

Never, under any circumstances, use .len() == 0 to check if the tree is empty, use Tree::is_empty instead.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let folder = tempfile::tempdir()?;
let tree = Config::new(&folder, Default::default(), Default::default()).open()?;

assert_eq!(tree.len(0, None)?, 0);
tree.insert("1", "abc", 0);
tree.insert("3", "abc", 1);
tree.insert("5", "abc", 2);
assert_eq!(tree.len(3, None)?, 3);

Errors

Will return Err if an IO error occurs.

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

Returns true if the tree is empty.

This operation has O(log N) complexity.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
assert!(tree.is_empty(0, None)?);

tree.insert("a", "abc", 0);
assert!(!tree.is_empty(1, None)?);

Errors

Will return Err if an IO error occurs.

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.

Examples

let tree = Config::new(folder, Default::default(), Default::default()).open()?;

tree.insert("1", "abc", 0);
tree.insert("3", "abc", 1);
tree.insert("5", "abc", 2);

let key = tree.first_key_value(3, None).expect("item should exist").key()?;
assert_eq!(&*key, "1".as_bytes());

Errors

Will return Err if an IO error occurs.

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.

Examples

tree.insert("1", "abc", 0);
tree.insert("3", "abc", 1);
tree.insert("5", "abc", 2);

let key = tree.last_key_value(3, None).expect("item should exist").key()?;
assert_eq!(&*key, "5".as_bytes());

Errors

Will return Err if an IO error occurs.

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

Retrieves an item from the tree as a PinnableSlice.

When the value is backed by an on-disk data block, implementations may return PinnableSlice::Pinned holding a reference to that block’s decompressed buffer (avoiding a data copy). Memtable and blob-resolved values use PinnableSlice::Owned. The default implementation always returns Owned; only Tree overrides with the pinned path.

The existing AbstractTree::get method is unaffected.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(&folder, Default::default(), Default::default()).open()?;
tree.insert("a", "my_value", 0);

let item = tree.get_pinned("a", 1)?;
assert_eq!(item.as_ref().map(|v| v.as_ref()), Some("my_value".as_bytes()));

Errors

Will return Err if an IO error occurs.

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

Returns true if the tree contains the specified key.

Examples

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
assert!(!tree.contains_key("a", 0)?);

tree.insert("a", "abc", 0);
assert!(tree.contains_key("a", 1)?);

Errors

Will return Err if an IO error occurs.

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.

This is a convenience method that checks whether the corresponding prefix iterator yields at least one item, while surfacing any IO errors via the Result return type. Implementations may override this method to provide a more efficient prefix-existence check.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
assert!(!tree.contains_prefix("abc", 0, None)?);

tree.insert("abc:1", "value", 0);
assert!(tree.contains_prefix("abc", 1, None)?);
assert!(!tree.contains_prefix("xyz", 1, None)?);

Errors

Will return Err if an IO error occurs.

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

Reads multiple keys from the tree.

Implementations may choose to perform all lookups against a single version snapshot and acquire the version lock only once, which can be more efficient than calling AbstractTree::get in a loop. The default trait implementation, however, is a convenience wrapper that simply calls AbstractTree::get for each key and therefore does not guarantee a single-snapshot or single-lock acquisition. Optimized implementations (such as Tree and BlobTree) provide the single-snapshot/one-lock behavior.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder, Default::default(), Default::default()).open()?;
tree.insert("a", "value_a", 0);
tree.insert("b", "value_b", 1);

let results = tree.multi_get(["a", "b", "c"], 2)?;
assert_eq!(results[0], Some("value_a".as_bytes().into()));
assert_eq!(results[1], Some("value_b".as_bytes().into()));
assert_eq!(results[2], None);

Errors

Will return Err if an IO error occurs.

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.

Errors

Error::StorageFull when the admission gate is closed.

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.

Errors

Error::StorageFull when the admission gate is closed.

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

Admission-gated remove. See try_insert.

Note a tombstone is itself a write that consumes space; an over-budget tree refuses it too. Reclaim space via compaction (never gated) rather than relying on deletes when already read-only.

Errors

Error::StorageFull when the admission gate is closed.

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

Admission-gated remove_weak. See try_insert.

Errors

Error::StorageFull when the admission gate is closed.

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

Admission-gated remove_range. See try_insert.

Errors

Error::StorageFull when the admission gate is closed.

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

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

This is sugar over AbstractTree::remove_range using prefix bounds.

Returns the approximate size added to the memtable. Returns 0 for empty prefixes or all-0xFF prefixes (cannot form valid half-open range).

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors

impl AbstractTree for AnyTree

impl AbstractTree for BlobTree

impl AbstractTree for Tree