Interview Guide: B-Trees Problems and Solutions

Understanding B-Trees

A B-tree is a self-balancing search tree that maintains sorted data and allows operations in logarithmic time. Unlike binary search trees, each node in a B-tree can store more than one key and have more than two children. The tree is characterized by its order M, which defines the maximum number of children a node can have. For a B-tree of order M:

• Every node contains at most M-1 keys and at most M child pointers.
• Every internal node (except the root) contains at least ceil(M/2) - 1 keys and at least ceil(M/2) children.
• The root has at least 1 key if the tree is non-empty, and at least 2 children if it is not a leaf.
• All leaves appear at the same level, guaranteeing perfect balance.

B-trees were designed to minimize disk I/O operations. By packing many keys into a single node and having a high branching factor, the height remains low, drastically reducing the number of node accesses. Variants like the B+ tree store all data in leaf nodes and chain them together for efficient range scans, and are widely used in database indexing engines and file systems.

Why B-Trees Matter in Interviews

Interviewers use B-tree problems to probe deeper than standard binary tree knowledge. They evaluate your understanding of data structures that underpin real-world systems like databases and file storage. Solving B-tree problems demonstrates:

• Mastery of multi-way search trees and their balancing mechanics.
• Ability to design node structures with dynamic arrays and child pointers.
• Comfort with recursive split/merge algorithms during insertion and deletion.
• Knowledge of disk-based vs memory-based performance trade-offs.
• Familiarity with B+ tree optimizations and why they are preferred in databases.

Typical interview challenges include implementing search, insertion, and deletion; explaining maximum key counts given an order; comparing B-trees with B+ trees; and reasoning about the time complexity of operations in terms of node accesses.

Common Interview Problems

• Implement a B-tree insert that maintains all properties after insertion.
• Delete a key from a B-tree, handling leaf deletion, borrowing from siblings, and merging.
• Given an order M, compute the minimum and maximum number of keys in an internal node.
• Explain how a B+ tree improves range query performance over a B-tree.
• Simulate a sequence of insertions and deletions, drawing the tree after each step.
• Design a file-system block allocator using a B-tree structure.

How to Approach B-Tree Problems

The key to solving B-tree problems successfully is to first nail down the definition and then systematically handle each operation. Below is a step-by-step methodology.

Step 1: Clarify the Definition

Always confirm the exact definition of order with the interviewer. Some texts define order as the maximum number of keys per node (d), with children at most d+1. Others use maximum children (M) as the order. The safest approach is to state your chosen convention explicitly and stick to it. In this guide, we use M = maximum children per node, so max keys = M-1, and minimum children for internal nodes (except root) = ceil(M/2), minimum keys = ceil(M/2) - 1. For example, an order-5 B-tree has nodes with 2 to 4 keys and 3 to 5 children (except root which may have fewer).

Step 2: Design the Node Structure

A node needs arrays for keys and children. A boolean leaf flag simplifies logic. Keys are kept sorted, and children interleave keys: child i holds values less than key i, child i+1 holds values greater than key i.

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []          # list of keys (integers or comparable)
        self.children = []      # list of BTreeNode references

Step 3: Implement Core Operations

Search

Search follows a multi-way decision path. Within a node, perform binary search (or linear scan) to find the smallest index i where the search key is less than or equal to keys[i]. If the key matches, return the node and index. If the key is not found and the node is a leaf, return failure. Otherwise, recurse into children[i] (or children[i+1] depending on equality). The time complexity is O(log_M n) node accesses.

def search(self, key, node=None):
    if node is None:
        node = self.root
    if node is None:
        return None
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    if i < len(node.keys) and key == node.keys[i]:
        return (node, i)
    if node.leaf:
        return None
    return self.search(key, node.children[i])

Insertion

Insertion always happens at a leaf. The algorithm pre-splits any full node encountered along the search path (root included), ensuring that a parent never needs to accept a new key from a child that is already full. When a node is full (keys count = M-1), it is split into two nodes around the median key. The median moves up to the parent. If the root splits, a new root is created, increasing the tree height.

def insert(self, key):
    root = self.root
    if root is None:
        self.root = BTreeNode(leaf=True)
        self.root.keys.append(key)
        return
    
    # If root is full, split root first
    if len(root.keys) == self.max_keys():
        new_root = BTreeNode()
        new_root.children.append(root)
        self._split_child(new_root, 0)
        self.root = new_root
    
    self._insert_non_full(self.root, key)

def _insert_non_full(self, node, key):
    i = len(node.keys) - 1
    if node.leaf:
        node.keys.append(None)  # placeholder, will shift
        while i >= 0 and key < node.keys[i]:
            node.keys[i+1] = node.keys[i]
            i -= 1
        node.keys[i+1] = key
    else:
        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        if len(node.children[i].keys) == self.max_keys():
            self._split_child(node, i)
            if key > node.keys[i]:
                i += 1
        self._insert_non_full(node.children[i], key)

def _split_child(self, parent, index):
    child = parent.children[index]
    split_pos = len(child.keys) // 2
    median_key = child.keys[split_pos]
    
    # Create new node (same leaf status as child)
    new_node = BTreeNode(leaf=child.leaf)
    new_node.keys = child.keys[split_pos+1:]
    child.keys = child.keys[:split_pos]
    
    if not child.leaf:
        new_node.children = child.children[split_pos+1:]
        child.children = child.children[:split_pos+1]
    
    parent.keys.insert(index, median_key)
    parent.children.insert(index+1, new_node)

Deletion

Deletion is more intricate. It must ensure that every node (except the root) retains at least the minimum number of keys. The algorithm handles three major cases:

• Key in leaf: simply remove it if the leaf has enough keys; otherwise, rebalance by borrowing from a sibling or merging.
• Key in internal node: replace the key with its predecessor (largest key in the left subtree) or successor (smallest key in the right subtree), and then delete the predecessor/successor from the leaf.
• Underflow: when a node ends up with fewer than the minimum keys, attempt to borrow from an immediate sibling with surplus keys (rotating a key through the parent), or merge with a sibling, pulling down a key from the parent.

The code below implements deletion for a B-tree of order M, with helper functions for borrowing and merging.

def delete(self, key):
    if self.root is None:
        return
    self._delete(self.root, key)
    # If root became empty after merge, shrink tree
    if len(self.root.keys) == 0 and not self.root.leaf:
        self.root = self.root.children[0]

def _delete(self, node, key):
    # Find position of key or subtree to descend
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    
    # Case 1: key found in this node
    if i < len(node.keys) and node.keys[i] == key:
        if node.leaf:
            # Simple leaf removal
            node.keys.pop(i)
        else:
            # Replace with predecessor or successor
            if len(node.children[i].keys) >= self.min_keys():
                pred_key = self._get_predecessor(node.children[i])
                node.keys[i] = pred_key
                self._delete(node.children[i], pred_key)
            elif len(node.children[i+1].keys) >= self.min_keys():
                succ_key = self._get_successor(node.children[i+1])
                node.keys[i] = succ_key
                self._delete(node.children[i+1], succ_key)
            else:
                # Merge children[i] and children[i+1], then delete key from merged node
                self._merge_nodes(node, i)
                self._delete(node.children[i], key)
        return
    
    # Case 2: key not in this node, must descend
    if node.leaf:
        return  # key not present
    
    # Ensure the child we are about to descend into has enough keys
    child = node.children[i]
    if len(child.keys) < self.min_keys():
        self._fix_child(node, i)
    self._delete(node.children[i], key)

def _get_predecessor(self, node):
    while not node.leaf:
        node = node.children[-1]
    return node.keys[-1]

def _get_successor(self, node):
    while not node.leaf:
        node = node.children[0]
    return node.keys[0]

def _fix_child(self, parent, index):
    child = parent.children[index]
    left_sibling = parent.children[index-1] if index > 0 else None
    right_sibling = parent.children[index+1] if index < len(parent.children)-1 else None
    
    # Try to borrow from left sibling
    if left_sibling and len(left_sibling.keys) > self.min_keys():
        # Rotate a key from left sibling through parent
        child.keys.insert(0, parent.keys[index-1])
        parent.keys[index-1] = left_sibling.keys.pop()
        if not child.leaf:
            child.children.insert(0, left_sibling.children.pop())
    # Try to borrow from right sibling
    elif right_sibling and len(right_sibling.keys) > self.min_keys():
        child.keys.append(parent.keys[index])
        parent.keys[index] = right_sibling.keys.pop(0)
        if not child.leaf:
            child.children.append(right_sibling.children.pop(0))
    # Merge with a sibling
    else:
        if left_sibling:
            self._merge_nodes(parent, index-1)
        else:
            self._merge_nodes(parent, index)

def _merge_nodes(self, parent, index):
    left = parent.children[index]
    right = parent.children[index+1]
    # Pull parent key down into left node
    left.keys.append(parent.keys.pop(index))
    left.keys.extend(right.keys)
    if not left.leaf:
        left.children.extend(right.children)
    parent.children.pop(index+1)

def min_keys(self):
    return (self.M // 2) - 1 if self.M % 2 == 0 else self.M // 2

def max_keys(self):
    return self.M - 1

Complete Python Implementation Example

Below is a full, runnable B-tree class in Python (order M=5 by default). It integrates search, insertion, deletion, and a demonstration. You can use it as a foundation for interview practice.

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.children = []

class BTree:
    def __init__(self, order=5):
        self.M = order
        self.root = None
    
    def min_keys(self):
        return (self.M // 2) - 1 if self.M % 2 == 0 else self.M // 2
    
    def max_keys(self):
        return self.M - 1
    
    def search(self, key, node=None):
        if node is None:
            node = self.root
        if node is None:
            return None
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            return (node, i)
        if node.leaf:
            return None
        return self.search(key, node.children[i])
    
    def insert(self, key):
        root = self.root
        if root is None:
            self.root = BTreeNode(leaf=True)
            self.root.keys.append(key)
            return
        if len(root.keys) == self.max_keys():
            new_root = BTreeNode()
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_non_full(self.root, key)
    
    def _insert_non_full(self, node, key):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i+1] = node.keys[i]
                i -= 1
            node.keys[i+1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == self.max_keys():
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)
    
    def _split_child(self, parent, index):
        child = parent.children[index]
        split_pos = len(child.keys) // 2
        median_key = child.keys[split_pos]
        new_node = BTreeNode(leaf=child.leaf)
        new_node.keys = child.keys[split_pos+1:]
        child.keys = child.keys[:split_pos]
        if not child.leaf:
            new_node.children = child.children[split_pos+1:]
            child.children = child.children[:split_pos+1]
        parent.keys.insert(index, median_key)
        parent.children.insert(index+1, new_node)
    
    def delete(self, key):
        if self.root is None:
            return
        self._delete(self.root, key)
        if len(self.root.keys) == 0 and not self.root.leaf:
            self.root = self.root.children[0]
    
    def _delete(self, node, key):
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            if node.leaf:
                node.keys.pop(i)
            else:
                if len(node.children[i].keys) >= self.min_keys():
                    pred_key = self._get_predecessor(node.children[i])
                    node.keys[i] = pred_key
                    self._delete(node.children[i], pred_key)
                elif len(node.children[i+1].keys) >= self.min_keys():
                    succ_key = self._get_successor(node.children[i+1])
                    node.keys[i] = succ_key
                    self._delete(node.children[i+1], succ_key)
                else:
                    self._merge_nodes(node, i)
                    self._delete(node.children[i], key)
            return
        if node.leaf:
            return
        child = node.children[i]
        if len(child.keys) < self.min_keys():
            self._fix_child(node, i)
        self._delete(node.children[i], key)
    
    def _get_predecessor(self, node):
        while not node.leaf:
            node = node.children[-1]
        return node.keys[-1]
    
    def _get_successor(self, node):
        while not node.leaf:
            node = node.children[0]
        return node.keys[0]
    
    def _fix_child(self, parent, index):
        child = parent.children[index]
        left_sibling = parent.children[index-1] if index > 0 else None
        right_sibling = parent.children[index+1] if index < len(parent.children)-1 else None
        if left_sibling and len(left_sibling.keys) > self.min_keys():
            child.keys.insert(0, parent.keys[index-1])
            parent.keys[index-1] = left_sibling.keys.pop()
            if not child.leaf:
                child.children.insert(0, left_sibling.children.pop())
        elif right_sibling and len(right_sibling.keys) > self.min_keys():
            child.keys.append(parent.keys[index])
            parent.keys[index] = right_sibling.keys.pop(0)
            if not child.leaf:
                child.children.append(right_sibling.children.pop(0))
        else:
            if left_sibling:
                self._merge_nodes(parent, index-1)
            else:
                self._merge_nodes(parent, index)
    
    def _merge_nodes(self, parent, index):
        left = parent.children[index]
        right = parent.children[index+1]
        left.keys.append(parent.keys.pop(index))
        left.keys.extend(right.keys)
        if not left.leaf:
            left.children.extend(right.children)
        parent.children.pop(index+1)
    
    def print_tree(self, node=None, level=0):
        if node is None:
            node = self.root
        if node is None:
            print("Empty tree")
            return
        print("  " * level + f"Node(leaf={node.leaf}) keys={node.keys}")
        for child in node.children:
            self.print_tree(child, level+1)

# Demonstration
if __name__ == "__main__":
    b = BTree(order=5)  # max 4 keys per node
    for val in [10, 20, 5, 6, 12, 30, 7, 17, 3, 8, 11, 14, 25, 19, 22]:
        b.insert(val)
    print("After insertions:")
    b.print_tree()
    print("\nSearch for 12:", b.search(12))
    b.delete(6)
    print("\nAfter deleting 6:")
    b.print_tree()
    b.delete(30)
    print("\nAfter deleting 30:")
    b.print_tree()

Best Practices for Interview Success

When tackling B-tree problems in an interview, keep these practices in mind:

• Clarify definitions upfront — Always state your interpretation of “order” and the minimum/maximum key constraints. This avoids confusion during implementation.
• Modularize your code — Separate helper functions like _split_child, _fix_child, and _merge_nodes make the logic easier to follow and debug.
• Test edge cases — Insert into an empty tree, insert a key that causes root split, delete from leaf with minimum keys, delete from internal node, delete the only key in the root, and handle merging that propagates to the root.
• Discuss time and space complexity — Search, insert, and delete are all O(log_M n) node accesses and O(log n) key comparisons. Space is O(n) keys stored across nodes.
• Compare with B+ trees — Be ready to explain that B+ trees store all data in leaves with linked lists for efficient range queries, and internal nodes only store routing keys, making them more suitable for database indexing.
• Draw the tree — When reasoning about splits and merges, sketching the tree helps you and the interviewer visualize the transformation.
• Handle disk-access perspective — Emphasize that the high branching factor reduces height, minimizing disk seeks, which is the primary motivation behind B-trees.

Conclusion

B-trees are a cornerstone data structure that powers modern databases and file systems. Their multi-way balanced design optimizes disk I/O and provides guaranteed logarithmic performance. In an interview setting, mastering B-trees signals a strong grasp of advanced tree algorithms and the ability to implement complex balancing logic. By clarifying definitions, structuring your code with helper functions, and systematically handling edge cases during insertion and deletion, you can confidently solve any B-tree problem. Use the complete Python implementation in this guide as a reference, practice variations, and be ready to discuss real-world applications like B+ tree indexing. With these tools, you’ll turn B-tree challenges into a showcase of your engineering depth.