Database-Management-System
August 29, 2024Database-Management-System
August 29, 2024Database-Management-System
| Question 507 |
In a B tree of order m with p nodes the average number of splits is at most
| 1/⌈(m/2)⌉-1) | |
| (⌈(m/2)⌉-1) | |
| 1/⌈m/2⌉ | |
| None |
Question 507 Explanation:
Leaf Nodes=p
keys=m
To split the node, assume that following the insertion of the new key, p has the format
m,A0,(K1,A1),…,(Km,Am), and Ki<ki+1, 1<=i<m
The node is split into two nodes, p and q, with the following formats:
node p: ⌈(m/2)⌉-1, A0(K1A1<`/sub>), …, (K⌈(m/2)⌉-1, A⌈(m/2)⌉-1)
node q: m-⌈(m/2)⌉, A⌈(m/2)⌉, (K⌈(m/2)⌉+1, A⌈(m/2)⌉+1), …, (Km,Am)
The remaining key, K⌈(m/2)⌉-1, and a pointer to the new node,q, from a tuple(K⌈(m/2)⌉,q).
</k
keys=m
To split the node, assume that following the insertion of the new key, p has the format
m,A0,(K1,A1),…,(Km,Am), and Ki<ki+1, 1<=i<m
The node is split into two nodes, p and q, with the following formats:
node p: ⌈(m/2)⌉-1, A0(K1A1<`/sub>), …, (K⌈(m/2)⌉-1, A⌈(m/2)⌉-1)
node q: m-⌈(m/2)⌉, A⌈(m/2)⌉, (K⌈(m/2)⌉+1, A⌈(m/2)⌉+1), …, (Km,Am)
The remaining key, K⌈(m/2)⌉-1, and a pointer to the new node,q, from a tuple(K⌈(m/2)⌉,q).
→ This is to be inserted into the parent of p. Before attempting this the nodes p and q are written to disk.
</k
Correct Answer: B
Question 507 Explanation:
Leaf Nodes=p
keys=m
To split the node, assume that following the insertion of the new key, p has the format
m,A0,(K1,A1),…,(Km,Am), and Ki<ki+1, 1<=i<m
The node is split into two nodes, p and q, with the following formats:
node p: ⌈(m/2)⌉-1, A0(K1A1<`/sub>), …, (K⌈(m/2)⌉-1, A⌈(m/2)⌉-1)
node q: m-⌈(m/2)⌉, A⌈(m/2)⌉, (K⌈(m/2)⌉+1, A⌈(m/2)⌉+1), …, (Km,Am)
The remaining key, K⌈(m/2)⌉-1, and a pointer to the new node,q, from a tuple(K⌈(m/2)⌉,q).
</k
keys=m
To split the node, assume that following the insertion of the new key, p has the format
m,A0,(K1,A1),…,(Km,Am), and Ki<ki+1, 1<=i<m
The node is split into two nodes, p and q, with the following formats:
node p: ⌈(m/2)⌉-1, A0(K1A1<`/sub>), …, (K⌈(m/2)⌉-1, A⌈(m/2)⌉-1)
node q: m-⌈(m/2)⌉, A⌈(m/2)⌉, (K⌈(m/2)⌉+1, A⌈(m/2)⌉+1), …, (Km,Am)
The remaining key, K⌈(m/2)⌉-1, and a pointer to the new node,q, from a tuple(K⌈(m/2)⌉,q).
→ This is to be inserted into the parent of p. Before attempting this the nodes p and q are written to disk.
</k