The order of a leaf node in a B+ tree is the maximum number of (value, data…
2021
The order of a leaf node in a B+ tree 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 75 students.
Show answer & explanation
Correct answer: A
Key insight: a B+ tree leaf node stores (value, data record pointer) pairs plus one extra block pointer that chains it to the next leaf. So its order — the maximum number of pairs it can hold — is order = floor((block size − block pointer size) / (value size + record pointer size)).
Pair size = value field + data record pointer = 9 + 7 = 16 bytes.
Usable bytes in the leaf block = block size − block pointer = 1024 − 6 = 1018 bytes.
Order = floor(1018 / 16) = floor(63.625) = 63.
Cross-check: 63 pairs plus the leaf's 6-byte block pointer use 63 × 16 + 6 = 1014 bytes, leaving 1024 − 1014 = 10 bytes spare in the 1024-byte block — so 63 pairs fit. One more pair (64) would alone need 64 × 16 = 1024 bytes, already the entire block, leaving no room for the 6-byte block pointer, so 64 pairs do not fit. This confirms 63 is the maximum.
Therefore the maximum number of (value, data record pointer) pairs a leaf can hold — the order of the leaf node — is 63.
A video solution is available for this question — log in and enroll to watch it.