Capstone: Build a Custom Collection
In this capstone you'll build a B-tree map from scratch. The project pulls together a hand-written Iterator, recursive ownership through boxed nodes, and idiomatic API design with a sketch of the entry pattern.
Why a B-Tree?
B-trees are self-balancing search trees tuned for storage with sluggish random access — disks, originally. Each node packs many keys, which slashes the cache-miss count compared to a plain binary search tree. The standard library's BTreeMap runs on one. Time to peek under the hood.
Node Structure
const ORDER: usize = 4; // Maximum children per nodeconst MAX_KEYS: usize = ORDER - 1;const MIN_KEYS: usize = ORDER / 2 - 1;
#[derive(Debug)]struct Node<K, V> { keys: Vec<K>, values: Vec<V>, children: Vec<Box<Node<K, V>>>, is_leaf: bool,}
impl<K: Ord, V> Node<K, V> { fn new_leaf() -> Self { Node { keys: Vec::with_capacity(MAX_KEYS), values: Vec::with_capacity(MAX_KEYS), children: Vec::new(), is_leaf: true, } }
fn new_internal() -> Self { Node { keys: Vec::with_capacity(MAX_KEYS), values: Vec::with_capacity(MAX_KEYS), children: Vec::with_capacity(ORDER), is_leaf: false, } }
fn is_full(&self) -> bool { self.keys.len() >= MAX_KEYS }
fn find_key_index(&self, key: &K) -> Result<usize, usize> { self.keys.binary_search(key) }}The BTreeMap
#[derive(Debug)]pub struct BTreeMap<K, V> { root: Option<Box<Node<K, V>>>, len: usize,}
impl<K: Ord, V> BTreeMap<K, V> { pub fn new() -> Self { BTreeMap { root: None, len: 0 } }
pub fn len(&self) -> usize { self.len }
pub fn is_empty(&self) -> bool { self.len == 0 }
pub fn get(&self, key: &K) -> Option<&V> { self.root.as_ref().and_then(|root| Self::search(root, key)) }
fn search<'a>(node: &'a Node<K, V>, key: &K) -> Option<&'a V> { match node.find_key_index(key) { Ok(idx) => Some(&node.values[idx]), Err(idx) => { if node.is_leaf { None } else { Self::search(&node.children[idx], key) } } } }}B-tree lookup is a recursive descent. At each node you binary-search the keys. Hit, and you've got the value. Miss, and the binary search hands you exactly the index of the child subtree to recurse into.
Insertion with Splitting
A full node splits before we insert into it:
impl<K: Ord, V> BTreeMap<K, V> { pub fn insert(&mut self, key: K, value: V) -> Option<V> { if self.root.is_none() { let mut node = Node::new_leaf(); node.keys.push(key); node.values.push(value); self.root = Some(Box::new(node)); self.len += 1; return None; }
// If root is full, split it first: the old root becomes the left child if self.root.as_ref().unwrap().is_full() { let mut old_root = self.root.take().unwrap(); let (median_key, median_val, right) = Self::split_node(&mut old_root); let mut new_root = Box::new(Node::new_internal()); new_root.keys.push(median_key); new_root.values.push(median_val); new_root.children.push(old_root); new_root.children.push(right); self.root = Some(new_root); }
let old_val = Self::insert_non_full(self.root.as_mut().unwrap(), key, value); if old_val.is_none() { self.len += 1; } old_val }
// Leaves the lower half in `node`; returns the median and the upper half fn split_node(node: &mut Node<K, V>) -> (K, V, Box<Node<K, V>>) { let mid = node.keys.len() / 2;
let mut right = if node.is_leaf { Box::new(Node::new_leaf()) } else { Box::new(Node::new_internal()) };
// Move upper half to right node right.keys = node.keys.split_off(mid + 1); right.values = node.values.split_off(mid + 1); if !node.is_leaf { right.children = node.children.split_off(mid + 1); }
let median_key = node.keys.pop().unwrap(); let median_val = node.values.pop().unwrap();
(median_key, median_val, right) }
fn insert_non_full(node: &mut Node<K, V>, key: K, value: V) -> Option<V> { match node.find_key_index(&key) { Ok(idx) => { // Key exists - replace value let old = std::mem::replace(&mut node.values[idx], value); Some(old) } Err(idx) => { if node.is_leaf { node.keys.insert(idx, key); node.values.insert(idx, value); None } else { // Descend into appropriate child if node.children[idx].is_full() { // Split child first; its median moves up to keys[idx] Self::split_child(node, idx); match key.cmp(&node.keys[idx]) { std::cmp::Ordering::Less => Self::insert_non_full(&mut node.children[idx], key, value), std::cmp::Ordering::Greater => Self::insert_non_full(&mut node.children[idx + 1], key, value), // The key we're inserting was the median that moved up std::cmp::Ordering::Equal => Some(std::mem::replace(&mut node.values[idx], value)), } } else { Self::insert_non_full(&mut node.children[idx], key, value) } } } } }
fn split_child(parent: &mut Node<K, V>, child_idx: usize) { // The left half stays where it is; only the median and right half move let (median_key, median_val, right) = Self::split_node(&mut parent.children[child_idx]); parent.keys.insert(child_idx, median_key); parent.values.insert(child_idx, median_val); parent.children.insert(child_idx + 1, right); }}Trace it with ORDER = 4 (at most three keys per node) and the keys 10 to 60 inserted in order. Inserting 40 finds the root full, so insert calls split_node on it: mid is 1, 30 moves into the new right node, 20 is popped as the median and becomes the new root. Inserting 50 just fills the right leaf. Inserting 60 descends, finds that leaf full, and split_child promotes its median, 40, into the parent before 60 goes into the new right-hand leaf:
Notice that the tree only ever grows at the top. The root split is the one place a new level appears, which is why every leaf stays at the same depth.
Implementing Iterator
An in-order walk yields keys left-to-right:
pub struct Iter<'a, K, V> { stack: Vec<(&'a Node<K, V>, usize)>,}
impl<K: Ord, V> BTreeMap<K, V> { pub fn iter(&self) -> Iter<'_, K, V> { let mut iter = Iter { stack: Vec::new() }; if let Some(ref root) = self.root { iter.push_left(root); } iter }}
impl<'a, K, V> Iter<'a, K, V> { fn push_left(&mut self, mut node: &'a Node<K, V>) { loop { self.stack.push((node, 0)); if node.is_leaf || node.children.is_empty() { break; } node = &node.children[0]; } }}
impl<'a, K: Ord, V> Iterator for Iter<'a, K, V> { type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> { loop { // Copy the top entry out so we don't hold a borrow of the stack let (node, idx) = match self.stack.last() { Some(&(node, idx)) => (node, idx), None => return None, }; if idx < node.keys.len() { self.stack.last_mut().unwrap().1 += 1;
// If internal node, push left spine of the child after this key if !node.is_leaf { self.push_left(&node.children[idx + 1]); }
return Some((&node.keys[idx], &node.values[idx])); } self.stack.pop(); } }}Entry API
In the standard library the entry API sidesteps the classic double lookup when you want insert-or-update: entry() searches once and the entry it returns remembers where in the tree the key lives (or would go). The sketch below gets the types right but cheats on that point. It does a lookup in entry() and the entry methods would do another, which is enough to show the shape of the API:
pub struct OccupiedEntry<'a, K, V> { map: &'a mut BTreeMap<K, V>, key: K,}
pub struct VacantEntry<'a, K, V> { map: &'a mut BTreeMap<K, V>, key: K,}
pub enum Entry<'a, K, V> { Occupied(OccupiedEntry<'a, K, V>), Vacant(VacantEntry<'a, K, V>),}
impl<K: Ord, V> BTreeMap<K, V> { pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { // Simplified: std stores a handle to the node and slot instead of // the map and key, so the methods below don't search again if self.get(&key).is_some() { Entry::Occupied(OccupiedEntry { map: self, key }) } else { Entry::Vacant(VacantEntry { map: self, key }) } }}
impl<'a, K: Ord, V> VacantEntry<'a, K, V> { pub fn insert(self, value: V) { // Second lookup: the price of the shortcut self.map.insert(self.key, value); }}Testing
#[cfg(test)]mod tests { use super::*;
#[test] fn test_insert_and_get() { let mut map = BTreeMap::new(); map.insert(3, "three"); map.insert(1, "one"); map.insert(2, "two");
assert_eq!(map.get(&1), Some(&"one")); assert_eq!(map.get(&2), Some(&"two")); assert_eq!(map.get(&3), Some(&"three")); assert_eq!(map.get(&4), None); assert_eq!(map.len(), 3); }
#[test] fn test_iteration_order() { let mut map = BTreeMap::new(); for i in (0..100).rev() { map.insert(i, i * 10); }
let keys: Vec<_> = map.iter().map(|(k, _)| *k).collect(); assert_eq!(keys, (0..100).collect::<Vec<_>>()); }}The runner has the whole map in one file, with both tests folded into main alongside a third: 1,000 pseudo-random inserts checked against the standard library's BTreeMap. The two constructors are merged into one Node::new(is_leaf), and there's a height() so you can see the shape of the tree.
What You Built
This B-tree map demonstrates:
- Advanced trait implementation: a hand-written Iterator over borrowed nodes
- Recursive data structures with Box
- Ownership and borrowing through tree navigation
- The entry API pattern used throughout the standard library
- Self-balancing through node splitting
B-trees are notoriously fiddly to get right in Rust. Ownership rules make you spell out, every step of the way, who owns which node and how a mutation ripples through the tree.