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
• Range scans with scan and scan_prefix
• Memory reclamation via epoch-based deferred cleanup
• Lazy leaf coalescing for deleted entries
• High-performance inline variant MassTree15Inline (the default MassTree alias)

Quick Start

use masstree::{MassTree, RangeBound};

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

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

// Point lookup (lock-free, returns copy for inline storage)
assert_eq!(tree.get_with_guard(b"hello", &guard), Some(123));

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

// Range scan
tree.scan(RangeBound::Included(b"a"), RangeBound::Excluded(b"z"), |_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.

Modules

batch

Batch insert utilities and helpers.

Structs

AtomicPermuter

Atomic wrapper for Permuter<WIDTH> where WIDTH <= 15.

BatchEntry

A single entry in a batch insert operation.

BatchInsertResult

Result of a batch insert operation.

BatchedRetire

Value retirement utilities.

BoxPolicy

Box-based value storage with lazy sidecar suffix.

InternodeNode

An internal routing node in the MassTree.

Key

A key for crate::MassTree operations.

KeysIter

Iterator adapter that yields only keys.

LeafNode15

B-link leaf node with 15 slots, parameterized over LeafPolicy.

MassTreeGeneric

A high-performance generic trie of B+trees.

NodeVersion

A versioned lock for tree nodes.

OccupiedEntry

A view into an occupied entry in a tree.

Permuter

A permutation of slot indices for a leaf node.

RangeIter

Iterator over a key range in a crate::MassTree.

ScanEntry

Contains an owned copy of the key and the value output.

SeizeAllocator

Unified seize-based allocator for all leaf policies.

SuffixBag

Contiguous storage for key suffixes.

VacantEntry

A view into a vacant entry in a tree.

ValuePtr

A lightweight, Copy pointer to a heap-allocated value.

ValuesIter

Iterator adapter that yields only values.

Enums

Entry

A view into a single entry in a tree, which may either be vacant or occupied.

InsertError

Errors that can occur during insert operations.

RangeBound

Range bound for scan operations.

RemoveError

Errors that can occur during removal.

ValueRef

Cow-like value handle: either a borrowed reference or an owned copy.

Constants

IKEY_SIZE

Size of an ikey in bytes.

MAX_KEY_LENGTH

Maximum supported key length in bytes (32 layers * 8 bytes).

MAX_WIDTH

Maximum allowed WIDTH for u64 permuter encoding.

Traits

InlineBits

Trait for values that can be stored inline as 64 bits.

LeafPolicy

Bundles value storage, suffix storage, and type conversion for a leaf node.

PermutationProvider

Trait for types that can provide permutation information.

RefLeafPolicy

Marker trait for policies that support zero-copy reference returns.

TreeAllocator

Trait for allocating and deallocating tree nodes generically.

TreeInternode

Trait for internode types used in a MassTree.

TreeLeafNode

Trait for abstracting over leaf node WIDTH variants.

TreePermutation

Trait for permutation types used in leaf nodes.

Functions

init_tracing

No-op when the tracing feature is disabled.

Type Aliases

AtomicPermuter15

Type alias for the standard 15-slot atomic permuter.

MassTree

High-performance inline storage variant for Copy types (default tree type).

MassTree15

Box-based storage for non-Copy types (String, Vec, etc.).

MassTree15Inline

True-inline storage for Copy types (u64, i32, *const T, etc.).

Permuter15

Type alias for standard 15-slot permuter.