Course contentsShow
← Computer Science
Lesson 561 of 2,87213. Balanced TreesFree lesson

Node Splitting During Insertion

Learn how to split full nodes during insertion, promoting the median key upward to maintain balance.

Node Splitting During Insertion

You'll learn how B-trees handle full nodes by splitting them in half and promoting the median key upward to keep the tree balanced.

Why Split Nodes?

In a B-tree, each node has a maximum capacity for keys (determined by the tree's order). When you try to insert a key into an already-full node, you can't just keep adding—the node would violate the B-tree invariants. Instead, you split the node into two smaller nodes and push the middle key up to the parent.

The Splitting Process

Think of it like overfilling a bookshelf. When one shelf has too many books, you:

  1. Take the middle book
  2. Split the remaining books between two shelves
  3. Use the middle book's title as a divider label on the shelf above

In B-tree terms:

  1. Identify the median key in the full node
  2. Create two new nodes: left gets keys smaller than median, right gets keys greater
  3. Promote the median up to the parent node
  4. Update pointers so the parent links to both new child nodes

Example

Imagine a node that can hold maximum 3 keys is full: [10, 20, 30]

When you need to insert 25:

  • The node becomes temporarily [10, 20, 25, 30]
  • Median is 20 (or 25, depending on convention)
  • Split into: Left [10], promote 20, Right [25, 30]
  • The parent node receives 20 as a new key pointing to both children

If the parent is also full, the split cascades upward—possibly creating a new root, which is how B-trees grow taller.

Key Takeaway: Node splitting divides a full node at its median, promoting the middle key upward to maintain B-tree balance and invariants during insertion.