B-trees for databases in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the primary purpose of a B-tree in databases?

Choose the best description of why B-trees are used in database systems.

A To maintain sorted data and allow efficient insertion, deletion, and search operations.

B To compress data to save storage space in databases.

C To store data in a way that allows fast sequential access only.

D To encrypt data for security purposes during storage.

💡 Hint

Think about how databases need to quickly find and update records.

B-trees keep data sorted and balanced, enabling fast search, insert, and delete operations, which is essential for database indexing.

📋 Factual

intermediate

What is the minimum number of keys a non-root node in a B-tree of order 4 must have?

In a B-tree of order 4 (maximum 4 children per node), how many keys must a non-root node have at minimum?

A 2

B 1

C 3

D 4

💡 Hint

Recall that the minimum number of keys is about half the maximum children minus one.

For a B-tree of order 4, each node can have up to 4 children and thus up to 3 keys. The minimum number of keys in a non-root node is ceil(4/2)-1 = 1.

🔍 Analysis

advanced

What happens during a node split in a B-tree insertion?

When inserting a key causes a node to overflow in a B-tree, what is the correct sequence of actions during the node split?

A 1,3,2,4

B 1,2,4,3

C 2,1,3,4

D 1,2,3,4

💡 Hint

Think about the order of splitting keys and updating the parent.

First, find the median key to split the node. Then create two nodes from keys less and greater than median. Next, move the median key up to the parent. Finally, update the parent's children pointers.

❓ Comparison

advanced

How does a B-tree differ from a binary search tree in database indexing?

Choose the statement that best explains the difference between B-trees and binary search trees (BST) in the context of databases.

A B-trees do not maintain sorted order of keys, unlike BSTs.

B B-trees are always binary, but BSTs can have multiple children per node.

C B-trees store multiple keys per node and keep the tree balanced, while BSTs store one key per node and can become unbalanced.

D BSTs are optimized for disk storage, while B-trees are only used in memory.

💡 Hint

Consider how nodes and balance affect search speed in large datasets.

B-trees store multiple keys per node and keep the tree balanced to minimize disk reads. BSTs store one key per node and can become unbalanced, leading to slower searches.

❓ Reasoning

expert

Why do B-trees reduce disk I/O operations in databases?

Explain why B-trees are designed to reduce the number of disk input/output (I/O) operations when searching or updating data in databases.

A Because B-trees store many keys in each node, they reduce the tree height, minimizing the number of disk reads needed to find a key.

B Because B-trees compress data, they reduce the amount of data read from disk.

C Because B-trees use hashing internally, they directly access data without searching.

D Because B-trees store data in random order, they avoid sequential disk reads.

💡 Hint

Think about how storing multiple keys per node affects tree height and disk access.

B-trees store multiple keys per node, which reduces the height of the tree. A shorter tree means fewer nodes to read from disk during search or update, thus reducing disk I/O operations.