Crate masstree 

MassTree

A high-performance concurrent ordered map for Rust. Stores keys as &[u8] and supports variable-length keys by building a trie of B+trees.

Features

• Ordered map for byte keys (lexicographic ordering)
• Lock-free reads with version validation
• Concurrent inserts and deletes with fine-grained leaf locking
• Zero-copy range scans with scan_ref and scan_prefix
• Memory reclamation via epoch-based deferred cleanup
• Lazy leaf coalescing for deleted entries
• high-performance inline variant MassTree15Inline, all benchmark results are based on it.

Variant Selection

Variant	Best For
MassTree15	Range scans, writes, shared-prefix keys, contention
MassTree (WIDTH=24)	Random-access reads, single-threaded point ops

MassTree15 tends to perform better due to cheaper u64 atomics and better cache utilization. Consider it for most workloads.

use masstree::{MassTree, MassTree15, MassTree15Inline};

// Default: WIDTH=15 with inline storage (best for Copy types)
let tree: MassTree<u64> = MassTree::new();

// WIDTH=15, Arc-based storage (for non-Copy types like String)
let tree15: MassTree15<String> = MassTree15::new();

// Explicit inline variant
let inline15: MassTree15Inline<u64> = MassTree15Inline::new();

Quick Start

use masstree::MassTree;

let tree: MassTree<u64> = MassTree::new();
let guard = tree.guard();

// Insert
tree.insert_with_guard(b"hello", 123, &guard);

// Point lookup (lock-free)
assert_eq!(tree.get_ref(b"hello", &guard), Some(&123));

// Remove
tree.remove_with_guard(b"hello", &guard).unwrap();

// Range scan (zero-copy)
use masstree::RangeBound;
tree.scan_ref(RangeBound::Included(b"a"), RangeBound::Excluded(b"z"), |key, value| {
    println!("{:?} -> {}", key, value);
    true // continue scanning
}, &guard);

Thread Safety

MassTree<V> is Send + Sync when V: Send + Sync. Concurrent access requires using the guard-based API. The guard ties operations to an epoch for safe memory reclamation.

use masstree::MassTree;

let tree: MassTree<u64> = MassTree::new();
let guard = tree.guard();

// Concurrent get (lock-free)
let value = tree.get_with_guard(b"key", &guard);

// Concurrent insert (fine-grained locking)
let old = tree.insert_with_guard(b"key", 42, &guard);

Key Constraints

• Keys must be 0-256 bytes. Longer keys will panic.
• Keys are byte slices (&[u8]), not generic types.

Re-exports

pub use leaf_trait::TreeInternode;

pub use leaf_trait::TreeLeafNode;

pub use leaf_trait::TreePermutation;

pub use alloc_trait::NodeAllocatorGeneric;

pub use permuter::AtomicPermuter;

pub use permuter::AtomicPermuter15;

pub use permuter::Permuter;

pub use permuter::Permuter15;

pub use leaf15::LeafNode15;

pub use leaf15::MODSTATE_DELETED_LAYER;

pub use leaf15::MODSTATE_INSERT;

pub use leaf15::MODSTATE_REMOVE;

pub use leaf15::WIDTH_15;

pub use internode::InternodeNode;

pub use nodeversion::NodeVersion;

pub use alloc15::SeizeAllocator15;

pub use alloc15::SeizeAllocator15TrueInline;

pub use inline::bits::InlineBits;

pub use inline::leaf15_true::LeafNode15TrueInline;

pub use slot::true_inline::TrueInlineSlot;

pub use value::InsertTarget;

pub use value::LeafValue;

pub use value::LeafValueIndex;

pub use value::SplitPoint;

pub use link::Linker;

pub use ref_value_slot::RefValueSlot;

pub use slot::ValueSlot;

pub use suffix::InlineSuffixBag;

pub use suffix::PermutationProvider;

pub use suffix::SuffixBag;

pub use tree::InsertError;

pub use tree::RemoveError;

pub use tree::KeysIter;

pub use tree::RangeBound;

pub use tree::RangeIter;

pub use tree::ScanEntry;

pub use tree::ValuesIter;

pub use tree::MassTree;

pub use tree::MassTree15;

pub use tree::MassTree15Inline;

pub use tree::MassTreeGeneric;

pub use tree::BatchEntry;

pub use tree::BatchInsertResult;

pub use tree::batch;

Modules

alloc15

Node allocation for LeafNode15 with WIDTH=15 leaves and WIDTH=15 internodes.

alloc_trait

Generic allocator trait for tree nodes.

hints

Branch prediction hints for performance-critical paths.

inline

True-inline value storage for leaf nodes.

internode

Filepath: src/internode.rs

key

Filepath: src/key.rs

ksearch

Key search algorithms for MassTree.

leaf15

Filepath: src/leaf15.rs

leaf_trait

Traits for abstracting over leaf node WIDTH variants.

link

Pointer marking utilities for concurrent split operations.

node_pool

Thread-local node pools using size-class buckets.

nodeversion

Filepath: src/nodeversion.rs

ordering

Standard memory orderings for concurrent node access.

permuter

Filepath: src/permuter.rs

prefetch

Software prefetching utilities for cache optimization.

ref_value_slot

Marker trait for value slots that support reference returns.

slot

Value slot abstraction for crate::MassTree storage modes.

suffix

Filepath: src/suffix.rs

tree

Filepath: src/tree.rs MassTree - A high-performance concurrent trie of B+trees.

value

Value types for leaf node storage.

Structs

BatchedRetire

Batched retirement utilities.

FlushOnDrop

Guard that flushes the retirement batch on drop.

Functions

init_tracing

No-op when tracing feature is disabled.