Question 64

Parameters:

• Block size $B = 4\text{ KB} = 4096\text{ bytes}$
• Search key size $K = 12\text{ bytes}$
• Pointer size $P = 8\text{ bytes}$
• Number of records $N = 1,000,000 = 10^6$

Capacities of B+ tree nodes:

• Internal node: holds $p$ pointers and $p - 1$ keys:
  $$p \cdot P + (p - 1) \cdot K \le B \implies 8p + 12(p - 1) \le 4096 \implies 20p \le 4108 \implies p \le 205$$
• Leaf node: holds $k$ key-pointer pairs and 1 block pointer to the next leaf:
  $$k(K + P) + P \le B \implies 20k + 8 \le 4096 \implies 20k \le 4088 \implies k \le 204$$

Minimum height of B+ tree to index $10^6$ records:

• To minimize height (and disk accesses), consider maximum fanout:
  • Level 1 (Root): 1 node, up to 205 pointers.
  • Level 2 (Internal): up to 205 nodes, up to $205 \times 205 = 42,025$ pointers.
  • Level 3 (Leaf nodes): 42,025 leaf nodes can hold up to $42,025 \times 204 \approx 8.57 \times 10^6$ records, easily accommodating $10^6$ records.
• Thus, the minimum tree height is 3 levels.

Total disk accesses:

• 1 access for root node (Level 1)
• 1 access for internal node (Level 2)
• 1 access for leaf node (Level 3)
• 1 access for the data block containing the actual record
• Total minimum disk accesses = $3 + 1 = 4$.