← 🌲 File Organisation & Indexing
Subtopic 1 of 5

7.1Disk blocks, blocking factor and file size

The idea

Records live in fixed-size disk blocks. The blocking factor is how many records fit in a block: ⌊B/R⌋. The file then needs ⌈r/bfr⌉ blocks.

Think of it like this: Packing boxes in a van: you cannot split a box, so count whole boxes per van, then the number of vans.

Why it exists

Almost every file-organisation calculation begins here.

How it works

  1. Records per block = ⌊block size / record size⌋ (floor).
  2. Blocks = ⌈records / records per block⌉ (ceil).
  3. Linear search averages half the blocks; worst case all of them.
  4. Binary search on a sorted file: ⌈log₂ b⌉ block accesses.

Worked example: B = 1024, R = 150, r = 30000.

bfr = ⌊1024/150⌋ = 6; blocks = ⌈30000/6⌉ = 5000; binary search = ⌈log₂ 5000⌉ = 13.

Now play with it

  • →Change the record size in the calculator and see the blocks change.
  • →Check the waste per block.
Records per block ⌊B/R⌋6
Blocks ⌈r/bfr⌉5000
Wasted bytes per block124
Binary search (sorted file)13 blocks
Linear search, average / worst2500 / 5000

Floor the records per block (a record does not span two blocks), then ceil the block count.

Check yourself

B = 512 bytes, R = 100 bytes, 1000 records (unspanned). Blocks needed?

Remember: Floor the records per block, ceil the blocks.
Exam notes (the dense version)

Records are stored in disk blocks. Blocking factor bfr = ⌊B / R⌋ (block size B, record size R; records do not span blocks in the unspanned case). Blocks for a file of r records: ⌈r / bfr⌉. A search on an unordered file reads b/2 blocks on average (b worst); a sorted file allows binary search in ⌈log₂ b⌉ block accesses. Always floor the records per block and ceil the blocks.

Previous year questions: File Organisation & Indexing (9)

PYQs are grouped by topic, so this is the full set for File Organisation & Indexing; try the ones that match this subtopic. Open all 9 on the topic page.