B-Tree (ordered map) — Rust
Topics: B-tree, balanced search tree, ordered map, range scan
Problem
Implement a B-tree ordered map of minimum degree t — the balanced, high-fanout tree behind
database indexes and filesystems. Every node holds between t-1 and 2t-1 keys; the tree stays
balanced by splitting full nodes rather than rotating.
pub struct BTree { /* … */ }
impl BTree {
pub fn new(t: usize) -> Self;
pub fn get(&self, key: i32) -> Option<i32>;
pub fn insert(&mut self, key: i32, val: i32);
pub fn range(&self, lo: i32, hi: i32) -> Vec<(i32, i32)>; // ascending, lo <= key <= hi
}
insert adds or updates a key. The classic trick (CLRS): as you descend, split any full
child (2t-1 keys) before entering it — that guarantees there's always room — and split a full
root to grow the tree's height.get walks down comparing within each node.range returns the in-range pairs in ascending order (an in-order traversal).
Key concepts
- Index arena: the tree lives in a
Vec<Node> with child links as usize indices — O(1) links
without raw pointers or borrow-checker fights (alloc is provided).
- Split, don't rotate: a full node splits into two
t-1-key nodes with its median pushed up;
this keeps every leaf at the same depth. Vec::split_off makes the split clean.
- Why a B-tree: high fanout = shallow, cache-friendly trees, with ordered iteration for free.
The arena, new, and alloc are provided; you implement get, insert, and range.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.