B+ tree index structure in DBMS Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does a B+ tree maintain sorted data?

In a B+ tree index, how is the data kept sorted for efficient searching?

A Data is stored in all nodes, but only root node keeps data sorted.

B Data is stored only in leaf nodes, which are linked in sorted order.

C Data is stored randomly in leaf nodes and sorted in internal nodes.

D Data is stored only in internal nodes, leaf nodes are empty.

💡 Hint

Think about where actual records or pointers to records are stored in a B+ tree.

B+ trees store all actual data pointers in the leaf nodes, which are linked in sorted order. Internal nodes only store keys to guide the search.

❓ query_result

intermediate

Number of keys in a B+ tree node

Given a B+ tree of order 4 (maximum 4 children per node), what is the maximum number of keys a single internal node can hold?

A 3

B 2

C 5

D 4

💡 Hint

Remember, the number of keys in an internal node is one less than the number of children.

For a B+ tree of order m, each internal node can have up to m children and thus m-1 keys.

📋 Factual

advanced

Identify the correct leaf node split in B+ tree insertion

When inserting a new key into a full leaf node in a B+ tree of order 3, which option correctly shows the resulting split?

DBMS Theory

Initial leaf node keys: [10, 20, 30]
Insert key: 25
Order: 3 (max 3 children, max 2 keys per node)

A Left leaf: [10, 25], Right leaf: [20, 30], Promote key: 20

B Left leaf: [10, 20, 25], Right leaf: [30], Promote key: 30

C Left leaf: [10, 20], Right leaf: [25, 30], Promote key: 25

D Left leaf: [10], Right leaf: [20, 25, 30], Promote key: 20

💡 Hint

Recall that after splitting, the middle key is promoted to the parent node.

Inserting 25 into [10,20,30] causes overflow. Splitting into [10,20] and [25,30] with 25 promoted maintains order and balance.

❓ optimization

advanced

Choosing B+ tree order for disk block size

You want to optimize a B+ tree index for a disk block size of 4KB. Which factor is most important when choosing the order of the B+ tree?

A Maximize the number of keys per node to fill the 4KB block efficiently.

B Minimize the number of keys per node to reduce search time inside nodes.

C Choose order so that each node fits multiple disk blocks for faster access.

D Choose order randomly since disk block size does not affect B+ tree order.

💡 Hint

Think about how disk reads work and how node size relates to block size.

Choosing an order that fills a disk block fully reduces the number of disk reads needed, improving performance.

🔍 Analysis

expert

Why does this B+ tree search fail to find a key?

Given a B+ tree search algorithm that always moves to the leftmost child if the key is less than the first key in the node, what is the likely cause of missing keys during search?

A The algorithm only searches leaf nodes and ignores internal nodes.

B The leaf nodes are not linked, so the search cannot continue sequentially.

C The root node is not checked for keys before descending.

D The algorithm does not correctly choose the child pointer based on key ranges in internal nodes.

💡 Hint

Consider how B+ tree internal nodes guide the search to the correct child.

B+ tree search must choose the correct child pointer based on key comparisons, not always the leftmost child. Otherwise, keys can be missed.

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