B-trees for databases in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the sentence to describe a B-tree property.

Data Structures Theory

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in [1] time.

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

Alogarithmic

Blinear

Cconstant

Dexponential

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing logarithmic time with linear or constant time.

Thinking B-trees are unbalanced.

B-trees keep their height low, so operations like search, insert, and delete take logarithmic time relative to the number of elements.

2fill in blank

medium

Complete the sentence to explain the node structure of a B-tree.

Data Structures Theory

Each node in a B-tree contains multiple keys and [1] children pointers.

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

Aone

Bzero

Cmultiple

Dtwo

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming B-trees are binary trees with only two children per node.

Confusing the number of keys with the number of children.

B-tree nodes can have multiple children, which allows the tree to be wide and shallow, improving efficiency.

3fill in blank

hard

Fix the error in the statement about B-tree leaf nodes.

Data Structures Theory

In a B-tree, all leaf nodes are at [1] level.

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

Adifferent

Bthe same

Crandom

Dhigher

Attempts:

3 left

💡 Hint

Common Mistakes

Thinking leaf nodes can be at different levels.

Confusing B-trees with unbalanced trees.

All leaf nodes in a B-tree are at the same level, which keeps the tree balanced.

4fill in blank

hard

Fill both blanks to describe B-tree node key constraints.

Data Structures Theory

Each node (except root) must have at least [1] keys and at most [2] keys.

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

At - 1

B2t

C2t - 1

Dt

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up minimum and maximum key counts.

Using t instead of t-1 for minimum keys.

In a B-tree of minimum degree t, each node except the root must have at least t-1 keys and at most 2t-1 keys.

5fill in blank

hard

Fill all three blanks to complete the B-tree insertion rule.

Data Structures Theory

If a node is full (has [1] keys), it must be [2] before inserting a new key, which splits it into two nodes with [3] keys each.

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

A2t - 1

Bsplit

Ct - 1

Dmerged

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing splitting with merging.

Incorrectly identifying the number of keys in full nodes.

When a node has 2t - 1 keys (full), it is split before insertion, resulting in two nodes each with t - 1 keys.

Practice

1. What is the main purpose of a B-tree in databases?

easy

A. To compress data to save disk space

B. To keep data sorted and balanced for fast searching and updating

C. To encrypt data for security

D. To store data in a linear list for quick access

Solution

1. Step 1: Understand B-tree structure

   B-trees organize data in a sorted and balanced tree structure.

2. Step 2: Identify the purpose in databases

   This structure allows fast searching, insertion, and deletion by minimizing tree height and disk reads.

3. Final Answer:

   To keep data sorted and balanced for fast searching and updating -> Option B

4. Quick Check:

   B-tree purpose = fast, balanced data access [OK]

Hint: B-trees balance data for speed, not encryption or compression [OK]

Common Mistakes:

• Confusing B-trees with simple lists
• Thinking B-trees encrypt data
• Assuming B-trees compress data

2. Which of the following correctly describes a property of B-tree nodes?

easy

A. Each node can contain multiple keys and multiple children

B. Nodes contain only keys but no children

C. Each node contains exactly one key and two children

D. Nodes are always leaf nodes without children

Solution

1. Step 1: Recall B-tree node structure

   B-tree nodes hold multiple keys to reduce tree height.

2. Step 2: Understand children count

   Each node has one more child than the number of keys it holds.

3. Final Answer:

   Each node can contain multiple keys and multiple children -> Option A

4. Quick Check:

   Multiple keys and children per node = C [OK]

Hint: B-tree nodes hold many keys and children, not just one [OK]

Common Mistakes:

• Thinking nodes have only one key
• Assuming nodes have no children
• Confusing B-trees with binary trees

3. Consider a B-tree of order 3 (each node can have at most 2 keys). If a node currently has keys [10, 20] and a new key 15 is inserted, what will happen?

medium

A. The key 15 will be discarded as duplicates are not allowed

B. The node will hold keys [10, 15, 20] without splitting

C. The node will split because it exceeds the max keys, promoting a key up

D. The tree will become unbalanced and require rebalancing later

Solution

1. Step 1: Check node capacity for order 3 B-tree

   Max keys per node = 2. Current keys are [10, 20]. Inserting 15 adds a third key.

2. Step 2: Understand insertion rules

   When a node exceeds max keys, it splits and promotes the middle key to the parent.

3. Final Answer:

   The node will split because it exceeds the max keys, promoting a key up -> Option C

4. Quick Check:

   Node over capacity causes split and promotion [OK]

Hint: If keys exceed max, node splits and middle key moves up [OK]

Common Mistakes:

• Thinking node can hold 3 keys without splitting
• Assuming duplicates are discarded here
• Believing tree becomes unbalanced without immediate fix

4. A B-tree node is supposed to split when it exceeds its maximum keys. Which of the following is a common mistake that can cause the tree to become unbalanced after insertion?

medium

A. Not promoting the middle key to the parent node after splitting

B. Always inserting keys in sorted order

C. Using nodes with multiple keys and children

D. Searching for keys before insertion

Solution

1. Step 1: Understand node splitting in B-trees

   When a node splits, the middle key must be promoted to keep the tree balanced.

2. Step 2: Identify the error impact

   If the middle key is not promoted, the tree structure breaks and becomes unbalanced.

3. Final Answer:

   Not promoting the middle key to the parent node after splitting -> Option A

4. Quick Check:

   Missing promotion causes imbalance [OK]

Hint: Always promote middle key on split to keep balance [OK]

Common Mistakes:

• Skipping promotion step after split
• Thinking sorted insertion causes imbalance
• Confusing node structure rules

5. You have a B-tree of order 4 (max 3 keys per node). After several insertions, a leaf node has keys [5, 10, 15] and you want to insert 12. Describe the sequence of steps the B-tree will perform to maintain balance.

hard

A. Insert 12 and increase the node capacity temporarily

B. Discard 12 because the node is full

C. Insert 12 and rebalance by merging with sibling nodes without splitting

D. Insert 12 into the leaf node, then split the node and promote the middle key to the parent

Solution

1. Step 1: Attempt to insert 12 into leaf node

   The leaf node has max 3 keys [5, 10, 15]. Inserting 12 adds a 4th key, exceeding capacity.

2. Step 2: Split the node and promote middle key

   The node splits into two nodes, and the middle key (10) is promoted to the parent to maintain balance.

3. Final Answer:

   Insert 12 into the leaf node, then split the node and promote the middle key to the parent -> Option D

4. Quick Check:

   Insert, split, promote middle key = balanced B-tree [OK]

Hint: Insert, then split and promote middle key if node is full [OK]

Common Mistakes:

• Discarding keys when node is full
• Merging instead of splitting on insertion
• Temporarily increasing node capacity