Suppose a B+ tree is used for indexing a database file. Consider the following…
2021
Suppose a B+ tree is used for indexing a database file. Consider the following information:
size of the search key field= 10 bytes, block size = 1024 bytes, size of the record pointer= 9 bytes, size of the block pointer= 8 bytes.
Let K be the order of internal node and L be the order of leaf node of B+ tree, then (K, L)=______.
- A.
(57, 53)
- B.
(50, 52)
- C.
(60, 64)
- D.
(34, 31)
Attempted by 43 students.
Show answer & explanation
Correct answer: A
Compute leaf node order L (maximum number of key-record pairs in a leaf):
Usable bytes in a leaf = block size - pointer to next leaf = 1024 - 8 = 1016.
Bytes per leaf entry = key size + record pointer size = 10 + 9 = 19.
Leaf order L = floor(1016 / 19) = 53.
Compute internal node order K (maximum number of block pointers in an internal node):
If m is the number of block pointers, the node stores m pointers (8 bytes each) and m - 1 keys (10 bytes each).
Space constraint: 8m + 10(m - 1) ≤ 1024 ⇒ 18m ≤ 1034 ⇒ m ≤ 57.44.
Maximum integer m = 57, so K = 57.
Final answer: (K, L) = (57, 53).
A video solution is available for this question — log in and enroll to watch it.