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 drop_range(&self, key_range: KeyRange) -> 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,
        segment_id: SegmentId,
        memtable: &Arc<Memtable>,
        seqno_threshold: SeqNo,
    ) -> Result<Option<(Segment, Option<BlobFile>)>>;
    fn register_segments(
        &self,
        segments: &[Segment],
        blob_files: Option<&[BlobFile]>,
        seqno_threshold: SeqNo,
    ) -> Result<()>;
    fn lock_active_memtable(&self) -> RwLockWriteGuard<'_, Arc<Memtable>>;
    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_segment_id(&self) -> SegmentId;
    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 segment_count(&self) -> usize;
    fn level_segment_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 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 drop_range(&self, key_range: KeyRange) -> Result<()>

Drops segments that are fully contained in a given range.

Errors

Will return Err if an IO error occurs.

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, segment_id: SegmentId, memtable: &Arc<Memtable>, seqno_threshold: SeqNo, ) -> Result<Option<(Segment, Option<BlobFile>)>>

Synchronously flushes a memtable to a disk segment.

This method will not make the segment immediately available, use AbstractTree::register_segments for that.

Errors

Will return Err if an IO error occurs.

fn register_segments( &self, segments: &[Segment], blob_files: Option<&[BlobFile]>, seqno_threshold: SeqNo, ) -> Result<()>

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

Errors

Will return Err if an IO error occurs.

fn lock_active_memtable(&self) -> RwLockWriteGuard<'_, Arc<Memtable>>

Write-locks the active memtable for exclusive access

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_segment_id(&self) -> SegmentId

Returns the next segment’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 segment_count(&self) -> usize

Returns the number of disk segments currently in the tree.

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

Returns the number of segments 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 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