I've spent the last hour staring at a binary search tree implementation, and frankly, I'm bored. BSTs are great for textbooks, but in the real world—especially when we're talking about disk I/O or massive datasets—they're too deep. We need something wider. That's where the B-Tree comes in. Instead of two children, we're going to give our nodes a whole handful. Let's try to build one from scratch and see where we hit a wall.

The Initial Structural Guess

My first instinct is to keep it simple. A B-Tree node needs to hold multiple keys and multiple children. Since we don't know the exact number of children at compile time (though we have a maximum degree $M$), a Vec feels like the right call. I'll start by defining a node that can hold keys and values.

struct Node<K, V> {
    keys: Vec<K>,
    values: Vec<V>,
    children: Vec<Node<K, V>>,
    is_leaf: bool,
}

Wait. I just realized something. If I use Vec<Node<K, V>>, I've just created an infinite-size type. Rust will scream at me because the compiler can't determine the size of Node at compile time. I need an indirection. I'll wrap the children in a Box, or better yet, just make the children vector hold Box<Node<K, V>>.

struct Node<K, V> {
    keys: Vec<K>,
    values: Vec<V>,
    children: Vec<Box<Node<K, V>>,
    is_leaf: bool,
}

The "Too Many Keys" Problem

Now, the core rule of a B-Tree: every node (except the root) must have between $t-1$ and $2t-1$ keys, where $t$ is the minimum degree. Let's say $t=3$. That means a node is "full" when it hits 5 keys. I tried writing a simple insert method that just pushes a key into the Vec and sorts it. It worked for the first few elements, but then I hit the limit.

If I just keep pushing keys into a full node, it's no longer a B-Tree; it's just a weirdly shaped list. I need a way to "split" the node. When a node exceeds $2t-1$, the median key needs to move up to the parent, and the remaining keys need to be split into two new sibling nodes.

I tried implementing the split after the insertion, but I ran into a nightmare with the borrow checker. I was trying to mutate the parent while holding a mutable reference to the child. In Rust, you can't have two mutable references to different parts of the same tree structure easily if you're traversing downward.

Proactive Splitting

I realized I was fighting the language because my strategy was reactive. Instead of inserting and then fixing the mess, I should split full nodes on the way down. If I encounter a full node while searching for the insertion point, I split it immediately. By the time I actually reach the leaf where the key belongs, I'm guaranteed to have room.

Here is the logic I'm sketching out for the split:

• Take the middle element of the full node.
• Create a new node for the right-hand side of the split.
• Move the upper half of the keys and children to this new node.
• Push the middle element up into the parent's key vector.
• Add the new node to the parent's children vector.

This feels much cleaner. Now, the parent always has space to accommodate the promoted key because we're splitting the parent before we ever descend into the child.

Dealing with the Root

There's one edge case that tripped me up: what happens if the root itself is full? The root doesn't have a parent to promote a key to. I tried calling my split_child method on the root, and it crashed because it was looking for a parent that didn't exist.

The solution is a bit counter-intuitive. When the root is full, we create a new root. This new root starts with zero keys and one child (the old root). Then, we split that old root. This is the only way the B-Tree grows in height—from the top down, not the bottom up. It's a strange feeling, but it's what keeps the tree perfectly balanced.

if root.keys.len() == (2 * t) - 1 {
    let mut new_root = Node::new(false);
    let old_root = std::mem::replace(&mut self.root, Box::new(new_root));
    self.root.children.push(old_root);
    self.split_child(0);
}

Using std::mem::replace here is a lifesaver. It allows me to swap the old root out of the structure so I can manipulate it without the borrow checker thinking I'm trying to mutate the tree while I'm still holding onto the root.

📋 Practical Task

Exercise: Implementing the B-Tree Node Split

You are provided with a partial implementation of a B-Tree where the Node struct and the BTree wrapper are already defined. Your task is to implement the split_child method.

Requirements:

• The method split_child(&mut self, child_idx: usize) should take the node at children[child_idx] (which is guaranteed to be full) and split it.
• The median key must be moved up into the current node's keys vector at the correct index.
• A new sibling node must be created to hold the keys and children to the right of the median.
• The new sibling must be inserted into the current node's children vector.
• Ensure that the is_leaf property of the new sibling matches the original child.

Starter Code Hint:

impl<K: Ord, V> BTree<K, V> {
    fn split_child(&mut self, parent: &mut Node<K, V>, child_idx: usize) {
        let t = self.t;
        // Your implementation here:
        // 1. Identify the child to split
        // 2. Create the new sibling node
        // 3. Move the right-half of keys/children to the sibling
        // 4. Promote the median key to the parent
        // 5. Update parent's children vector
    }
}