the free-space bitmap
Picture a wall of mailboxes in an apartment lobby, each with a little flag: flag up means the box is empty and available, flag down means it is taken. To find a free box you scan the flags; to claim one you flip its flag down. The free-space bitmap is exactly this wall of flags for disk blocks — one bit per block, where the bit says free or used.
Concretely, the file system keeps an array of bits, one for each block on the volume. By convention a 1 might mean free and a 0 used (systems differ; the convention is fixed per file system). Block number n is represented by bit n, so checking whether block 1574 is free is just reading bit 1574, and claiming it is clearing or setting that single bit. Two things make bitmaps attractive. First, they are compact: one bit per block means a 1 TB disk with 4 KB blocks needs only about 32 MB of bitmap, small enough to keep in memory. Second, they make finding a run of contiguous free blocks easy and fast, because you scan for a stretch of consecutive free bits — exactly what contiguous allocation needs. Many CPUs even have an instruction to find the first set bit in a word, speeding the scan.
The bitmap is the most common free-space structure in real file systems (ext, for instance, uses block bitmaps and inode bitmaps). Its honest weakness is that on a very large volume the bitmap itself is large, and scanning a nearly full disk for the last few free blocks can be slow. Like all free-space metadata, the bitmap must be kept consistent with the actual allocation: a crash that updates data but not the bitmap, or vice versa, leaves the file system needing repair.
A 16-block volume's bitmap reads 1100 1111 0011 1110, where 1 = free. Blocks 2, 3, 8, 9, and 15 are used; everything else is free. To allocate two contiguous blocks, the file system scans for two adjacent 1s and finds blocks 4 and 5, then flips bits 4 and 5 to 0.
One bit per block: scanning for free bits, especially contiguous runs, is fast and compact.
A bitmap excels at finding contiguous free runs cheaply, but on a huge nearly-full volume the scan for the last free blocks can be slow, and the whole bitmap must be kept crash-consistent with actual allocations.