index-db
_{^{B+TREE INDEXING PRIMITIVE}}

index-db is a B+tree indexing primitive for storage engines: ordered keys mapped to values, with fast point lookups and efficient range scans, laid out over paged storage rather than the heap.

Nodes are pages, so the tree persists and caches through a pager (it pairs with page-db), and it supports concurrent access via latch coupling (crabbing) so many readers and writers can traverse at once without locking the whole tree.

---

MSRV is 1.85+ (Rust 2024 edition). Ordered B+tree. Range scans. Latch-coupled concurrent access.

Status: 1.0 — stable, API frozen until 2.0. v1.0.0 is the stable in-memory ordered map — ordered storage, point lookups, deletion, forward and reverse range scans, and bulk construction from sorted input — hardened with adversarial, large-scale, and sustained soak tests. The tree is Sync, so any number of threads may read it at once. Node access runs through an internal storage seam so a page-backed, concurrent (write-side) backend over page-db arrives additively in a 1.x release without breaking this API. See dev/ROADMAP.md.

---

What it does

Available now (v1.0.0):

• Ordered B+tree — keys kept in sorted order; logarithmic point lookup, insert, and delete
• Self-balancing — nodes split on insert and borrow or merge on delete, so the tree stays balanced at every depth on its own
• Range scans — forward and reverse iteration over a key range, the operation B+trees exist for
• Bulk load — build a balanced tree bottom-up from sorted input in one fast pass
• Storage seam — nodes are addressed by id through an internal node store, so the same algorithm can later run over a paged, persistent backend
• no_std support — depends only on alloc; the std feature is optional

On the roadmap (see dev/ROADMAP.md):

• Page-backed, concurrent backend — nodes as page-db pages, with latch coupling (crabbing) over the pager's frame guards for many-reader / many-writer traversal. Concurrency is a property of the storage backend, not of the in-memory tree.

---

Installation

[dependencies]
index-db = "1"

Quick Start

use index_db::BPlusTree;

let mut index = BPlusTree::new();

// Insert key/value pairs in any order; the tree keeps them sorted.
index.insert(3_u32, "three");
index.insert(1, "one");
index.insert(2, "two");

// Point lookups return a reference to the value, or None.
assert_eq!(index.get(&2), Some(&"two"));
assert_eq!(index.get(&9), None);

// Re-inserting a key replaces and returns the old value.
assert_eq!(index.insert(1, "ONE"), Some("one"));

// Scan a key range in order (and in reverse).
let keys: Vec<_> = index.range(1..3).map(|(&k, _)| k).collect();
assert_eq!(keys, vec![1, 2]);

// Remove returns the value that was there.
assert_eq!(index.remove(&2), Some("two"));
assert_eq!(index.len(), 2);

Build a large index in one pass from sorted data:

use index_db::BPlusTree;

let index = BPlusTree::from_sorted((0..1_000_u32).map(|k| (k, k * k)));
assert_eq!(index.get(&30), Some(&900));
assert_eq!(index.len(), 1_000);

API Overview

For the complete reference with examples for every method, see docs/API.md. For benchmark baselines, see docs/PERFORMANCE.md.

Method	Purpose
BPlusTree::new	Create an empty tree
from_sorted	Bulk-build from sorted entries
insert	Insert or replace a key's value
get / contains_key	Point lookup / membership test
remove	Delete a key, returning its value
iter / range	Ordered iteration / range scan, forward or reverse
len / is_empty / height	Size and shape
clear	Remove every entry

---

Where It Fits

index-db is the ordered-index layer. It builds on / pairs with:

• page-db — B+tree nodes are pages allocated and cached by the pager
• lock-db — range locks protect scanned key ranges
• storage engines — the secondary-index and ordered-access structure above the pager
• lsm-db — a B-tree alternative to the LSM index for read-heavy workloads

It has no first-party dependencies, so it builds and tests standalone today.

Cross-Platform Support

Linux (x86_64, aarch64), macOS (x86_64, Apple Silicon), and Windows (x86_64) are first-class and verified by the CI matrix.

Contributing

See CONTRIBUTING.md and dev/DIRECTIVES.md. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.

License

Licensed under either of

• Apache License, Version 2.0 — LICENSE-APACHE
• MIT License — LICENSE-MIT

at your option.

^{COPYRIGHT © 2026 JAMES GOBER.}