Trait AbstractTree 

pub trait AbstractTree {
    // Required methods
    fn prefix<K: AsRef<[u8]>>(
        &self,
        prefix: K,
        seqno: SeqNo,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl<'_>> + '_>;
    fn range<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl<'_>> + '_>;
    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 major_compact(
        &self,
        target_size: u64,
        seqno_threshold: SeqNo,
    ) -> Result<()>;
    fn filter_size(&self) -> usize;
    fn pinned_filter_size(&self) -> usize;
    fn pinned_block_index_size(&self) -> usize;
    fn version_free_list_len(&self) -> usize;
    fn flush_memtable(
        &self,
        table_id: TableId,
        memtable: &Arc<Memtable>,
        seqno_threshold: SeqNo,
    ) -> Result<Option<(Table, Option<BlobFile>)>>;
    fn register_tables(
        &self,
        tables: &[Table],
        blob_files: Option<&[BlobFile]>,
        frag_map: Option<FragmentationMap>,
        seqno_threshold: SeqNo,
    ) -> Result<()>;
    fn clear_active_memtable(&self);
    fn set_active_memtable(&self, memtable: Memtable);
    fn sealed_memtable_count(&self) -> usize;
    fn add_sealed_memtable(&self, id: u64, memtable: Arc<Memtable>);
    fn compact(
        &self,
        strategy: Arc<dyn CompactionStrategy>,
        seqno_threshold: SeqNo,
    ) -> Result<()>;
    fn get_next_table_id(&self) -> TableId;
    fn tree_config(&self) -> &Config;
    fn active_memtable_size(&self) -> u64;
    fn tree_type(&self) -> TreeType;
    fn rotate_memtable(&self) -> Option<(u64, Arc<Memtable>)>;
    fn table_count(&self) -> usize;
    fn level_table_count(&self, idx: usize) -> Option<usize>;
    fn l0_run_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);

    // Provided methods
    fn iter(
        &self,
        seqno: SeqNo,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl<'_>> + '_> { ... }
    fn stale_blob_bytes(&self) -> u64 { ... }
    fn get_highest_seqno(&self) -> Option<SeqNo> { ... }
    fn blob_file_count(&self) -> usize { ... }
    fn len(&self, seqno: SeqNo, index: Option<Arc<Memtable>>) -> Result<usize> { ... }
    fn is_empty(
        &self,
        seqno: SeqNo,
        index: Option<Arc<Memtable>>,
    ) -> Result<bool> { ... }
    fn first_key_value(
        &self,
        seqno: SeqNo,
        index: Option<Arc<Memtable>>,
    ) -> Result<Option<KvPair>> { ... }
    fn last_key_value(
        &self,
        seqno: SeqNo,
        index: Option<Arc<Memtable>>,
    ) -> Result<Option<KvPair>> { ... }
    fn contains_key<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<bool> { ... }
}

Generic Tree API

Required Methods

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

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>>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl<'_>> + '_>

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

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

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

Errors

Will return Err if an IO error occurs.

fn filter_size(&self) -> usize

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 flush_memtable( &self, table_id: TableId, memtable: &Arc<Memtable>, seqno_threshold: SeqNo, ) -> Result<Option<(Table, Option<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 register_tables( &self, tables: &[Table], blob_files: Option<&[BlobFile]>, frag_map: Option<FragmentationMap>, seqno_threshold: 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 set_active_memtable(&self, memtable: Memtable)

Sets the active memtable.

May be used to restore the LSM-tree’s in-memory state from a write-ahead log after tree recovery.

fn sealed_memtable_count(&self) -> usize

Returns the number of sealed memtables.

fn add_sealed_memtable(&self, id: u64, memtable: Arc<Memtable>)

Adds a sealed memtables.

May be used to restore the LSM-tree’s in-memory state from some journals.

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

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

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_size(&self) -> u64

Returns the approximate size of the active memtable in bytes.

May be used to flush the memtable if it grows too large.

fn tree_type(&self) -> TreeType

Returns the tree type.

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

Seals the active memtable, and returns a reference to it.

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

Provided Methods

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

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 get_highest_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number.

fn blob_file_count(&self) -> usize

Returns the number of blob files currently in the tree.

fn len(&self, seqno: SeqNo, index: Option<Arc<Memtable>>) -> 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).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>>) -> 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).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>>, ) -> Result<Option<KvPair>>

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).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");
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>>, ) -> Result<Option<KvPair>>

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

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