Trait AbstractTree 

pub trait AbstractTree: Sealed {
    // Required methods
    fn table_file_cache_size(&self) -> usize;
    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 tombstone_count(&self) -> u64;
    fn weak_tombstone_count(&self) -> u64;
    fn weak_tombstone_reclaimable_count(&self) -> u64;
    fn drop_range<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
    ) -> Result<()>;
    fn clear(&self) -> Result<()>;
    fn major_compact(
        &self,
        target_size: u64,
        seqno_threshold: SeqNo,
    ) -> Result<CompactionResult>;
    fn filter_size(&self) -> u64;
    fn pinned_filter_size(&self) -> usize;
    fn pinned_block_index_size(&self) -> usize;
    fn version_free_list_len(&self) -> usize;
    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,
    ) -> Result<()>;
    fn clear_active_memtable(&self);
    fn sealed_memtable_count(&self) -> usize;
    fn compact(
        &self,
        strategy: Arc<dyn CompactionStrategy>,
        seqno_threshold: SeqNo,
    ) -> Result<CompactionResult>;
    fn get_next_table_id(&self) -> TableId;
    fn tree_config(&self) -> &Config;
    fn active_memtable(&self) -> Arc<Memtable>;
    fn tree_type(&self) -> TreeType;
    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 get_highest_memtable_seqno(&self) -> Option<SeqNo>;
    fn get_highest_persisted_seqno(&self) -> Option<SeqNo>;
    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 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 flush(
        &self,
        _lock: &MutexGuard<'_, ()>,
        seqno_threshold: 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>>)>> { ... }
    fn get_highest_seqno(&self) -> Option<SeqNo> { ... }
    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 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 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 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).

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

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 drop_range<K: AsRef<[u8]>, R: RangeBounds<K>>(&self, range: R) -> Result<()>

Drops tables that are fully contained in a given range.

Accepts any RangeBounds, including unbounded or exclusive endpoints. If the normalized lower bound is greater than the upper bound, the method returns without performing any work.

Errors

Will return Err only if an IO error occurs.

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, seqno_threshold: SeqNo, ) -> Result<CompactionResult>

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

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

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 pinned_block_index_size(&self) -> usize

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

fn version_free_list_len(&self) -> usize

Gets the length of the version free list.

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, ) -> Result<()>

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

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>, seqno_threshold: 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.

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 tree_type(&self) -> TreeType

Returns the tree type.

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

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.

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 flush( &self, _lock: &MutexGuard<'_, ()>, seqno_threshold: 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.

Errors

Will return Err if an IO error occurs.

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.

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.

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

Errors

Will return Err if an IO error occurs.

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

Returns the highest sequence number.

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 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 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", so this trait is not object safe.

Implementors

impl AbstractTree for AnyTree

impl AbstractTree for BlobTree

impl AbstractTree for Tree