A · Compressed recap
Cost unit: block access (seek + rotational latency (half a rotation on average) + transfer). bfr = ⌊B/R⌋ (unspanned), b = ⌈r/bfr⌉; spanned b = ⌈r·R/B⌉ with no waste (needed when R > B). Pointers: block pointer P, record pointer Pr.
Heap: search b/2 average if found, b if missing or non-key; cheap append. Sorted: binary search ⌈log₂ b⌉ on the ordering field only; inserts/deletes shift ~b/2 blocks. Hashed: ~1 access for equality on the hash field; useless for ranges and other fields.
B · Merged rule card
5.1.1 Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
- Cost unit = block access (seek + rotational latency + transfer); avg latency = half a rotation.
- bfr = ⌊B / R⌋ (unspanned); b = ⌈r / bfr⌉.
- Spanned: b = ⌈r·R / B⌉, no waste; needed when R > B.
- Block pointer P vs record pointer Pr.
5.2.1 File organization: heap, sorted, hashed; cost of search/insert/delete
- log₂ b = power of 2 giving b; use ⌈log₂ b⌉ for whole steps.
- Heap: search b/2 avg (exists), b (missing or non-key); insert ~1.
- Sorted: ⌈log₂ b⌉ on the ordering field only; insert/delete ~b/2.
- Hashed: ~1 for equality on the hash field (+ overflow); no help for ranges.
C · Interleaved GATE-style questions
Q1 · NAT · 1 mark(s) — bfr
B = 1024, R = 120, unspanned. bfr?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Blocks
r = 100,000, R = 120, B = 1024, unspanned. How many blocks?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — Waste
B = 1024, R = 120, unspanned. How many bytes are wasted per block?
Numerical answer: ________
Q4 · NAT · 1 mark(s) — Binary search
A sorted file has 12,500 blocks. Block accesses for binary search on the ordering field?
Numerical answer: ________
Q5 · NAT · 1 mark(s) — Heap
A heap file of 12,500 blocks is searched on a non-key field. Block accesses?
Numerical answer: ________
Q6 · MCQ · 1 mark(s) — Organisation
Which organisation suits "find all students with roll between 200 and 300" best?
- (A) File hashed on name
- (B) Heap
- (C) File sorted on roll
- (D) File hashed on roll
Q7 · MCQ · 2 mark(s) — Latency
A disk at 5,400 rpm has an average seek time of 9 ms. Ignoring transfer time, the average time to access a block is closest to:
- (A) 20.1 ms
- (B) 14.6 ms
- (C) 9 ms
- (D) 5.6 ms
Q8 · MSQ · 2 mark(s) — Facts
Which are true?
- (A) Binary search works on any field of a sorted file.
- (B) Spanned records avoid wasted space at block ends.
- (C) A heap file allows constant-time append.
- (D) Hashing gives about one block access for equality on the hash key.
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: 8 · 1 mark(s)
⌊1024/120⌋ = 8.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q2 Answer: 12500 · 2 mark(s)
bfr 8; 100000/8 = 12,500.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q3 Answer: 64 · 2 mark(s)
1024 − 8 × 120 = 64.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q4 Answer: 14 · 1 mark(s)
2¹⁴ = 16384 ≥ 12500 > 8192.
Re-read: Lesson 5.2.1 — File organization: heap, sorted, hashed; cost of search/insert/delete
Q5 Answer: 12500 · 1 mark(s)
All blocks.
Re-read: Lesson 5.2.1 — File organization: heap, sorted, hashed; cost of search/insert/delete
Q6 Answer: (C) · 1 mark(s)
Binary search to 200, then consecutive blocks.
- (A) is wrong: Wrong field.
- (B) is wrong: Full scan.
- (D) is wrong: Hashing scatters ranges.
Re-read: Lesson 5.2.1 — File organization: heap, sorted, hashed; cost of search/insert/delete
Q7 Answer: (B) · 2 mark(s)
Rotation = 60000/5400 = 11.1 ms; half = 5.6 ms; 9 + 5.6 = 14.6 ms.
- (A) is wrong: Uses a full rotation.
- (C) is wrong: Ignores latency.
- (D) is wrong: Ignores seek time.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q8 Answer: (B) (C) (D) · 2 mark(s)
Binary search needs the ordering field.
- (A) is wrong: Only the ordering field.
Re-read: Lesson 5.2.1 — File organization: heap, sorted, hashed; cost of search/insert/delete