Lib.rs

A concurrent in-memory B+ tree featuring optimistic lock coupling.

Features

• High-throughput concurrent access using optimistic lock coupling
• Three access modes: Optimistic (non-blocking), Shared (read), Exclusive (write)
• Thread-safe (Send + Sync) when key and value types are thread-safe
• Epoch-based memory reclamation for safe concurrent access
• Bidirectional iteration with next() and prev()
• Range queries with configurable bounds
• Automatic node splitting and merging

Design

Ferntree is based on research from:

• LeanStore - Optimistic lock coupling for B-trees
• Umbra - High-performance database engine techniques

The key innovation is optimistic lock coupling: readers acquire "optimistic" access (no locks) and validate at the end that no concurrent modifications occurred. If validation fails, the operation retries automatically. This allows readers to proceed without blocking writers, and vice versa.

Quick start

use ferntree::Tree;

fn main() {
    let tree: Tree<String, i32> = Tree::new();

    // Insert key-value pairs
    tree.insert("apple".to_string(), 1);
    tree.insert("banana".to_string(), 2);
    tree.insert("cherry".to_string(), 3);

    // Lookup values using a closure
    let value = tree.lookup(&"banana".to_string(), |v| *v);
    assert_eq!(value, Some(2));

    // Convenience method for cloneable values
    let value = tree.get("apple");
    assert_eq!(value, Some(1));

    // Check existence
    assert!(tree.contains_key("cherry"));
    assert!(!tree.contains_key("durian"));

    // Remove entries
    let removed = tree.remove(&"banana".to_string());
    assert_eq!(removed, Some(2));

    // Tree statistics
    assert_eq!(tree.len(), 2);
    assert!(!tree.is_empty());
}

Concurrent usage

The tree is designed for high-concurrency workloads. Wrap it in an Arc to share across threads:

use ferntree::Tree;
use std::sync::Arc;
use std::thread;

fn main() {
    let tree = Arc::new(Tree::<i32, i32>::new());

    // Spawn multiple writer threads
    let handles: Vec<_> = (0..4).map(|t| {
        let tree = Arc::clone(&tree);
        thread::spawn(move || {
            for i in 0..1000 {
                tree.insert(t * 1000 + i, i);
            }
        })
    }).collect();

    for h in handles {
        h.join().unwrap();
    }

    assert_eq!(tree.len(), 4000);
}

Concurrent readers and writers can operate simultaneously:

use ferntree::Tree;
use std::sync::Arc;
use std::thread;

fn main() {
    let tree = Arc::new(Tree::<i32, i32>::new());

    // Pre-populate some data
    for i in 0..100 {
        tree.insert(i, i * 10);
    }

    let tree_writer = Arc::clone(&tree);
    let tree_reader = Arc::clone(&tree);

    // Writer thread adds new entries
    let writer = thread::spawn(move || {
        for i in 100..200 {
            tree_writer.insert(i, i * 10);
        }
    });

    // Reader thread performs lookups concurrently
    let reader = thread::spawn(move || {
        let mut found = 0;
        for i in 0..100 {
            if tree_reader.lookup(&i, |v| *v).is_some() {
                found += 1;
            }
        }
        found
    });

    writer.join().unwrap();
    let found = reader.join().unwrap();

    assert_eq!(found, 100); // Reader sees consistent data
}

Iterator usage

Ferntree provides several ways to iterate over entries:

use ferntree::Tree;
use std::ops::Bound::{Included, Excluded, Unbounded};

fn main() {
    let tree: Tree<i32, &str> = Tree::new();
    tree.insert(1, "one");
    tree.insert(2, "two");
    tree.insert(3, "three");
    tree.insert(4, "four");
    tree.insert(5, "five");

    // Raw iterator for manual control
    let mut iter = tree.raw_iter();
    iter.seek_to_first();
    while let Some((k, v)) = iter.next() {
        println!("{}: {}", k, v);
    }

    // Reverse iteration
    iter.seek_to_last();
    while let Some((k, v)) = iter.prev() {
        println!("{}: {}", k, v);
    }

    // Keys iterator
    let mut keys = tree.keys();
    assert_eq!(keys.next(), Some(&1));
    assert_eq!(keys.next(), Some(&2));

    // Values iterator
    let mut values = tree.values();
    assert_eq!(values.next(), Some(&"five")); // Sorted by key
    
    // Range queries
    let mut range = tree.range(Included(&2), Excluded(&5));
    assert_eq!(range.next(), Some((&2, &"two")));
    assert_eq!(range.next(), Some((&3, &"three")));
    assert_eq!(range.next(), Some((&4, &"four")));
    assert_eq!(range.next(), None);
}

Additional operations

use ferntree::Tree;

fn main() {
    let tree: Tree<i32, i32> = Tree::new();
    
    for i in 0..10 {
        tree.insert(i, i * 10);
    }

    // First and last entries
    let first = tree.first(|k, v| (*k, *v));
    assert_eq!(first, Some((0, 0)));

    let last = tree.last(|k, v| (*k, *v));
    assert_eq!(last, Some((9, 90)));

    // Pop operations (remove and return)
    let popped = tree.pop_first();
    assert_eq!(popped, Some((0, 0)));

    let popped = tree.pop_last();
    assert_eq!(popped, Some((9, 90)));

    // Get or insert (returns existing or inserts default)
    let value = tree.get_or_insert(100, 1000);
    assert_eq!(value, 1000);

    let value = tree.get_or_insert(1, 9999); // Key exists
    assert_eq!(value, 10); // Returns existing value

    // Clear all entries
    tree.clear();
    assert!(tree.is_empty());
}

API overview

Read operations:

• lookup(key, closure) - Look up a value, applying a closure to extract data
• get(key) - Get a cloned value (requires V: Clone)
• contains_key(key) - Check if a key exists
• first(closure) - Get the first (minimum) entry
• last(closure) - Get the last (maximum) entry
• len() - Number of entries
• is_empty() - Check if tree is empty
• height() - Current tree height

Write operations:

• insert(key, value) - Insert or update, returns old value if key existed
• remove(key) - Remove an entry, returns the value if it existed
• pop_first() - Remove and return the first entry
• pop_last() - Remove and return the last entry
• get_or_insert(key, default) - Get existing or insert default
• get_or_insert_with(key, closure) - Get existing or insert computed value
• clear() - Remove all entries

Iteration:

• raw_iter() - Low-level shared iterator with seek*, next(), prev()
• raw_iter_mut() - Low-level exclusive iterator for modifications
• keys() - Iterator over keys
• values() - Iterator over values
• range(min, max) - Iterator over a key range

Important notes

Closure execution: The closures passed to lookup(), first(), last(), etc. may be executed multiple times if concurrent modifications cause validation failures. Avoid side effects in these closures.

// Good: Pure closure that just extracts data
let value = tree.lookup(&key, |v| v.clone());

// Avoid: Side effects may execute multiple times
let mut counter = 0;
tree.lookup(&key, |v| { counter += 1; v.clone() }); // counter may be > 1

Thread safety: Tree<K, V> implements Send and Sync when both K and V implement Send + Sync. This means the tree can be safely shared across threads using Arc.

Memory reclamation: The tree uses epoch-based memory reclamation via crossbeam-epoch. Nodes removed from the tree are not immediately freed; they remain valid until all concurrent readers have finished. This ensures safe concurrent access without use-after-free bugs.

Original

This code is forked originally from bplustree, dual-licensed under the Apache 2.0 and MIT licenses.