Crate index_db 

index-db

A B+tree indexing primitive for storage engines: ordered keys mapped to values, with fast point lookups, laid out as a tree of fixed-fan-out nodes rather than on the heap one entry at a time.

The one public type is BPlusTree, an ordered map. Keys are kept sorted across the tree, so a lookup is a binary search at each level and the height grows only with the logarithm of the entry count. Beyond point operations it supports ordered iteration and range scans, forward and in reverse. The node layout — sorted keys packed into fixed-capacity arrays, internal nodes routing to children — is the same structure a storage engine persists as an on-disk index; this release keeps the tree in memory.

Example

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(42_u32, "answer");
index.insert(7, "lucky");

assert_eq!(index.get(&42), Some(&"answer"));
assert_eq!(index.get(&13), None);

// Ordered range scan.
let keys: Vec<_> = index.range(0..50).map(|(&k, _)| k).collect();
assert_eq!(keys, vec![7, 42]);

assert_eq!(index.remove(&7), Some("lucky"));
assert_eq!(index.len(), 1);

Scope

As of v0.3.0 the ordered-map surface is complete: search, insert, delete (with merge and redistribute), and forward and reverse range scans. Latch-coupled concurrent access lands in v0.4.0. See dev/ROADMAP.md.

Structs

BPlusTree

An ordered map backed by a B+tree.

Iter

A forward-and-reverse iterator over a BPlusTree’s entries in ascending key order, yielding (&K, &V).