B-Tree Insertion with Node Splitting

Split Full Nodes on the Way Up

Insert descends to the correct leaf. If a node is full, split it into two halves, promote the middle key to the parent, and possibly split the parent recursively. Splits keep nodes at least half full except the root, preserving balance.

Split Outline

Move upper half keys to a new right sibling, push median key into parent, link children accordingly.

c
Loading…

Root split grows tree height by one
Bulk load can build trees with fewer splits than repeated insert
WAL must log splits before pointers become visible on disk
Visualize with USFCA B-tree animator when debugging

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement insert with node splitting when capacity is exceeded. This exercise requires demonstrating a split that promotes a key into the parent.

Write a C program that implements B-tree insertion with node splitting.

Requirements:

Use MAX_KEYS=3 (so split when a node has 4 keys temporarily)
Implement btree_insert(root, key, value) that inserts a key-value pair
Implement split_child(parent, child_index) that splits a full child
When inserting into a full root, create a new root and split the old root
Start with an empty tree and insert these keys in order: 10, 20, 5, 6, 12, 30, 7, 17
After each insertion that causes a split, print "SPLIT: promoted key X"
After all insertions, print the tree level by level showing keys in each node
Verify that all leaves are at the same depth
Count and print the total number of nodes and the tree height
Test searching for a few keys to verify the tree is correct

Split Full Nodes on the Way Up

Split Outline

Move upper half keys to a new right sibling, push median key into parent, link children accordingly.

c
Loading…

Root split grows tree height by one
Bulk load can build trees with fewer splits than repeated insert
WAL must log splits before pointers become visible on disk
Visualize with USFCA B-tree animator when debugging

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement insert with node splitting when capacity is exceeded. This exercise requires demonstrating a split that promotes a key into the parent.

Write a C program that implements B-tree insertion with node splitting.

Requirements:

Use MAX_KEYS=3 (so split when a node has 4 keys temporarily)
Implement btree_insert(root, key, value) that inserts a key-value pair
Implement split_child(parent, child_index) that splits a full child
When inserting into a full root, create a new root and split the old root
Start with an empty tree and insert these keys in order: 10, 20, 5, 6, 12, 30, 7, 17
After each insertion that causes a split, print "SPLIT: promoted key X"
After all insertions, print the tree level by level showing keys in each node
Verify that all leaves are at the same depth
Count and print the total number of nodes and the tree height
Test searching for a few keys to verify the tree is correct

Topic Overview

Split Full Nodes on the Way Up

Split Outline

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

B-Tree Insertion with Node Splitting

Topic Overview

Split Full Nodes on the Way Up

Split Outline

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source