Foundations — File allocation — contiguous, linked, indexed (inode)

Before you can read the parent note (File allocation — contiguous, linked, indexed (inode)), you must be fluent in the tiny alphabet it uses without stopping to explain. This page builds each letter from nothing.

0. The disk as an array of boxes

The whole subject rests on one picture: the disk is a row of numbered boxes, all the same size.

1. $B$ — the block size (bytes per box)

• Plain words: how much data one box can hold.
• Picture: the height of a single box in the shelf figure — a container of capacity $B$.
• Why the topic needs it: every "how many boxes does this file need?" and "which box holds byte 9000?" question is a division or multiplication by $B$. It is the conversion rate between bytes (what users think in) and blocks (what disks think in).

2. A byte, and byte-numbering inside a file

• Picture: if a block is a box, a byte is one tiny cell inside it. A block of $B=4096$ has cells numbered $0$ to $4095$.
• Why the topic needs it: users ask "give me byte 9000." The OS must translate that flat byte-number into (which box, which cell inside it). That translation is the heart of every scheme.

3. Logical block $i$ vs. physical block $b$

This is the single most important distinction on the whole parent page. Two different numbering systems live side by side.

• Picture: the top row in the figure is the file's own pieces $i=0,1,2,3$; the arrows drop down to scattered boxes on the disk $b=50,51,90,12$. Same data, two names.
• Why the topic needs it: allocation is the function that turns a logical $i$ into a physical $b$. Every formula on the parent page — $\text{phys}(i)=b+i$, $\text{phys}(i)=\text{Index}[i]$ — is just a different rule for that same arrow.

4. $L$ — file length in blocks

• Plain words: how many boxes this file needs.
• Picture: count the top-row pieces in the mapping figure — that count is $L$.
• Why the topic needs it: contiguous allocation stores exactly the pair $(b,L)$ and nothing else. $L$ also tells us the valid range of $i$: asking for block $L$ or beyond is reading past the end of the file.

5. Turning a byte number into (block, offset)

Now we can read the parent's very first worked example symbol-for-symbol.

• Picture: lay the file's bytes end to end and slice every $B$ bytes into a box. The floor tells you which box a byte fell into; the modulo tells you how far in (the cell).

6. $p$ — the pointer size

• Picture: a small arrow drawn inside a box, pointing at another box. Drawing that arrow costs $p$ bytes of the box's own space.
• Why the topic needs it:
  • In linked allocation the pointer lives inside each data box, so usable data is $B_{\text{data}}=B-p$.
  • In indexed allocation an index box is filled entirely with pointers, so it holds $B/p$ of them.

7. $k$ — pointers per block

• Picture: an empty box divided into $k$ little slots, each slot holding one arrow.
• Why the topic needs it: this single number drives the entire inode size calculation. One index box reaches $k$ data blocks; each extra level of indirection multiplies reach by $k$ again → $k$, $k^2$, $k^3$.
• Numbers: with $B=4096$, $p=4$: $k=4096/4=1024$.

8. Big-O — the cost language ($O(1)$ vs $O(n)$)

• Picture: two curves against file position. $O(1)$ is a flat line (always one lookup). $O(n)$ is a rising straight line (block $i$ costs $i+1$ reads).
• Why the topic needs it: it is the yardstick the whole comparison table uses. "Fast random access" means $O(1)$; "slow random access" means $O(n)$. Contiguous and indexed are $O(1)$; plain linked is $O(n)$.

9. Two words you'll meet: fragmentation & inode

Prerequisite map

Every arrow says "you need the left idea before the right one makes sense." Everything funnels into the three schemes on the parent note.

Related vault topics

• Free Space Management (bitmap, free list) — how the OS finds a free box to hand out.
• File Systems (ext4, FAT, NTFS) — real systems that implement these schemes.
• Directory Structure — where the "start block" / "inode number" is actually stored.
• Disk Scheduling — the cost of a "seek" that makes contiguous layout attractive.
• Virtual Memory Paging — the same logical→physical mapping idea, for RAM.
• 🇮🇳 Hinglish version

Equipment checklist