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) = ______.
Solution
Order of Internal Node Calculation:
Key size = 10 bytes (given)
Child / Blobk pointer = 8 bytes (given)
NOTE: record pointer is not needed in non-leafy nodes.
We assume the order of internal node of B+ tree to be ‘K’.
- Block size = (K – 1) * key size + K * 8
- 1024 >= (K – 1) * 10 + K * 8
- 1024 >= 10 * K – 10 + 8 * K
- K <= (1024 + 10) / 18
- K <= 1034 / 18
- K <= 57.44
- K = 57
Order of Leaf Node Calculation:
Key size = 10 Bytes (given)
Block Pointer = 8 Bytes (given)
Record Pointer = 9 Bytes (given)
Disk Block Size = 1024 Bytes (given)
We assume the order of leaf node of B+ tree to be 'L'.
- Block size >= Block Pointer + L * (Key Field + Record Pointer)
- 1024 >= 8 + L * (10 + 9)
- 1024 >= 8 + L * (19)
- L <= (1024 - 8) / 19
- L <= 1016 / 19
- L <= 53.47
- L = 53