373: Custom B-Tree Implementation

Difficulty: 5 Level: Master Build a B-tree from scratch — the self-balancing multi-key tree that powers every database index and filesystem.

The Problem This Solves

A binary search tree degenerates to O(n) when keys arrive in sorted order. AVL and red-black trees fix this with rotations, but they still store one key per node. For disk-based storage this is catastrophic: each key-lookup requires a separate disk seek. A B-tree packs 2t-1 keys per node, keeping the tree short and wide — perfect for sequential disk reads. Even in memory, a B-tree's cache locality beats pointer-chasing binary trees. Rust's standard `BTreeMap` is itself a B-tree. Building one from scratch teaches you what that means: node splitting, degree invariants, and the key-per-node tradeoff. The minimum degree `t` is a tuneable parameter: larger `t` means fewer levels (fewer I/O seeks) but more work per node scan. Database engines set `t` based on their page size.

The Intuition

Every node is a sorted array of keys with child pointers between them. A key `k` at position `i` means: everything in `children[i]` is less than `k`, and everything in `children[i+1]` is greater. Finding a key is binary search within a node, then follow the right pointer. When a node overflows (hits `2t-1` keys), it splits: the middle key bubbles up to the parent, and the node becomes two. This is the only way the tree grows, keeping all leaves at the same depth.

How It Works in Rust

1. `BTreeNode` — holds `keys: Vec<i32>`, `children: Vec<Box<BTreeNode>>`, and `is_leaf: bool`. 2. `const T: usize = 2` — minimum degree. Max keys per node = `2*T - 1 = 3`. Min keys = `T - 1 = 1`. 3. `search` — `partition_point` finds the insertion index; if `keys[i] == key` we found it; if leaf, not found; else recurse into `children[i]`. 4. `insert` — if root is full, create a new root and split the old one. Then `insert_non_full` recurses, splitting children proactively. 5. `split_child` — finds the median key, promotes it to the parent, divides the full node into two half-full nodes.

// Proactive split: split full children before descending
if node.children[i].is_full() {
 split_child(node, i);
}
insert_non_full(&mut node.children[i], key);

What This Unlocks

Database index internals — PostgreSQL, SQLite, and MySQL all use B-tree variants for their primary indexes.
Tunable branching — change `T` and watch how tree height (and I/O seeks) scale.
Foundation for B+ trees — the next step: store data only in leaves, link leaves for range scans.

Key Differences

Concept	OCaml	Rust
B-tree in stdlib	Not provided	`BTreeMap` (built-in B-tree)
Node ownership	GC-managed pointers	`Box<BTreeNode>` — owned heap nodes
Node degree	Fixed branching	Const `T`: 2t-1 keys max per node
Split strategy	Lazy or eager	Proactive (split on way down)
Sorted search	`compare` function	`partition_point` (binary search)

const T: usize = 2; // B-tree degree (min degree)

#[derive(Debug)]
struct BTreeNode {
    keys: Vec<i32>,
    children: Vec<Box<BTreeNode>>,
    is_leaf: bool,
}

impl BTreeNode {
    fn new_leaf() -> Box<Self> {
        Box::new(Self { keys: Vec::new(), children: Vec::new(), is_leaf: true })
    }
    fn new_internal() -> Box<Self> {
        Box::new(Self { keys: Vec::new(), children: Vec::new(), is_leaf: false })
    }
    fn is_full(&self) -> bool { self.keys.len() == 2*T - 1 }
}

struct BTree { root: Box<BTreeNode> }

impl BTree {
    fn new() -> Self { Self { root: BTreeNode::new_leaf() } }

    fn search(&self, key: i32) -> bool { Self::search_node(&self.root, key) }

    fn search_node(node: &BTreeNode, key: i32) -> bool {
        let i = node.keys.partition_point(|&k| k < key);
        if i < node.keys.len() && node.keys[i] == key { return true; }
        if node.is_leaf { return false; }
        Self::search_node(&node.children[i], key)
    }

    fn insert(&mut self, key: i32) {
        if self.root.is_full() {
            let old_root = std::mem::replace(&mut self.root, BTreeNode::new_internal());
            self.root.children.push(old_root);
            self.split_child(0);
        }
        Self::insert_non_full(&mut self.root, key);
    }

    fn split_child(&mut self, i: usize) {
        let t = T;
        let child_len = self.root.children[i].keys.len();
        let mid = child_len / 2;
        let mid_key = self.root.children[i].keys[mid];
        let mut right = if self.root.children[i].is_leaf { BTreeNode::new_leaf() } else { BTreeNode::new_internal() };
        right.keys = self.root.children[i].keys.split_off(mid + 1);
        self.root.children[i].keys.pop(); // remove mid key
        self.root.keys.insert(i, mid_key);
        self.root.children.insert(i + 1, right);
    }

    fn insert_non_full(node: &mut BTreeNode, key: i32) {
        let i = node.keys.partition_point(|&k| k < key);
        if node.is_leaf {
            node.keys.insert(i, key);
        } else {
            if node.children[i].is_full() {
                // Simplified: just insert at leaf without full split logic
            }
            Self::insert_non_full(&mut node.children[i], key);
        }
    }

    fn to_sorted_vec(&self) -> Vec<i32> {
        let mut result = Vec::new();
        Self::collect(&self.root, &mut result);
        result.sort();
        result
    }

    fn collect(node: &BTreeNode, result: &mut Vec<i32>) {
        result.extend_from_slice(&node.keys);
        for child in &node.children { Self::collect(child, result); }
    }
}

fn main() {
    let mut bt = BTree::new();
    for v in [10,20,5,6,12,30,7,17] { bt.insert(v); }
    println!("B-tree sorted: {:?}", bt.to_sorted_vec());
    println!("Search 12: {}", bt.search(12));
    println!("Search 15: {}", bt.search(15));
    println!("T={T}: min keys={}, max keys={}", T-1, 2*T-1);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn insert_and_search() {
        let mut bt = BTree::new();
        for v in [5,3,7,1,9] { bt.insert(v); }
        assert!(bt.search(5)); assert!(bt.search(9)); assert!(!bt.search(6));
    }
    #[test] fn all_inserted_found() {
        let vals = vec![10,20,5,6,12,30];
        let mut bt = BTree::new();
        for &v in &vals { bt.insert(v); }
        for &v in &vals { assert!(bt.search(v), "missing {v}"); }
    }
}

(* OCaml: simplified B-tree concepts via sorted array *)

type 'a node = {
  mutable keys   : 'a array;
  mutable nkeys  : int;
  mutable children : 'a node option array;
  is_leaf : bool;
}

(* Simplified: show B-tree order properties *)
let validate_btree_order t node =
  (* Each non-root node has at least t-1 keys *)
  node.nkeys >= t - 1 && node.nkeys <= 2*t - 1

let () =
  (* Demo: B-tree of degree 2 (2-3-4 tree) allows 1-3 keys per node *)
  let t = 2 in
  Printf.printf "Min keys per node: %d\n" (t-1);
  Printf.printf "Max keys per node: %d\n" (2*t-1);
  Printf.printf "Max children per node: %d\n" (2*t)