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 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());