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

Splitting Root Nodes

Understand how B-trees grow in height by splitting the root and creating a new root with promoted key.

Splitting Root Nodes

What you'll learn: How B-trees increase their height by splitting the root node and promoting a key upward to form a new root.

The Unique Growth Pattern

In most trees, height increases by adding leaves at the bottom. B-trees are different—they grow upward by splitting the root when it overflows.

When you insert a key into a full root node (one that's already at maximum capacity), you can't just split it like an internal node and promote a key to the parent—there is no parent. This is the special case.

How Root Splitting Works

When the root node is full and needs to accommodate another key:

  1. Split the full root into two nodes, just like any node split
  2. Promote the middle key upward
  3. Create a brand new root containing only the promoted key
  4. Make the two split pieces children of this new root

This is the only way a B-tree grows taller. The entire tree gains one level of height, but remains perfectly balanced because the root split affects all paths equally.

Simple Example

Imagine a B-tree of order 3 (max 2 keys per node) with root containing [10, 20]. When you insert 15:

  • Root is full, so you'd have [10, 15, 20] to split
  • Middle key 15 gets promoted
  • New root contains just [15]
  • Left child: [10], right child: [20]
  • Tree height increased from 1 to 2

Key Takeaway: B-trees grow in height exclusively through root splitting, where the middle key is promoted to a newly created root, making the tree grow upward while maintaining perfect balance across all paths.