indexed allocation

Think of a book's index at the back. Instead of flipping page by page to find every mention of a topic, you turn to one page that lists all the relevant page numbers in order, and jump straight to any of them. Indexed allocation gives each file its own little index: a single block, the index block, that holds an ordered list of the disk-block addresses making up the file.

When a file is created, the file system sets aside one index block for it. Slot 0 of the index block holds the address of the file's first data block, slot 1 holds the second, and so on; an empty slot (often a special null value) marks blocks not yet used. To read the file's i-th block you simply look at slot i of the index block and go straight there — true random access, no chain to walk. The directory entry just points at the index block. This keeps all the pointers together (like FAT) but per-file (unlike FAT's one giant table), so the pointers a file needs are loaded together when the file is opened.

Indexed allocation cures the two big linked-allocation problems at once: there is no external fragmentation (blocks can be anywhere) and random access is fast (one lookup, not a walk). Its own problem is the size of the index block. A small file wastes most of an index block (internal waste), while a very large file may need more pointers than one index block can hold. The classic Unix answer to that second problem is to make the index multi-level — adding indirect blocks — which is the next idea.