A B+ tree index is to be built on the name attribute of the STUDENT relation.…
2012
A B+ tree index is to be built on the name attribute of the STUDENT relation. Assume that every student name is 8 bytes long, disk blocks are 512 bytes, and index pointers are 4 bytes. What is the best choice for the degree (the number of pointers per internal node) of the B+ tree?
Answer: C. 43 — ConceptAn internal B+ tree node with p pointers stores p pointers and p − 1 search-key values. If the pointer size is P bytes, key size is K bytes, and block…
- A.
16
- B.
42
- C.
43
- D.
44
Attempted by 37 students.
Show answer & explanation
Correct answer: C
Concept
An internal B+ tree node with p pointers stores p pointers and p − 1 search-key values.
If the pointer size is P bytes, key size is K bytes, and block size is B bytes, the capacity condition is pP + (p − 1)K ≤ B.
Application
Here, P = 4 bytes, K = 8 bytes, and B = 512 bytes.
Substitute the values: 4p + 8(p − 1) ≤ 512.
Simplify: 4p + 8p − 8 ≤ 512, so 12p ≤ 520.
Therefore p ≤ 43.33..., and the largest permissible integer degree is 43.
Cross-check
For p = 43, the node uses 43 × 4 + 42 × 8 = 508 bytes, which fits in one 512-byte block.
For p = 44, it would use 44 × 4 + 43 × 8 = 520 bytes, which exceeds the block size.
Hence, the best choice for the degree is 43.