The order of a leaf node in a tree B+ is the maximum number of (value, data…
2007
The order of a leaf node in a tree B+ is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
- A.
63
- B.
64
- C.
67
- D.
68
Attempted by 74 students.
Show answer & explanation
Correct answer: A
Solution:
Given values:
Block size = 1 KB = 1024 bytes
Value field = 9 bytes
Data record pointer = 7 bytes
Block pointer (used for linking leaves) = 6 bytes
Step-by-step calculation:
Each (value, data record pointer) pair uses 9 + 7 = 16 bytes.
Reserve 6 bytes in the leaf for the block pointer, so usable space for pairs = 1024 - 6 = 1018 bytes.
Maximum number of pairs = floor(1018 / 16) = floor(63.625) = 63.
Therefore, the order of the leaf node is 63.
A video solution is available for this question — log in and enroll to watch it.