bplus-index

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

Designed for data-oriented architectures where you need secondary indexes on tables backed by slotmaps or ECS-style storage. Supports non-unique keys natively -- the (K, V) pair is the unique identity of each entry.

Features

• Arena storage -- all nodes live in contiguous Vecs indexed by u32. No Box, no heap allocation per node, no pointer chasing between siblings.
• Cache-friendly -- each leaf holds up to 64 entries in inline ArrayVecs. Range scans follow a doubly-linked leaf chain with sequential memory access.
• Non-unique keys -- first-class support for one-to-many and many-to-many secondary indexes. Inner node separators store (K, V) for correct routing.
• Zero unsafe -- built on arrayvec. No raw pointer manipulation.
• Minimal API -- insert, delete, update, lookup_unique, lookup_range, range, iter. One struct covers unique, 1:N, and N:N indexes depending on the choice of K and V.

Complexity

Where n is the total number of entries and k is the number of results.

Usage

[dependencies]
bplus-index = "0.1"

Unique index

use bplus_index::BPlusIndex;

let mut idx = BPlusIndex::<u64, u32>::new();
idx.insert(42, 1001); // key=42, row_id=1001

assert_eq!(idx.lookup_unique(&42), Some(&1001));

Non-unique 1:N index

use bplus_index::BPlusIndex;

// One score -> many player ids
let mut idx = BPlusIndex::<i32, u64>::new();
idx.insert(1500, 1);
idx.insert(1500, 2);
idx.insert(1500, 3);

let players: Vec<_> = idx.lookup_range(&1500).copied().collect();
assert_eq!(players, vec![1, 2, 3]);

Composite key for N:N index

use bplus_index::BPlusIndex;

// (game_mode, mmr) -> ticket_id
let mut idx = BPlusIndex::<(u8, i32), u64>::new();
idx.insert((1, 1200), 100);
idx.insert((1, 1350), 101);
idx.insert((1, 1400), 102);
idx.insert((2, 1300), 103);

// Range scan: mode 1, mmr 1200..1400
let tickets: Vec<_> = idx.range((1, 1200)..(1, 1400))
    .map(|(_, id)| *id)
    .collect();
assert_eq!(tickets, vec![100, 101]);

Update (re-index)

use bplus_index::BPlusIndex;

let mut idx = BPlusIndex::<i32, u64>::new();
idx.insert(1500, 42);

// Player 42's score changed from 1500 to 1600
idx.update(&1500, 1600, 42);

assert_eq!(idx.lookup_unique(&1500), None);
assert_eq!(idx.lookup_unique(&1600), Some(&42));

Benchmarks

Compared against std::collections::BTreeMap with i64 keys and u64 values, random insertion order.

Measured on Intel Core i7-10870H (8C/16T, 2.20 GHz) running Fedora Linux 43. Run with cargo bench.

Range scans and full iteration show the largest gains (3x) thanks to the linked leaf chain and sequential memory layout.

Lookups benefit from the flat arena reducing cache misses during descent (2x at scale).

Deletes are roughly on par since rebalancing logic dominates over memory access patterns

Design notes

Why not BTreeMap?

BTreeMap is a B-Tree (not B+Tree) -- values are stored in both leaf and internal nodes, and there is no leaf chain. Range scans require climbing back up the tree to visit the next subtree. Each node is a separate heap allocation, so sibling traversal involves pointer chasing.

BPlusIndex stores values only in leaves, which are linked for O(1) sibling traversal. Nodes live in flat Vecs for better memory locality.

Why (K, V) separators in inner nodes?

Standard B+Trees use K-only separators, which breaks down when the same key appears in multiple leaves. A query for key K would descend into one subtree and miss entries in adjacent subtrees. By using (K, V) as the separator, the routing is always unambiguous regardless of key cardinality.

Node recycling

Deleted nodes are not deallocated. Their indices are pushed onto a free list and reused by subsequent allocations. This avoids Vec fragmentation and keeps arena indices stable.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.