The order of an internal node in a B+ tree index is the maximum number of…
2004
The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?
- A.
24
- B.
25
- C.
26
- D.
27
Attempted by 83 students.
Show answer & explanation
Correct answer: C
Key formula: m * (pointer size) + (m - 1) * (key size) ≤ block size
Substitute pointer size = 6 bytes, key size = 14 bytes, block size = 512 bytes: 6m + 14(m - 1) ≤ 512
Simplify the inequality: 6m + 14m - 14 ≤ 512 → 20m ≤ 526 → m ≤ 526/20 = 26.3
m must be an integer, so the maximum feasible m is 26.
Verify: for m = 26 the used space is 26*6 + 25*14 = 156 + 350 = 506 bytes ≤ 512; for m = 27 used space = 27*6 + 26*14 = 162 + 364 = 526 bytes > 512 (not allowed).
Answer: The order of the internal node is 26.
A video solution is available for this question — log in and enroll to watch it.