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.