Question 6 If the index entries are inserted in sorted order into a B+ tree, choose the incorrect option/s about the leaf nodes. a) The new entries get directed to last leaf node if the index entries are inserted in ascending order. b) When last leaf node gets filled, it is split into two. c) If the leaf node splits when inserting in ascending order, the right node is left untouched and the insertions takes place on the left node. d) Except for the first and last leaf, the occupancy of nodes is about 50 percent if inserted in ascending or descending order.
help me with the answer and solutions in dbms
Answers
Answered by
5
The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+-tree is initially empty. 10, 3, 6, 8, 4, 2, 1. The maximum number of times leaf nodes would get split up as a result of these insertions is
(A) 2
(B) 3
(C) 4
(D) 5
Answer: (B)
Explanation:
Please see the below image to see how many times a leaf node is splitted. We have marked all the leaf and root nodes splits by *. I have used left biasing in B+ Tree construction as biasing is important in B+ tree because all the keys have to present at the leaf nodes.
In a B+ tree, insertion always happens at the leaf level, because that is where all the data resides. The nodes above the leaf level contain only keys that serve to guide the search, which may be copies of actual keys. The leaf layer is often called a ‘sequence set’ whereas the internal nodes make up the ‘index’. When a leaf splits, a suitable separator key(which is the middle one) is copied up into the index layer.
(A) 2
(B) 3
(C) 4
(D) 5
Answer: (B)
Explanation:
Please see the below image to see how many times a leaf node is splitted. We have marked all the leaf and root nodes splits by *. I have used left biasing in B+ Tree construction as biasing is important in B+ tree because all the keys have to present at the leaf nodes.
In a B+ tree, insertion always happens at the leaf level, because that is where all the data resides. The nodes above the leaf level contain only keys that serve to guide the search, which may be copies of actual keys. The leaf layer is often called a ‘sequence set’ whereas the internal nodes make up the ‘index’. When a leaf splits, a suitable separator key(which is the middle one) is copied up into the index layer.
moniyagoel:
we have to identify incorrect option
plese give answer if u know
Answered by
0
In this question, there are two incorrect entries. Incorrect entries are c) If the leaf node splits when inserting in ascending order, the right node is left untouched and the insertions takes place on the left node. d) Except for the first and last leaf, the occupancy of nodes is about 50 per cent if inserted in ascending or descending order.
Because while inserting in ascending order, insertions takes place in right node and the occupancy of nodes is about 50 percent if inserted in ascending or descending order except for the last leaf.
Similar questions