Struct lsm_tree::Tree

source ·

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

Expand description

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

Implementations§

source §

impl Tree

source

pub fn open(config: Config) -> Result<Self>

Opens an LSM-tree in the given directory.

Will recover previous state if the folder was previously occupied by an LSM-tree, including the previous configuration. If not, a new tree will be initialized with the given config.

After recovering a previous state, use Tree::set_active_memtable to fill the memtable with data from a write-ahead log for full durability.

§Errors

Returns error, if an IO error occured.

source

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

Run compaction, blocking the caller until it’s done.

§Errors

Will return Err if an IO error occurs.

source

pub fn snapshot(&self, seqno: SeqNo) -> Snapshot

Opens a read-only point-in-time snapshot of the tree

Dropping the snapshot will close the snapshot

§Examples

use lsm_tree::{Config, Tree};

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

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

let snapshot = tree.snapshot(1);
assert_eq!(snapshot.len()?, tree.len()?);

tree.insert("b", "abc", 1);

assert_eq!(2, tree.len()?);
assert_eq!(1, snapshot.len()?);

assert!(snapshot.contains_key("a")?);
assert!(!snapshot.contains_key("b")?);

source

pub fn register_segments(&self, segments: &[Arc<Segment>]) -> Result<()>

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

source

pub fn flush_active_memtable(&self) -> Result<Option<PathBuf>>

Synchronously flushes the active memtable to a disk segment.

The function may not return a result, if, during concurrent workloads, the memtable ends up being empty before the flush thread is set up.

The result will contain the disk segment’s path, relative to the tree’s base path.

§Errors

Will return Err if an IO error occurs.

source

pub fn first_level_segment_count(&self) -> usize

Returns the amount of disk segments in the first level.

source

pub fn segment_count(&self) -> usize

Returns the amount of disk segments currently in the tree.

source

pub fn approximate_len(&self) -> u64

Approximates the amount of items in the tree.

source

pub fn active_memtable_size(&self) -> u32

Returns the approximate size of the active memtable in bytes.

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

source

pub fn lock_active_memtable(&self) -> RwLockWriteGuard<'_, MemTable>

Write-locks the active memtable for exclusive access

source

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

Seals the active memtable, and returns a reference to it

source

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

source

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

source

pub fn len(&self) -> Result<usize>

Scans the entire tree, returning the amount 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::{Tree, Config};

let folder = tempfile::tempdir()?;
let tree = Config::new(folder).open()?;

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

§Errors

Will return Err if an IO error occurs.

source

pub fn is_empty(&self) -> Result<bool>

Returns true if the tree is empty.

This operation has O(1) complexity.

§Examples

use lsm_tree::{Config, Tree};

let tree = Config::new(folder).open()?;
assert!(tree.is_empty()?);

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

§Errors

Will return Err if an IO error occurs.

source

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

Retrieves an item from the tree.

§Examples

use lsm_tree::{Config, Tree};

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

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

§Errors

Will return Err if an IO error occurs.

source

pub fn insert<K: AsRef<[u8]>, V: AsRef<[u8]>>( &self, key: K, value: V, seqno: SeqNo ) -> (u32, u32)

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::{Config, Tree};

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

§Errors

Will return Err if an IO error occurs.

source

pub fn remove<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> (u32, u32)

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")?.expect("should have item");
assert_eq!("abc".as_bytes(), &*item);

tree.remove("a", 1);

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

§Errors

Will return Err if an IO error occurs.

source

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

Returns true if the tree contains the specified key.

§Examples

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

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

§Errors

Will return Err if an IO error occurs.

source

pub fn iter( &self ) -> impl DoubleEndedIterator<Item = Result<(UserKey, UserValue)>> + '_

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.

§Examples

use lsm_tree::{Config, Tree};

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

tree.insert("a", "abc", 0);
tree.insert("f", "abc", 1);
tree.insert("g", "abc", 2);
assert_eq!(3, tree.iter().count());

§Errors

Will return Err if an IO error occurs.

source

pub fn range<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R ) -> impl DoubleEndedIterator<Item = Result<(UserKey, UserValue)>> + '_

Returns an iterator over a range of items.

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

§Examples

use lsm_tree::{Config, Tree};

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

tree.insert("a", "abc", 0);
tree.insert("f", "abc", 1);
tree.insert("g", "abc", 2);
assert_eq!(2, tree.range("a"..="f").count());

§Errors

Will return Err if an IO error occurs.

source

pub fn prefix<K: AsRef<[u8]>>( &self, prefix: K ) -> impl DoubleEndedIterator<Item = Result<(UserKey, UserValue)>> + '_

Returns an iterator over a prefixed set of items.

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

§Examples

use lsm_tree::{Config, Tree};

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

tree.insert("a", "abc", 0);
tree.insert("ab", "abc", 1);
tree.insert("abc", "abc", 2);
assert_eq!(2, tree.prefix("ab").count());

§Errors

Will return Err if an IO error occurs.

source

pub fn first_key_value(&self) -> Result<Option<(UserKey, UserValue)>>

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()?.expect("item should exist");
assert_eq!(&*key, "1".as_bytes());

§Errors

Will return Err if an IO error occurs.

source

pub fn last_key_value(&self) -> Result<Option<(UserKey, UserValue)>>

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()?.expect("item should exist");
assert_eq!(&*key, "5".as_bytes());