Database-Management-System

Question 507

In a B tree of order m with p nodes the average number of splits is at most

A	1/⌈(m/2)⌉-1)
B	(⌈(m/2)⌉-1)
C	1/⌈m/2⌉
D	None

Database-Management-SystemB-and-B+-TreesUGC NET CS 2009-June-Paper-2

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,A₀,(K₁,A₁),…,(K_m,A_m), and K_i<k_{i+1, 1<=i<m

The node is split into two nodes, p and q, with the following formats:
node p: ⌈(m/2)⌉-1, A₀(K₁A_{1<`/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), …, (K_m,A_m)

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.}</m
</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,A₀,(K₁,A₁),…,(K_m,A_m), and K_i<k_{i+1, 1<=i<m

The node is split into two nodes, p and q, with the following formats:
node p: ⌈(m/2)⌉-1, A₀(K₁A_{1<`/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), …, (K_m,A_m)

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.}</m
</k}