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 ____
B) O(log n)
C) O(nlog n)
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?
Explanation: A B+ tree of order n and height h can have at most nh – 1 keys. Therefore maximum number of keys = 33 -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
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.
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?
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+ 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.