WHAT we want: store many files, read/write any byte quickly, let files grow/shrink.
WHY it's hard: blocks must be allocated on disk where free space happens to be. If we demand the file occupy one solid run, growth breaks. If we scatter it freely, finding "byte 1,000,000" becomes slow.
HOW schemes differ: by where they store the "next block" pointer — inside data, in a table, or in a dedicated index block.
Pros:O(1) access, minimal metadata, great for sequential reads (no seeks).
Cons: external fragmentation (free space splits into small unusable holes); must know/guess file size in advance; growing a file may require moving it entirely.
FAT variant (the smart fix): pull all the "next" pointers out of the data blocks into one in-memory table, the File Allocation Table. Then the chain can be traversed in RAM without disk reads, and blocks become full B bytes of data.
What two numbers fully describe a contiguous file?
Start block address and length (number of blocks).
Random-access formula for contiguous allocation?
phys(i) = start_block + i, giving O(1) access.
Main drawback of contiguous allocation?
External fragmentation + must know file size in advance.
Why is random access O(n) in linked allocation?
You must follow the pointer chain from the first block; block i's address is only known after reading block i−1.
In plain linked allocation, why is usable data per block B − p?
The next-block pointer (p bytes) is stored inside the block, stealing space from data.
What does the FAT scheme do differently?
Moves all "next" pointers into one in-memory File Allocation Table, so chains traverse in RAM and blocks hold full data.
What is an inode?
Unix index node — per-file structure holding metadata plus the array of pointers (direct + indirect) to data blocks.
Why does Unix use 12 direct pointers before any indirection?
Most files are small; direct pointers give zero-overhead access to common-case tiny files (80/20).
With pointers-per-block k=B/p, what does double indirection cover?
k² data blocks (k single-indirect blocks × k pointers each).
Max file size formula for Unix inode?
12·B + k·B + k²·B + k³·B where k = B/p.
How many disk reads to read a block in the triple-indirect region?
3 pointer-block reads (single→double→triple chain) + 1 data read = depends; for triple it's reading 3 index levels then the data.
Which scheme has the best sequential read performance and why?
Contiguous — blocks are physically adjacent, minimizing disk seeks.
Recall Feynman: explain to a 12-year-old
Imagine your toys (file) need to be stored in a row of boxes (disk blocks).
Contiguous: put all toys in boxes right next to each other. Easy to find toy #5 (count from the start), but if you get more toys later, there might be no room beside them.
Linked: each box has a note saying "next toy is in box #14." You can store toys anywhere, but to reach toy #5 you must open boxes one by one following the notes.
Indexed (inode): keep one special list-box that says exactly which box holds each toy. Look at the list, jump straight to toy #5. For HUGE toy collections, the list points to more lists (indirect), like a menu of menus.
Dekho, disk basically ek lamba array hai fixed-size blocks ka (maan lo 4 KB ka ek block). File toh logically bytes ki stream hai, par physically use in blocks me scatter karna padta hai. File allocation ka kaam yahi hai: kis file ka data kaun se physical blocks me hai, aur kis order me. Teen tarike hote hain, aur teeno ek trade-off ke alag-alag corner pe baithe hain — fast access, kam waste space, aur easy growth.
Contiguous matlab saare blocks ek dusre ke saath, jaise book ke consecutive pages. Sirf start aur length store karo, aur block i ka address = start + i, ekdum O(1) fast. Problem: external fragmentation ho jaati hai aur file badi karni ho to jagah nahi milti. Linked me har block apne data ke saath next block ka pointer rakhta hai — treasure hunt jaisa, koi bhi free block use ho sakta hai (no fragmentation), par block i tak pahunchne ke liye poori chain follow karni padti hai, O(n) slow.
Indexed (inode) dono ka best mix hai: ek index block me saare pointers ki list rakho, jaise book ka table of contents. Block i ka address = Index[i], direct jump, O(1) wapas aa gaya, aur fragmentation bhi nahi. Unix isme smart trick lagata hai — 12 direct pointers chote files ke liye (jo zyada common hain, 80/20 logic), phir single, double, triple indirect bade files ke liye. Har indirection level capacity ko k = B/p guna badha deta hai, isliye max file size = 12·B + k·B + k²·B + k³·B, jo terabytes tak jaati hai. Yaad rakhna: chote file fast rahein, bade file possible rahein — yahi inode ka pura genius hai.
