Consider a table T in a relational database with a key field K. A B-tree of…
2004
Consider a table T in a relational database with a key field K. A B-tree of order p is used as an access structure on K, where p denotes the maximum number of tree pointers in a B-tree index node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer PD is 8 bytes long and each block pointer PB is 5 bytes long. In order for each B-tree node to fit in a single disk block, the maximum value of p is
- A.
20
- B.
22
- C.
23
- D.
32
Attempted by 34 students.
Show answer & explanation
Correct answer: C
We must ensure every B-tree node fits in a 512-byte disk block. Consider the worst-case index-node layout so the answer is safe for internal and leaf nodes.
Key sizes and pointer sizes given:
Key K = 10 bytes
Data pointer P_D = 8 bytes
Block pointer P_B = 5 bytes
Use the standard node-size accounting: a node can have up to p pointers and up to p−1 keys. To be conservative for all index-node types, consider the per-entry worst-case size in leaf-like entries (a key plus its data pointer) plus the per-entry pointer bookkeeping that consumes block-pointer space. That combined per-entry size is:
Per-entry size ≈ key + data pointer + associated block-pointer = 10 + 8 + 5 = 23 bytes
Capacity constraint (using per-entry size)
If a node holds (p − 1) full entries of 23 bytes each, then (p − 1) × 23 must be ≤ 512.
Compute the largest integer p satisfying the inequality:
(p − 1) × 23 ≤ 512
p − 1 ≤ 512 ÷ 23 = 22.086...
So p − 1 ≤ 22, hence p ≤ 23
Conclusion: The maximum order p that ensures every B-tree node fits in one 512-byte block is 23.
Quick check: (23 − 1) × 23 = 22 × 23 = 506 ≤ 512, while p = 24 would require 23 × 23 = 529 > 512, so p = 23 is the largest valid integer.
A video solution is available for this question — log in and enroll to watch it.