Crate bplus_index 

Arena-backed B+Tree for in-memory sorted indexes.

BPlusIndex<K, V> is a sorted multimap where entries are (K, V) pairs. Multiple values per key are supported natively – the (K, V) pair is the unique identity of each entry. This makes it suitable for secondary indexes in data-oriented designs where one key maps to many row identifiers.

Design

• Arena storage: all nodes live in contiguous Vecs, indexed by u32 ids. No Box, no pointer chasing between siblings during range scans.
• Cache-friendly leaves: each leaf holds up to 64 keys and 64 values in inline ArrayVecs. Binary search within a leaf touches 1-2 cache lines.
• Linked leaves: leaves form a doubly-linked list for O(log n + k) range scans without climbing back up the tree.
• Zero unsafe: built on top of arrayvec which encapsulates all the MaybeUninit machinery.
• Non-unique key support: inner node separators store (K, V) tuples for correct routing even when thousands of entries share the same key.

Complexity

Operation	Time	Notes
insert	O(log n)	Amortized, with rare leaf/inner splits
delete	O(log n)	With borrow-or-merge rebalancing
update	O(log n)	Delete + insert
lookup_unique	O(log n)	Returns first value for a given key
lookup_range	O(log n + k)	All values for a given key
range	O(log n + k)	Arbitrary key range with bounds
iter	O(n)	Full scan via leaf chain

Example

use bplus_index::BPlusIndex;

let mut idx = BPlusIndex::<i32, u64>::new();

// Non-unique: multiple values for the same key
idx.insert(10, 100);
idx.insert(10, 200);
idx.insert(20, 300);

// Lookup all values for key 10
let vals: Vec<_> = idx.lookup_range(&10).copied().collect();
assert_eq!(vals, vec![100, 200]);

// Range scan
let entries: Vec<_> = idx.range(5..15).collect();
assert_eq!(entries.len(), 2);

Structs

BPlusIndex

An arena-backed B+Tree sorted multimap.

LookupRange

Iterator returned by BPlusIndex::lookup_range.

RangeIter

Iterator returned by BPlusIndex::range and BPlusIndex::iter.