Consider a B+ tree in which the search key is 12 bytes long, block size is…
2015
Consider a B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is ____________.
Attempted by 144 students.
Show answer & explanation
Correct answer: 50
Answer: 50 keys
Explanation:
Let n be the number of keys in a non-leaf node. A non-leaf node stores n keys (each 12 bytes) and n+1 child pointers (each 8 bytes).
Total space used: 12n + 8(n + 1) bytes, which must be ≤ 1024 bytes (block size).
Solve: 12n + 8n + 8 ≤ 1024 ⇒ 20n + 8 ≤ 1024 ⇒ 20n ≤ 1016 ⇒ n ≤ 50.8.
Maximum integer n is 50, so the maximum number of keys per non-leaf node is 50.
Note: The record pointer size (10 bytes) is not used in internal (non-leaf) nodes, since they store child block pointers.
A video solution is available for this question — log in and enroll to watch it.