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

Concept Flow - B-tree index structure

Start at Root Node

↓

Compare Key with Node Keys

↓

If Key < Node Key

→Go to Left Child

↓

If Key > Node Key

→Go to Right Child

↓

Repeat Until Leaf Node

↓

Search or Insert Key in Leaf

↓

If Node Full

→Split Node and Promote Middle Key

↓

Update Parent Nodes

↓

End

The B-tree index structure starts at the root and moves down nodes by comparing keys until it reaches a leaf, where it searches or inserts keys, splitting nodes if full and updating parents.

Execution Sample

DBMS Theory

Insert keys: 10, 20, 5, 6, 12
Start with empty B-tree of order 3
Insert 10 at root
Insert 20 to right of 10
Insert 5 to left of 10, causes leaf split
Promote middle key 10 to root
Insert 6 into left child
Insert 12 into right child

This example shows inserting keys into a B-tree of order 3, causing a leaf split and promotion of a middle key to maintain balance.

Analysis Table

Step	Action	Node State	Split Occurs?	Promotion	Resulting Tree Structure
1	Insert 10	Root: [10]	No	None	Root node with key 10
2	Insert 20	Root: [10, 20]	No	None	Root node with keys 10, 20
3	Insert 5	Root full, insert 5 triggers split	Yes	Promote 10	Root: [10], Left child: [5], Right child: [20]
4	Insert 6	Insert 6 into left child [5]	No	None	Root: [10], Left: [5,6], Right: [20]
5	Insert 12	Insert 12 into right child [20]	No	None	Root: [10], Left: [5,6], Right: [12,20]
6	Search 6	Traverse root [10], go left child [5,6]	No	None	Found 6 in left child
7	Search 15	Traverse root [10], go right child [12,20]	No	None	15 not found in right child
8	End	Tree balanced and updated	No	None	Final balanced B-tree

💡 Insertion ends when all keys are placed and tree remains balanced

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Root Node Keys	[]	[10]	[10,20]	[10]	[10]	[10]	[10]
Left Child Keys	[]	[]	[]	[5]	[5,6]	[5,6]	[5,6]
Right Child Keys	[]	[]	[]	[20]	[20]	[12,20]	[12,20]

Key Insights - 3 Insights

Why does inserting 5 cause a split?

Because the B-tree order is 3, meaning max 2 keys per node. After inserting 10 and 20, the root had 2 keys which is full. Inserting 5 exceeds capacity, triggering split as shown in step 3 of execution_table.

What happens to the middle key during a node split?

The middle key is promoted to the parent node to maintain order and balance. In step 3, key 10 is promoted to root, splitting the node into left and right children.

How does the tree stay balanced after multiple insertions?

By splitting full nodes and promoting middle keys, the tree grows in height evenly, keeping all leaf nodes at the same level as seen in the final tree structure in step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what key is promoted to the root during the split?

A 10

B 6

C 5

D 20

💡 Hint

Check the 'Promotion' column in step 3 of execution_table

At which step does the tree first have child nodes?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Resulting Tree Structure' column for when children appear

If we insert key 15 after step 5, where would it be placed?

A Left child node

B Root node

C Right child node

D Causes another split

💡 Hint

Refer to the tree structure after step 5 and key comparisons

Concept Snapshot

B-tree index structure:
- Balanced tree with nodes holding multiple keys
- Keys in nodes sorted, children pointers between keys
- Insert by descending from root to leaf
- Split full nodes, promote middle key
- Keeps tree height low for fast search and insert

Full Transcript

The B-tree index structure is a balanced tree used in databases to keep data sorted and allow fast searches and inserts. It starts at the root node and compares keys to decide which child node to visit next. When inserting, if a node is full, it splits and promotes the middle key to the parent, keeping the tree balanced. This process repeats until all keys are inserted and the tree remains balanced with all leaves at the same level. The example shows inserting keys 10, 20, 5, 6, and 12 into a B-tree of order 3, causing a split and promotion of key 10. The execution table traces each step, showing node states, splits, and promotions. Key moments clarify why splits happen and how the tree stays balanced. The visual quiz tests understanding of promotions, child nodes, and insertion placement. This structure ensures efficient data retrieval in databases.