Course contentsShow
← Computer Science
Lesson 1681 of 2,87238. Database Transactions and IndexingFree lesson

Node Splitting During Insertion

How to split full nodes, promote median keys, and propagate splits up the tree during insertion.

Node Splitting During Insertion

What You'll Learn

You'll learn how B-Trees maintain balance by splitting full nodes, promoting median keys upward, and propagating splits through the tree during insertion operations.

Why Nodes Split

When inserting into a B-Tree, you might encounter a node that's already at maximum capacity. Since B-Trees enforce strict size limits (typically a maximum number of keys per node), you can't simply add another key. Instead, you must split the full node into two smaller nodes.

The Splitting Process

Imagine a bookshelf that's completely full. To add another book, you:

  1. Find the middle book (the median)
  2. Split the shelf into two shorter shelves—books before the median on the left, books after on the right
  3. Move the middle book up to a "supervisor" shelf that tracks which books are on which lower shelf

B-Tree node splitting works similarly:

  1. Identify the full node – The node has reached its maximum key capacity
  2. Find the median key – Select the middle key from the sorted keys in the node
  3. Create two new nodes – Split the keys and child pointers around the median
  4. Promote the median – Push the median key up to the parent node
  5. Propagate if needed – If the parent is also full, repeat the split process upward

Cascading Splits

The promoted key must be inserted into the parent node. If the parent is also full, it must split too, promoting its own median key to its parent. This can cascade all the way to the root. When the root splits, a new root with a single key is created, increasing the tree's height by one level.

Key Takeaway: Node splitting maintains B-Tree balance by dividing full nodes at their median, promoting the middle key upward, and potentially triggering a chain of splits that ensures all leaf nodes remain at the same depth.