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.

Practice

1. What is the main purpose of a B-tree index in a database?

easy

A. To speed up data searching by organizing data in a balanced tree

B. To store data in a flat file for easy access

C. To encrypt data for security

D. To backup data automatically

Solution

1. Step 1: Understand what a B-tree index does

   A B-tree index organizes data in a balanced tree structure to make searching faster.

2. Step 2: Compare options with B-tree purpose

   Only To speed up data searching by organizing data in a balanced tree describes speeding up search using a balanced tree, which matches B-tree index use.

3. Final Answer:

   To speed up data searching by organizing data in a balanced tree -> Option A

4. Quick Check:

   B-tree index = speed up search [OK]

Hint: B-tree indexes speed up search by balanced tree structure [OK]

Common Mistakes:

• Confusing B-tree with encryption or backup
• Thinking B-tree stores data flatly
• Assuming B-tree slows down all operations

2. Which of the following is the correct way to create a B-tree index on column name in SQL?

easy

A. CREATE INDEX idx_name BY BTREE ON table_name (name);

B. CREATE BTREE INDEX idx_name ON table_name (name);

C. CREATE INDEX idx_name ON table_name (name);

D. CREATE INDEX idx_name USING BTREE ON table_name (name);

Solution

1. Step 1: Recall SQL syntax for B-tree index creation

   The standard syntax to specify B-tree index is using USING BTREE clause.

2. Step 2: Check each option's syntax

   CREATE INDEX idx_name USING BTREE ON table_name (name); uses CREATE INDEX idx_name USING BTREE ON table_name (name); which is correct. CREATE INDEX idx_name ON table_name (name); creates an index but does not specify B-tree explicitly. Options B and D have invalid syntax.

3. Final Answer:

   CREATE INDEX idx_name USING BTREE ON table_name (name); -> Option D

4. Quick Check:

   Correct syntax includes USING BTREE [OK]

Hint: Use 'USING BTREE' clause to specify B-tree index in SQL [OK]

Common Mistakes:

• Omitting USING BTREE when required
• Using BY or incorrect keywords
• Assuming default index is always B-tree

3. Given a B-tree index on column age, what will be the result of the query:
SELECT * FROM users WHERE age BETWEEN 20 AND 30;?

medium

A. The query will scan the entire table without using the index

B. The query will use the B-tree index to quickly find rows with age between 20 and 30

C. The query will return an error because BETWEEN is not supported with B-tree

D. The query will only return rows where age is exactly 20 or 30

Solution

1. Step 1: Understand B-tree index support for range queries

   B-tree indexes support range queries efficiently, such as BETWEEN.

2. Step 2: Analyze query behavior with B-tree index

   The query uses BETWEEN 20 AND 30, so the B-tree index will help find all rows in that range quickly.

3. Final Answer:

   The query will use the B-tree index to quickly find rows with age between 20 and 30 -> Option B

4. Quick Check:

   B-tree supports range queries = fast search [OK]

Hint: B-tree indexes speed up range queries like BETWEEN [OK]

Common Mistakes:

• Thinking B-tree only supports exact matches
• Assuming BETWEEN causes errors
• Believing full table scan always happens

4. A developer created a B-tree index on column salary but notices queries using salary are still slow. Which of the following is a likely cause?

medium

A. The index was created but the column has many NULL values and queries filter on NULL

B. The B-tree index automatically speeds up all queries regardless of conditions

C. The database does not support B-tree indexes

D. The index was created on a different column by mistake

Solution

1. Step 1: Identify why B-tree index might not help

   If the column has many NULL values and queries filter on NULL, B-tree index may not be used effectively.

2. Step 2: Evaluate other options

   The B-tree index automatically speeds up all queries regardless of conditions is false because indexes don't speed up all queries automatically. The database does not support B-tree indexes is unlikely if B-tree index was created. The index was created on a different column by mistake is possible but less likely than D given the scenario.

3. Final Answer:

   The index was created but the column has many NULL values and queries filter on NULL -> Option A

4. Quick Check:

   NULL values can reduce B-tree index effectiveness [OK]

Hint: NULL values can prevent B-tree index use in queries [OK]

Common Mistakes:

• Assuming index always speeds up queries
• Ignoring NULL value impact
• Believing database lacks B-tree support without checking

5. You have a large table with millions of rows and want to optimize queries that search for customers by last name prefix (e.g., names starting with 'Sm'). How can a B-tree index help, and what is a limitation you must consider?

hard

A. B-tree index cannot help prefix searches; use hash index instead

B. B-tree index speeds up prefix searches and has no impact on insert speed

C. B-tree index can speed up prefix searches, but it may slow down insert operations

D. B-tree index only works for numeric columns, so it cannot help here

Solution

1. Step 1: Understand B-tree index support for prefix searches

   B-tree indexes support prefix searches efficiently by traversing the tree to matching keys.

2. Step 2: Consider performance trade-offs

   While B-tree indexes speed up reads, they can slow down insert and update operations because the tree must be maintained.

3. Final Answer:

   B-tree index can speed up prefix searches, but it may slow down insert operations -> Option C

4. Quick Check:

   B-tree = fast prefix search + slower inserts [OK]

Hint: B-tree helps prefix search but slows inserts due to tree maintenance [OK]

Common Mistakes:

• Thinking B-tree can't do prefix searches
• Ignoring insert/update slowdown
• Believing B-tree only works on numbers