index-db 0.4.0

B+tree indexing primitive for Rust storage engines - ordered keys, range scans, and concurrent access over paged storage.
Documentation

Available now (v0.4.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 = "0.4"

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.

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.