The order of a leaf node in a B+ tree is the maximum number of children it can…
2017
The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that block size is 1 kilobytes, the child pointer takes 7 bytes long and search field value takes 14 bytes long. The order of the leaf node is ________.
- A.
16
- B.
48
- C.
64
- D.
65
Attempted by 42 students.
Show answer & explanation
Correct answer: B
Assumptions and interpretation: each leaf entry stores a search key (14 bytes) and a data pointer (7 bytes). The leaf node also keeps a pointer to the next leaf (7 bytes).
Entry size = search key + data pointer = 14 bytes + 7 bytes = 21 bytes.
Reserve 7 bytes in the block for the pointer to the next leaf, so available space for entries = 1024 - 7 = 1017 bytes.
Maximum number of entries = floor(available space / entry size) = floor(1017 / 21) = 48.