Operations

Point Lookup

Single-key lookup navigates from root to leaf using binary search at each internal node, then binary searches the leaf's key array. Complexity: O(log n).

Insert with Auto-Split

Insertion finds the correct leaf and adds the key-value pair. When a leaf exceeds capacity (order - 1 keys), it splits at the midpoint: the right half becomes a new leaf and the median key is promoted to the parent. Internal nodes split the same way, propagating up to the root if needed.

Insert key into leaf
  ↓ leaf.keys.len() > max_keys (order - 1)?
  ↓ YES: split at midpoint
     Left leaf: keys[..mid], values[..mid]
     Right leaf: keys[mid..], values[mid..]
     Promote keys[mid] to parent
  ↓ Parent overflow? Split parent recursively
  ↓ Root splits? Create new root with single key

Delete with Merge/Redistribute

Deletion removes the key from its leaf. If the leaf underflows below the minimum (ceil((order-1)/2) keys), the tree first attempts to redistribute entries from a sibling. If redistribution isn't possible (sibling also at minimum), the nodes merge. Merges can cascade up to the root, reducing tree height.

Range Scans

Range queries navigate to the start leaf, then follow the next_leaf linked list until the upper bound is reached. No tree traversal is needed after finding the start position.

Bulk Loading

Pre-sorted data can be loaded bottom-up in a single pass, bypassing the insert-split cycle entirely. Leaf nodes are packed to capacity and linked, then internal levels are built from the leaf boundaries. This is significantly faster than repeated inserts for large datasets.

// Build tree from 10,000 sorted entries in one pass
let tree = BPlusTree::bulk_load(
    64, // order
    sorted_data.into_iter(),
);

Capacity Rules

All capacity limits are derived from the configurable order parameter (minimum 3). The order determines the maximum fan-out of internal nodes.

Concurrent Access

The ConcurrentBPlusTree wrapper provides thread-safe access via Arc<RwLock>. Multiple readers can access the tree concurrently; writers acquire an exclusive lock. Custom read/write closures are supported for complex operations.

pub struct ConcurrentBPlusTree<K, V> {
    inner: Arc<RwLock<BPlusTree<K, V>>>,
}

// Multiple concurrent readers
tree.get(&key);           // shared read lock
tree.range_to_vec(&a, &b); // shared read lock

// Exclusive writer
tree.insert(key, value);  // exclusive write lock
tree.remove(&key);        // exclusive write lock

Index Types Built on B+ Tree

The index manager uses B+ trees as the underlying structure for all index types in Anvil DB.

Prefix Scanning

The B+ tree supports prefix-based range scans for String and Vec<u8> keys via the PrefixBound trait. The trait computes the exclusive upper bound of a prefix range by incrementing the last non-0xFF byte.

// Find all keys starting with "usr_"
for (key, val) in tree.prefix_scan(&"usr_".to_string()) {
    // yields: "usr_001", "usr_002", "usr_alice", ...
}

// Internally computes: range("usr_", "usr]")
// where upper bound is "usr_" with last byte incremented

Test Coverage

The B+ tree implementation is covered by 51 tests across 2 modules, verifying correctness under sequential inserts, reverse inserts, large-scale operations (10,000 keys), and concurrent access.

Key Test Scenarios

Design Decisions