Crate masstree 

MassTree

A concurrent ordered map based on a trie of B+trees.

This crate implements Masstree, combining tries and B+trees:

• Trie structure for variable-length key prefixes (8-byte chunks)
• B+tree at each trie node for the current 8-byte slice
• Cache-friendly: 8-byte key slices fit in registers

Status: v0.3.0 (Core Feature Complete)

All core operations implemented and tested. Not yet production-ready—concurrent data structures require extensive stress testing beyond what Miri and proptests provide.

Feature	Status
Concurrent get	Lock-free, version-validated
Concurrent insert	Fine-grained leaf locking
Concurrent remove	Fine-grained locking + lazy coalescing
Split propagation	Leaf and internode
Range scans	scan, scan_ref, scan_prefix, iterator
Memory reclamation	Seize-based epoch reclamation
Lazy leaf coalescing	Queue-based background cleanup

Not Yet Implemented

• Entry API (like std::collections::HashMap)
• DoubleEndedIterator (reverse iteration)
• Extend, FromIterator traits

Thread Safety

MassTree<V> is Send + Sync when V: Send + Sync. Concurrent access requires using the guard-based API:

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

The non-guard methods (get, insert) exist for convenience but require &mut self for insert, making them unsuitable for concurrent use.

Key Constraints

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

Design

Keys are split into 8-byte slices. Each slice is handled by a B+tree. When a key is longer than 8 bytes, the B+tree leaf points to another layer (another B+tree for the next 8 bytes).

Value Storage

• MassTree<V>: Stores values as Arc<V>. Returns Arc<V> on get.
• MassTreeIndex<V: Copy>: Convenience wrapper that copies values. Note: Currently wraps MassTree<V> internally; true inline storage is planned for a future release.

Feature Flags

tracing

Enables structured logging for debugging concurrent operations. See the crate-level documentation for details.

mimalloc

Uses mimalloc as the global allocator for improved performance.

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 permuter24::AtomicPermuter24;

pub use permuter24::Permuter24;

pub use permuter24::WIDTH_24;

pub use leaf15::LeafNode15;

pub use leaf15::WIDTH_15;

pub use leaf24::LeafNode24;

pub use leaf24::MODSTATE_DELETED_LAYER;

pub use leaf24::MODSTATE_INSERT;

pub use leaf24::MODSTATE_REMOVE;

pub use leaf24::WIDTH_24 as LEAF24_WIDTH;

pub use alloc15::SeizeAllocator15;

pub use alloc24::SeizeAllocator24;

pub use value::InsertTarget;

pub use value::LeafValue;

pub use value::LeafValueIndex;

pub use value::SplitPoint;

pub use link::is_marked;

pub use link::mark_ptr;

pub use link::unmark_ptr;

pub use ptr::NodePtr;

pub use slot::ValueSlot;

pub use suffix::InlineSuffixBag;

pub use suffix::PermutationProvider;

pub use suffix::SuffixBag;

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::MassTree24;

pub use tree::MassTree24Inline;

pub use tree::MassTreeGeneric;

pub use tree::MassTreeIndex;

pub use tree::BatchEntry;

pub use tree::BatchInsertResult;

pub use tree::batch;

Modules

alloc15

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

alloc24

Node allocation for LeafNode24 (WIDTH=24).

alloc_trait

Generic allocator trait for tree nodes.

internode

Filepath: src/internode.rs

key

Filepath: src/key.rs

ksearch

Key search algorithms for MassTree.

leaf15

Filepath: src/leaf15.rs

leaf24

Filepath: src/leaf24.rs

leaf_trait

Traits for abstracting over leaf node WIDTH variants.

link

Pointer marking utilities for concurrent split operations.

nodeversion

Filepath: src/nodeversion.rs

ordering

Standard memory orderings for concurrent node access.

permuter

Filepath: src/permuter.rs

permuter24

24-slot permutation using u128 storage.

prefetch

Software prefetching utilities for cache optimization.

ptr

Type-safe pointer wrappers for tree nodes.

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.

Functions

init_tracing

No-op when tracing feature is disabled.