This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “B+ Tree”.

**1. Statement 1: When a node is split during insertion, the middle key is promoted to the parent as well as retained in right half-node.Statement 2: When a key is deleted from the leaf, it is also deleted from the non-leaf nodes of the tree.**

**A) Statement 1 is true but statement 2 is false**

B) Statement 2 is true but statement 1 is false

C) Both the statements are true

D) Both the statements are false

Explanation: The middle key is held in the right half node and promoted to parent node throughout the break. When a key is removed from a leaf, it is kept in non-leaves so it can still be used as a key separator in nodes below.

**2. Efficiency of finding the next record in B+ tree is ____**

A) O(n)

B) O(log n)

C) O(nlog n)**D) O(1)**

Explanation: Finding the next recored (successor) in a B+ -tree needs at most one additional leaf. As a result, the efficiency of searching for the next record is O. (1).

**3. What is the maximum number of keys that a B+ -tree of order 3 and of height 3 have?**

A) 3

B) 80

C) 27**D) 26**

Explanation: A B+ tree of order n and height h can have at most n^{h} – 1 keys. Therefore maximum number of keys = 3^{3} -1 = 27 -1 = 26.

**4. Which of the following is false?**

A) Compared to B-tree, B+ -tree has larger fanout

B) Deletion in B-tree is more complicated than in B+ -tree**C) B+ -tree has greater depth than corresponding B-tree**

D) Both B-tree and B+ -tree have same search and insertion efficiencies

Explanation: A B+ -tree has a greater fanout and therefore a shallower depth than a corresponding B-tree.

**5. Which one of the following data structures are preferred in database-system implementation?**

A) AVL tree

B) B-tree**C) B+ -tree**

D) Splay tree

Explanation: B+ -tree data structures are used in database system implementations since they can be used for multilevel indexing.

**6. In a B+ tree, both the internal nodes and the leaves have keys.**

A) True**B) False**

Explanation: Only the leaves of a B+ -tree have keys, which are repeated in non-leaf nodes to define the direction for finding individual records.

**7. Which of the following is true?**

A) B + tree allows only the rapid random access

B) B + tree allows only the rapid sequential access**C) B + tree allows rapid random access as well as rapid sequential access**

D) B + tree allows rapid random access and slower sequential access

Explanation: Since the B+ -tree is a variant of the B-tree, it allows for fast random access. The leaves of a B+ -tree are connected together, allowing for rapid sequential entry.

**8. A B+ tree can contain a maximum of 7 pointers in a node. What is the minimum number of keys in leaves?**

A) 6**B) 3**

C) 4

D) 7

Explanation: Maximum number of pointers in a node is 7, i.e. the order of the B+ -tree is 7. In a B+ tree of order n each leaf node contains at most n – 1 key and at least ⌈(n − 1)/2⌉ keys. Therefore, a minimum number of keys each leaf can have = ⌈(7 – 1)/2⌉ = 3.

**9. Which of the following is false?****a) A B+ -tree grows downwards**

b) A B+ -tree is balanced

c) In a B+ -tree, the sibling pointers allow sequential searching

d) B+ -tree is shallower than B-tree

Explanation: The growth of a B+ -tree is always upwards. In a B+tree, the path from the root to each leaf node is the same length, resulting in a balanced tree. ii) Since the leaves are related, sequential searching is possible. iii) An index is shallower than a B-tree because it is constructed with a single key per block of data rather than one key per data record.

**5. A B+ -tree of order 3 is generated by inserting 89, 9 and 8. The generated B+ -tree is __________**

A)

**B) **

C)

D)

Explanation:

A B+ tree is an m-ary tree with a variable number of children per node, but always a large number. A base, internal nodes, and leaves make up a B+ tree. A leaf or a node with two or more children may be the root. A B+ tree is a B-tree with an additional level at the bottom with connected leaves and each node containing only keys (not key–value pairs). A B+ tree’s main benefit is in storing data for fast retrieval in a block-oriented storage context, such as filesystems.