B+ tree index structure in DBMS Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a B+ tree index on the column 'employee_id'.

DBMS Theory

CREATE INDEX idx_emp_id ON employees USING [1] (employee_id);

Drag options to blanks, or click blank then click option'

Abtree

Bgin

Cgist

Dhash

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'hash' instead of 'btree' will create a hash index, not a B+ tree index.

Using 'gist' or 'gin' are for other index types, not B+ tree.

The B+ tree index is created using the keyword btree in SQL.

2fill in blank

medium

Complete the code to find the leaf node in a B+ tree index where the key 50 would be located.

DBMS Theory

SELECT * FROM bplus_tree WHERE key = [1];

Drag options to blanks, or click blank then click option'

A50

B25

C75

D100

Attempts:

3 left

💡 Hint

Common Mistakes

Using a different key value will not find the correct leaf node.

Using a range or inequality instead of equality.

To find the leaf node for key 50, you query the B+ tree index with key = 50.

3fill in blank

hard

Fix the error in the B+ tree node split condition to check if the number of keys exceeds the maximum.

DBMS Theory

if (num_keys [1] max_keys) {
    split_node();
}

Drag options to blanks, or click blank then click option'

A<

B>=

C<=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' or '<=' will cause split to happen too early or never.

Using '>=' may cause split to happen one key too late.

The node should split when the number of keys is greater than the maximum allowed, so use '>'.

4fill in blank

hard

Fill both blanks to complete the B+ tree search condition for keys between 10 and 20 inclusive.

DBMS Theory

SELECT * FROM bplus_tree WHERE key [1] 10 AND key [2] 20;

Drag options to blanks, or click blank then click option'

A>=

B<

C<=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' or '>' excludes boundary keys.

Mixing operators incorrectly changes the range.

To include keys between 10 and 20 inclusive, use 'key >= 10' and 'key <= 20'.

5fill in blank

hard

Fill all three blanks to complete the B+ tree insertion pseudocode for updating parent after split.

DBMS Theory

parent.keys.[1](new_key)
parent.children.[2](new_child)
if len(parent.keys) [3] max_keys:
    split_node(parent)

Drag options to blanks, or click blank then click option'

Aappend

Binsert

C>

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'append' for keys may not keep order.

Using 'pop' removes elements instead of adding.

Using '<' or '<=' in condition delays split.

Insert the new key with 'insert', add new child with 'append', and check if keys exceed max with '>'.

Practice

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

easy

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

B. To store data in a random order for faster insertion

C. To compress data to save storage space

D. To encrypt data for security

Solution

1. Step 1: Understand the role of B+ tree indexes

   B+ tree indexes organize keys in a balanced tree structure to allow quick searching.

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

   Only To speed up data retrieval by organizing keys in a balanced tree describes speeding up data retrieval using a balanced tree, which matches B+ tree function.

3. Final Answer:

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

4. Quick Check:

   B+ tree index purpose = speed up search [OK]

Hint: B+ trees speed up search by balanced key organization [OK]

Common Mistakes:

• Confusing B+ tree with data compression
• Thinking B+ tree encrypts data
• Assuming B+ tree stores data randomly

2. Which of the following is the correct property of a B+ tree node?

easy

A. Nodes are linked only vertically, not horizontally

B. Each node contains only data records, no keys

C. Leaf nodes contain only keys, internal nodes contain data records

D. Internal nodes contain keys and pointers, leaf nodes contain data pointers

Solution

1. Step 1: Recall B+ tree node structure

   Internal nodes hold keys and pointers to child nodes; leaf nodes hold keys and pointers to actual data.

2. Step 2: Match options with B+ tree node properties

   Internal nodes contain keys and pointers, leaf nodes contain data pointers correctly states internal nodes have keys and pointers, leaf nodes have data pointers.

3. Final Answer:

   Internal nodes contain keys and pointers, leaf nodes contain data pointers -> Option D

4. Quick Check:

   B+ tree node structure = internal keys + leaf data [OK]

Hint: Internal nodes hold keys; leaves hold data pointers [OK]

Common Mistakes:

• Thinking leaf nodes have no keys
• Believing nodes link only vertically
• Confusing data records with keys in internal nodes

3. Consider a B+ tree of order 3 (each node can have max 3 children). If we insert keys 10, 20, 5, 6, 12 in order, what will be the root node's keys after all insertions?

medium

A. [6, 12]

B. [5, 6, 10]

C. [10]

D. [12, 20]

Solution

1. Step 1: Insert keys step-by-step in B+ tree order 3

   Insert 10, 20, 5 fills root node keys [5,10,20]. Inserting 6 causes split because max keys is 2 (order 3 means max 2 keys per node). The middle key 10 moves up as root key.

2. Step 2: Determine root keys after split

   After split, root has key [10], left child has [5,6], right child has [12,20].

3. Final Answer:

   [10] -> Option C

4. Quick Check:

   Order 3 split root key = 10 [OK]

Hint: Order 3 means max 2 keys; middle key moves up on split [OK]

Common Mistakes:

• Assuming root keeps all keys without split
• Confusing order with max keys per node
• Forgetting to move middle key up on split

4. A B+ tree index is not updating correctly after inserting a new key. Which of the following is the most likely cause?

medium

A. The tree height is too large

B. The leaf nodes are not linked properly after split

C. The root node contains too many keys

D. The keys are not sorted in the leaf nodes

Solution

1. Step 1: Identify common B+ tree update issues

   When inserting keys, leaf nodes must be linked in order to maintain correct traversal and range queries.

2. Step 2: Analyze options for update failure

   If leaf nodes are not linked properly after split, the index will not update correctly. Other options are less likely causes.

3. Final Answer:

   The leaf nodes are not linked properly after split -> Option B

4. Quick Check:

   Leaf node linkage error = update failure [OK]

Hint: Check leaf node links after splits for update issues [OK]

Common Mistakes:

• Blaming root node size without checking leaf links
• Ignoring leaf node order and linkage
• Assuming tree height causes update failure

5. You have a large database table and want to optimize range queries on a numeric column. Which feature of a B+ tree index makes it especially suitable for this task?

hard

A. Leaf nodes are linked in a sorted sequence allowing fast range scans

B. Internal nodes store full data records for quick access

C. B+ trees compress data to reduce disk space

D. B+ trees use hashing to find exact matches quickly

Solution

1. Step 1: Understand B+ tree leaf node linkage

   Leaf nodes in B+ trees are linked in a sorted order, enabling efficient sequential access for range queries.

2. Step 2: Evaluate options for range query optimization

   Leaf nodes are linked in a sorted sequence allowing fast range scans correctly identifies linked leaf nodes as the key feature for fast range scans. Other options describe unrelated features.

3. Final Answer:

   Leaf nodes are linked in a sorted sequence allowing fast range scans -> Option A

4. Quick Check:

   Linked leaf nodes = efficient range queries [OK]

Hint: Linked leaves enable fast sequential range scans [OK]

Common Mistakes:

• Confusing B+ tree with hash indexes
• Thinking internal nodes store full data
• Assuming compression is main feature