In a file with 1 million records and with an order of the tree being 100, find…
2021
In a file with 1 million records and with an order of the tree being 100, find out the maximum number of nodes to be accessed if a B+ tree index is used.
- A.
5
- B.
4
- C.
3
- D.
10
- E.
Question not attempted
Attempted by 141 students.
Show answer & explanation
Correct answer: C
Concept: In a B+ tree index of order m (fan-out m), each level of the tree multiplies the number of reachable entries by m. A search descends one node per level from the root to the leaf, so the maximum number of nodes accessed equals the height (number of levels), which is the smallest h with mh ≥ n, i.e. h = ⌈logₘ n⌉.
Application: here the fan-out is m = 100 and the file has n = 1,000,000 records. Find the smallest h such that 100h ≥ 1,000,000:
1001 = 100 — far below 1,000,000.
1002 = 10,000 — still below 1,000,000.
1003 = 1,000,000 — reaches exactly the record count, so h = 3 levels suffice.
Cross-check: h = ⌈log₁₀₀(1,000,000)⌉ = ⌈log₁₀₀(10⁶)⌉ = ⌈6/2⌉ = 3. A search therefore touches one node at each of the 3 levels (root → internal → leaf), so the maximum number of nodes accessed is 3.