Table of contents
1.
B and B+ trees
2.
Key Takeaways
Last Updated: Mar 27, 2024

B and B+ Trees

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

B and B+ trees

Question 1

If the maximum number of keys in a node in a B+ tree is 5, find the minimum number of keys in any non-root node?

  1. 1
  2. 2
  3. 3
  4. 4

Ans: B

It is given that the maximum number of keys is 5. Therefore a node can have at most 6 children. The minimum number of children of a node = max/2 = 6/2 = 3. Thus, the minimum number of keys a child node can have is 3 - 1 = 2.

Question 2

What is a major factor for preferring B-trees over binary search trees for indexing Database relations?

  1. A large number of records in a database
  2. Sorted database relations on the primary key
  3. B-trees use less memory
  4. Data is transferred from the disk in the form of blocks.

Answer: D

A single node can contain multiple keys in a B-tree, while in a binary search tree, one node contains only one key. Since a disk block has many keys, it is better to use B-tree so that the tree height is small.

Question 3

Why are B+ trees preferred over B-trees for database relations?

  1. The Capacity of disks is greater than memory.
  2. Disk access is slower than memory access.
  3. Data transfer rates of disks are much less than memory.
  4. Disks are more reliable than memory.

Answer: B

B+ trees use less number of disk hits to search for a result. Since disk accesses are slower, it is better to use B+ trees.

Question 4

Find the incorrect statement about B trees.

  1. B trees grow upward
  2. The time complexity of the B tree is less than the Red-Black tree.
  3. The number of child pointers in a B tree is always equal to the number of keys + 1.
  4. The minimum degree of a B tree depends on block size, key and address sizes.

Answer: B

Both the B tree and the Red-black tree have O(logN) time complexity.

Question 5

What is the maximum number of node splitting operations when a B-tree of order 4 is built from scratch by 10 successive insertions?

  1. 3
  2. 4
  3. 5
  4. 6

Answer: C

Consider a B-tree of order 4 and the 10 insertions as:

10 20 30 40 5 8 15 12 17 13

The final B-tree will look like this:

The number of node splitting operations while forming the above B-tree is 5.

Question 6

If the block size is 1K bytes, the data record pointer is 7 bytes long, the value field is 9 bytes long, and the block pointer is 6 bytes long, find the order of the leaf node in a B+ tree.

  1. 63
  2. 64
  3. 67
  4. 68

Answer: A

Let the order of the leaf node be m. A leaf node can contain m record pointers, m values, and one block pointer. Thus the total size of the block will be r * m + V * m + p.

Given that block size is 1K bytes:

7*m + 9*m + 6 = 1024

16m = 1018

m = 63

Question 7

If a child pointer uses 6 bytes, search field value uses 14 bytes, and the block size uses 512 bytes, what will be the order of the internal node.

  1. 24
  2. 25
  3. 26
  4. 27

Answer: C

Let the order of the B+ tree be n.

block size = (n-1) * key size + n * child pointer

(n-1)*14 + n*6 = 512

n = (512 + 14)/20

n = 26.3 = 26

Question 8

It is required to build a B+ tree on the Name attribute of the Student table. Assume that the name column has a length of 8 bytes, the disk block size is 512 bytes, and index pointers have a size of 4 bytes. What would be the best choice of degree for the B+ tree? 

  1. 16
  2. 42
  3. 43
  4. 44

Answer: C

Memory required by 1 record = 8 + 4 = 12 bytes.

Let the order of the B+ tree be N. 

12 * N + 4 = 512

12N = 516

N = 43

Question 9

Consider the following B+ tree. Find the number of nodes that need to be accessed to execute the following query: “Get records where search key >= 7 and < 15”.

  1. 4
  2. 5
  3. 6
  4. 7

Answer: B

To get all the values between 7 and 15, we first access the leaf node containing 7. Once this node is found, we linearly traverse to the right till 15 is found. The total number of nodes accessed will be 5.

Here is the diagram showing the nodes accessed:

Question 10

Given that a file contains 1 million records and the order of the B+ tree is 100. Find the maximum number of nodes that need to be accessed to fetch a record?

  1. 5
  2. 4
  3. 3
  4. 10

Answer: B

Number of records = 10^6

Order of B+ tree = 100

Max pointers per node = order = 100

Minimum pointers per node = max/2 = 50

Max no. of nodes at last level = 10^6/50 = 2*10^4

Number of nodes in second last level = 2*10^4/50 = 400

Number of nodes in third last level = 400/50 = 8

Number of nodes in fourth last level = 1

Thus, the maximum number of nodes accessed = level of B+ tree = 4.
Check out this problem - Largest BST In Binary Tree

Key Takeaways

In this article, we discussed various quality multiple-choice questions based on B and B+ trees. We hope that this blog has helped you enhance your knowledge of syntax analysis and if you would like to learn more, check out our articles on code studio. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass