A file allocation table (FAT) is a table that an OperatingSystem maintains on a HardDisk that provides a map of the clusters (the basic units of logical storage on a hard disk) that a file has been stored in. When you write a new file to a hard disk, the file is stored in one or more clusters that are not necessarily next to each other; they may be rather widely scattered over the disk. A typical cluster size is 2,048 bytes, 4,096 bytes, or 8,192 bytes. The operating system creates a FAT entry for the new file that records where each cluster is located and their sequential order. When you read a file, the operating system reassembles the file from clusters and places it as an entire file where you want to read it. For example, if you were to save this Wiki page to your hard disk, it may very well be stored on more than one cluster on your hard disk.

Note that most modern OS's don't have a centralised FAT anymore, but use Inodes and bitmaps. an inode specifies where data for an individual file is (by direct, indirect, and double and triple indirect pointers), while the bitmap is of which blocks within a zone or group are in use. If you have a very sophisticated FileSystem then inodes may be created on the fly, with others the maximum number of inodes on a partition is fixed at format time.

df -i .

will show you how many inodes are free on a filesystem. It is rare to run out of inodes unless you have a really weird partition (for instance a news spool).

Some much newer filesystems (such as ReiserFS) don't use a FAT or inodes/bitmaps for their allocation, but use a tree structure.