B-Tree Insertion: Simple Cases
What you'll learn: How to insert keys into B-tree nodes when there's enough space available.
The Core Idea
B-tree insertion becomes straightforward when the target node isn't full. Since B-trees maintain sorted order within each node and keep all leaves at the same level, you need to find the correct leaf position and insert while preserving these properties—but only when the node has room.
Finding the Right Spot
When inserting a key, you start at the root and navigate down following the B-tree search rules (comparing with node keys to choose the appropriate child pointer). You always insert into a leaf node, never an internal node.
Think of it like filing papers in a cabinet drawer: you open the drawer (leaf node), find the alphabetically correct spot among the existing papers, and slide the new one in—assuming the drawer isn't overstuffed.
The Simple Case
When does the simple case apply? When the target leaf has fewer than the maximum allowed keys (less than 2t - 1 keys for a B-tree of order t).
The insertion steps are:
- Search down to the appropriate leaf node
- Check if the leaf has space (current key count < maximum)
- Insert the new key in sorted order within that leaf
- Update the key count
This is similar to inserting into a sorted array—shift existing keys right if needed to maintain order.
Example Walkthrough
Suppose you have a B-tree of order 3 (maximum 5 keys per node). A leaf contains [10, 30, 50] and you want to insert 20:
- Navigate to this leaf
- It has 3 keys (less than 5) ✓
- Insert
20between10and30:[10, 20, 30, 50] - Done!
Key Takeaway: Simple B-tree insertion occurs when the target leaf has available space—just find the leaf, insert the key in sorted order, and you're done. Complex cases (splits) only arise when nodes are full.