B+ tree index structure in DBMS Theory - Step-by-Step Execution

Concept Flow - B+ tree index structure

Start: Empty B+ Tree

↓

Insert Key

↓

Find Leaf Node

↓

Insert Key in Leaf

↓

Is Leaf Full?

No→Done

Yes↓

Split Leaf Node

↓

Insert Middle Key to Parent

↓

Is Parent Full?

No→Done

Yes↓

Split Internal Node

↓

Repeat Insert to Parent

↓

Done

The B+ tree grows by inserting keys into leaf nodes, splitting nodes when full, and propagating splits up to the root if needed.

Execution Sample

DBMS Theory

Insert keys: 10, 20, 5, 6, 12
Order = 3 (max 2 keys per node)

Shows step-by-step insertion of keys into a B+ tree of order 3, including splits.

Analysis Table

Step	Action	Node Affected	Keys Before	Keys After	Split Occurs	Parent Update
1	Insert 10	Leaf	[]	[10]	No	No
2	Insert 20	Leaf	[10]	[10,20]	No	No
3	Insert 5	Leaf	[10,20]	[5,10,20]	Yes	Insert 10 to Parent
4	Split Leaf	Leaf	[5,10,20]	[5] | [10,20]	Yes	Insert 10 to Parent
5	Insert 6	Leaf	[5]	[5,6]	No	No
6	Insert 12	Leaf	[10,20]	[10,12,20]	Yes	Insert 12 to Parent
7	Insert 12 to Parent	Root	[10]	[10,12]	No	No

💡 All keys inserted; tree balanced with splits propagated to root as needed.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
Leaf Node Keys	[]	[10]	[10,20]	[5,10,20]	[5] | [10,20]	[5,6] | [10,20]	[5,6] | [10,12,20]	[5,6] | [10,12,20]
Root Keys	[]	[]	[]	[]	[10]	[10]	[10,12]	[10,12]
Split Occurred	No	No	No	Yes	Yes	No	Yes	No

Key Insights - 3 Insights

Why do we split the leaf node when it has 3 keys if the order is 3?

Because order 3 means max 2 keys per node; inserting the 3rd key causes overflow, so we split (see step 3 and 4 in execution_table).

Why is the middle key inserted into the parent after splitting a leaf?

The middle key acts as a separator to guide searches; it moves up to the parent to maintain tree order (see step 4 and 7).

What happens if the parent node is also full when inserting the middle key?

Then the parent node splits too, and the process repeats upward until no overflow or root is split (not shown here but described in concept_flow).

Visual Quiz - 3 Questions

Look at the execution_table, after which step does the first split occur?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Check the 'Split Occurs' column in execution_table rows.

According to variable_tracker, what keys does the root have after step 7?

A [10,12]

B [5,6]

C []

D [12,20]

💡 Hint

Look at 'Root Keys' row under 'After Step 7' column.

If we insert a key that causes the parent to split, what would happen next according to concept_flow?

A Insertion stops immediately

B Keys are deleted from leaf

C Split propagates up to grandparent

D Tree height decreases

💡 Hint

Refer to the flow from 'Is Parent Full? Yes' to 'Split Internal Node' and 'Repeat Insert to Parent'.

Concept Snapshot

B+ Tree Index Structure:
- Keys stored in sorted order in leaf nodes.
- Each node can hold up to order-1 keys.
- Insertions cause splits if node is full.
- Middle key moves up to parent on split.
- Splits can propagate up to root, increasing tree height.
- Leaf nodes linked for fast range queries.

Full Transcript

This visual execution traces inserting keys into a B+ tree of order 3. Starting with an empty tree, keys 10 and 20 insert into the leaf node without splits. Inserting 5 causes the leaf to overflow (3 keys), triggering a split. The leaf splits into two nodes with keys [5] and [10,20], middle key 10 moves up to the root. Subsequent inserts: 6 into left becoming [5,6], 12 into right becoming [10,12,20], causing another split and insertion of 12 to the root. The root now holds keys 10 and 12, separating the leaf nodes. The process shows how splits propagate upward to maintain balance and order in the B+ tree.