Struct lsm_tree::Tree

source ·

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

Expand description

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

The tree is internally synchronized (Send + Sync), so it does not need to be wrapped in a lock nor an Arc.

To share the tree between threads, use Arc::clone(&tree) or tree.clone().

Implementations§

source §

impl Tree

source

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

Opens the tree at the given folder.

Will create a new tree if the folder is not in use or recover a previous state if it exists.

Examples

use lsm_tree::{Config, Tree};

let tree = Tree::open(Config::new(folder))?;
// Same as
let tree = Config::new(folder).open()?;

Errors

Will return Err if an IO error occurs.

source

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

Gets the given key’s corresponding entry in the map for in-place manipulation.

Examples

use lsm_tree::{Config, Tree};

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

let value = tree.entry("a")?.or_insert("abc")?;
assert_eq!("abc".as_bytes(), &*value);

Errors

Will return Err if an IO error occurs.

source

pub fn snapshot(&self) -> 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")?;

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

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

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

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

source

pub fn batch(&self) -> Batch

Initializes a new, atomic write batch.

Call Batch::commit to commit the batch to the tree.

Dropping the batch will not commit items to the tree.

Examples

use lsm_tree::{Config, Tree};

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

let mut batch = tree.batch();
batch.insert("a", "hello");
batch.insert("b", "hello2");
batch.insert("c", "hello3");
batch.remove("idontlikeu");

batch.commit()?;

assert_eq!(3, tree.len()?);

source

pub fn disk_space(&self) -> Result<u64>

Sums the disk space usage of the tree (segments + journals).

Examples

use lsm_tree::{Config, Tree};

let tree = Config::new(folder).open()?;
assert_eq!(0, tree.disk_space()?);

source

pub fn approximate_len(&self) -> Result<u64>

Approximates the item count of the tree.

This metric is only reliable for insert-only (no updates, deletes) workloads. Otherwise, the value may become less accurate over time and only converge to the real value time as compaction kicks in.

This operation has O(1) complexity and can be used without feeling bad about it.

source

pub fn config(&self) -> Config

Returns the tree configuration.

Examples

use lsm_tree::{Config, Tree};

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

assert_eq!(Config::default().block_size, tree.config().block_size);

source

pub fn block_cache_size(&self) -> usize

Returns the amount of cached blocks.

Examples

use lsm_tree::{Config, Tree};

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

assert_eq!(0, tree.block_cache_size());

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")?;
tree.insert("3", "abc")?;
tree.insert("5", "abc")?;
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", nanoid::nanoid!())?;
assert!(!tree.is_empty()?);

Errors

Will return Err if an IO error occurs.

source

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

Inserts a key-value pair into the tree.

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

Examples

use lsm_tree::{Config, Tree};

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

Errors

Will return Err if an IO error occurs.

source

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

Deletes an item from the tree.

Examples

use lsm_tree::{Config, Tree};

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

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

tree.remove("a")?;

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

Errors

Will return Err if an IO error occurs.

source

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

Removes the item and returns its value if it was previously in the tree.

This is less efficient than just deleting because it needs to do a read before deleting.

Examples

use lsm_tree::{Config, Tree};

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

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

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

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

Errors

Will return Err if an IO error occurs.

source

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

Returns true if the tree contains the specified key.

Examples

use lsm_tree::{Config, Tree};

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

tree.insert("a", nanoid::nanoid!())?;
assert!(tree.contains_key("a")?);

Errors

Will return Err if an IO error occurs.

source

pub fn iter(&self) -> Range<'_>

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", nanoid::nanoid!())?;
tree.insert("f", nanoid::nanoid!())?;
tree.insert("g", nanoid::nanoid!())?;
assert_eq!(3, tree.iter().into_iter().count());

Errors

Will return Err if an IO error occurs.

source

pub fn range<K: AsRef<[u8]>, R: RangeBounds<K>>(&self, range: R) -> Range<'_>

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", nanoid::nanoid!())?;
tree.insert("f", nanoid::nanoid!())?;
tree.insert("g", nanoid::nanoid!())?;
assert_eq!(2, tree.range("a"..="f").into_iter().count());

Errors

Will return Err if an IO error occurs.

source

pub fn prefix<K: AsRef<[u8]>>(&self, prefix: K) -> Prefix<'_>

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", nanoid::nanoid!())?;
tree.insert("ab", nanoid::nanoid!())?;
tree.insert("abc", nanoid::nanoid!())?;
assert_eq!(2, tree.prefix("ab").into_iter().count());

Errors

Will return Err if an IO error occurs.

source

pub fn first_key_value(&self) -> Result<Option<(Arc<[u8]>, Arc<[u8]>)>>

Returns the first key-value pair in the tree. The key in this pair is the minimum key in the tree.

Examples

use lsm_tree::{Tree, Config};

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

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

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<(Arc<[u8]>, Arc<[u8]>)>>

Returns the last key-value pair in the tree. The key in this pair is the maximum key in the tree.

Examples

use lsm_tree::{Tree, Config};

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

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

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

Errors

Will return Err if an IO error occurs.

source

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

Retrieves an item from the tree.

Examples

use lsm_tree::{Config, Tree};

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

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 compare_and_swap<K: AsRef<[u8]>>( &self, key: K, expected: Option<&Arc<[u8]>>, next: Option<&Arc<[u8]>> ) -> Result<Result<(), CompareAndSwapError>>

Compare-and-swap an entry

Errors

Will return Err if an IO error occurs.

Panics

Panics on lock poisoning

source

pub fn fetch_update<K: AsRef<[u8]>, V: AsRef<[u8]>, F: Fn(Option<&Arc<[u8]>>) -> Option<V>>( &self, key: K, f: F ) -> Result<Option<Arc<[u8]>>>

Atomically fetches and updates an item if it exists.

Returns the previous value if the item exists.

Examples

use lsm_tree::{Config, Tree};

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

let prev = tree.fetch_update("key".as_bytes(), |_| Some("b"))?.expect("item should exist");
assert_eq!("a".as_bytes(), &*prev);

let item = tree.get("key")?.expect("item should exist");
assert_eq!("b".as_bytes(), &*item);

let prev = tree.fetch_update("key", |_| None::<String>)?.expect("item should exist");
assert_eq!("b".as_bytes(), &*prev);

assert!(tree.is_empty()?);

Errors

Will return Err if an IO error occurs.

source

pub fn update_fetch<K: AsRef<[u8]>, V: AsRef<[u8]>, F: Fn(Option<&Arc<[u8]>>) -> Option<V>>( &self, key: K, f: F ) -> Result<Option<Arc<[u8]>>>

Atomically fetches and updates an item if it exists.

Returns the updated value if the item exists.

Examples

use lsm_tree::{Config, Tree};

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

let prev = tree.update_fetch("key", |_| Some("b"))?.expect("item should exist");
assert_eq!("b".as_bytes(), &*prev);

let item = tree.get("key")?.expect("item should exist");
assert_eq!("b".as_bytes(), &*item);

let prev = tree.update_fetch("key", |_| None::<String>)?;
assert_eq!(None, prev);

assert!(tree.is_empty()?);

Errors

Will return Err if an IO error occurs.

source

pub fn flush(&self) -> Result<()>

Flushes the journal to disk, making sure all written data is persisted and crash-safe.

Examples

use lsm_tree::{Config, Tree};

let tree = Config::new(folder.clone()).open()?;
tree.insert("a", nanoid::nanoid!())?;
tree.flush()?;

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

let item = tree.get("a")?;
assert!(item.is_some());