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

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does a B-tree maintain balance?

In a B-tree index, what mechanism ensures that the tree remains balanced after insertions and deletions?

A By storing all keys in a single sorted list

B By rotating nodes left or right like in AVL trees

C By rebuilding the entire tree after every insertion

D By splitting or merging nodes to keep all leaf nodes at the same depth

💡 Hint

Think about how B-trees keep their height minimal and uniform.

B-trees keep all leaf nodes at the same depth by splitting nodes when they get too full and merging nodes when they get too empty. This keeps the tree balanced and search efficient.

❓ query_result

intermediate

Number of keys in a B-tree node

Consider a B-tree of order 4 (each node can have at most 4 children). What is the maximum number of keys a single node can hold?

A 3

B 4

C 5

D 2

💡 Hint

Remember, a node with n children has n-1 keys.

In a B-tree, the number of keys in a node is always one less than the number of its children. For order 4, max children is 4, so max keys is 3.

📋 Factual

advanced

Identify the correct B-tree insertion step

Which SQL-like pseudocode correctly describes the step to split a full B-tree node during insertion?

DBMS Theory

IF node.isFull() THEN
  median = node.keys[middle_index]
  leftNode = node.keys[0 to middle_index-1]
  rightNode = node.keys[middle_index+1 to end]
  parent.insertKey(median)
  parent.insertChild(leftNode)
  parent.insertChild(rightNode)
END IF

A Merge node with sibling and push median down to child

B Delete median key and redistribute keys evenly

C Split node into two nodes around median key and push median up to parent

D Replace node keys with median key only

💡 Hint

Think about how B-tree insertion handles full nodes.

When a node is full, it splits into two nodes around the median key. The median key moves up to the parent node to maintain order.

❓ optimization

advanced

Choosing B-tree order for disk storage

Why is a higher order (more children per node) preferred for B-trees used in disk-based databases?

A Because it allows storing keys in random order

B Because it reduces the tree height and number of disk reads

C Because it increases the number of keys per node, causing more disk reads

D Because it makes the tree unbalanced and faster to traverse

💡 Hint

Consider how disk access speed affects search performance.

Higher order means more keys per node, which reduces tree height. This lowers the number of disk reads needed to find a key, improving performance.

🔍 Analysis

expert

Diagnose B-tree search failure

A B-tree search for key 42 returns no result, but the key exists in the tree. Which issue below most likely causes this problem?

A The tree nodes are not properly linked after a node split

B The key comparison uses <= instead of <

C The tree height is too large

D The root node has fewer keys than allowed

💡 Hint

Think about what happens if pointers between nodes are incorrect.

If nodes are not linked correctly after splitting, the search path can miss keys even if they exist, causing search failures.