B-Tree Foundations & Node Splitting
Binary search trees degrade into uncacheable linked lists on storage media. A B-Tree is a balanced $M$-way search tree structured around OS disk block sizes. When a node overflows its key limit, it splits at the median key and pushes it into its parent 🌳⚖️.
class BTreeNode:
def __init__(self, is_leaf=True):
self.is_leaf = is_leaf
self.keys = []
self.children = []
def split_node(parent, child_idx, child):
mid = len(child.keys) // 2
median = child.keys[mid]
sibling = BTreeNode(is_leaf=child.is_leaf)
sibling.keys = child.keys[mid + 1:]
child.keys = child.keys[:mid]
parent.keys.insert(child_idx, median)
parent.children.insert(child_idx + 1, sibling)
root = BTreeNode(is_leaf=False)
child = BTreeNode(is_leaf=True)
child.keys = [10, 20, 30] # Overfilled node
root.children.append(child)
split_node(root, 0, child)
print(f"Parent promoted key: {root.keys}, Sibling keys: {root.children[1].keys} 🚀")
# 54. B-Tree Foundations & Node Splitting In-memory data structures like red-black trees or AVL trees have a branching factor of 2. On a disk where every pointer dereference costs a 4KB disk page read, a tree with depth 30 requires 30 separate I/O operations per query 🛑. ```python # Binary Tree (Branching factor = 2): # 1,000,000 items -> Depth = log2(1M) ~ 20 disk seeks! # B-Tree (Branching factor = 512, aligned with 4KB page): # 1,000,000 items -> Depth = log512(1M) ~ 2-3 disk seeks! ``` ### The B-Tree Invariants 1. **High Fan-Out**: Nodes are sized to match the storage block (e.g. 4KB or 16KB), holding hundreds of keys per node to keep depth exceptionally shallow ($\le 3$). 2. **Balanced Growth**: A B-Tree never grows downward at the leaves. When a leaf overflows, it splits and pushes its median key upward to its parent. 3. **Root Split**: When the root itself overflows, it splits into two children and a new single-key root is created above them, increasing tree height uniformly across all branches 🌳⚖️. --- ### Interactive Pop-Quiz 🧠 #### What mathematical property ensures that all leaf nodes in a B-Tree remain at the exact same depth from the root? - [ ] The tree grows exclusively upward from the root when the root node splits and creates a new level 🌳 - [ ] Leaves are periodically rebalanced by rotating through memory caches - [ ] Every write operation executes a depth-first search to rewrite heights - [ ] Leaves with greater depth are pruned automatically on each commit --- ### Practical Challenge 🎯 Implement `split_node(parent, child_idx, child)`. Populate a parent node with empty keys and children `[child]`. Fill `child.keys = [100, 200, 300]`. Execute `split_node(parent, 0, child)`. Assert `parent.keys == [200]`, `child.keys == [100]`, and the new sibling's keys equal `[300]`. Print `parent.keys`. <details> <summary>Solution</summary> ```python class BTreeNode: def __init__(self, is_leaf=True): self.is_leaf = is_leaf self.keys = [] self.children = [] def split_node(parent, child_idx, child): mid = len(child.keys) // 2 median = child.keys[mid] sibling = BTreeNode(is_leaf=child.is_leaf) sibling.keys = child.keys[mid + 1:] child.keys = child.keys[:mid] parent.keys.insert(child_idx, median) parent.children.insert(child_idx + 1, sibling) parent = BTreeNode(is_leaf=False) child = BTreeNode(is_leaf=True) child.keys = [100, 200, 300] parent.children.append(child) split_node(parent, 0, child) assert parent.keys == [200] assert child.keys == [100] assert parent.children[1].keys == [300] print(parent.keys) ``` </details>