An integral part of an OS is what is known as a File System. A File System is a methodology by which data and information are stored on storage devices (hard drives, floppy disc, etc.), making them easily retrievable. Different OS’s use different file systems but all have similar features.
The most important part of the file system is the method by which files are indexed on the hard drive. This index allows the OS to know at any given time where to find a specific file on the hard drive. This index is most typically based on file names. Depending on the operating system there are different file systems and thus different indexing methods.
In the Windows environment you will find one of two file systems, each with different indexing methods. The first is known as the FAT or FAT32 file system. This system uses what is known as a File Allocation Table to index the files on the disc. This file allocation table is very simple to implement and use, however can be somewhat slow. The other file system you may encounter when using Windows XP is known as NTFS. NTFS (NT File System) uses binary trees that, while complex, allow for very fast access times.
In the Apple OS X environment you will find the HFS+ file system. HFS+ (Hierarchal File System plus) uses something known as a B-Tree to index the files on the hard discs. B-Trees (which are different than a binary tree) allow for fast access time much like the binary tree.
Depending on which "flavor" of Linux you are running you may run into several different file systems. Some of them are EXT3, EXT2, and XFS. The most common is EXT3, which is a journaling extension to the EXT2 file system on Linux. Journaling results in massively reduced time spent recovering a file system after a crash. XFS is very fast and also uses B-Trees for its file indexing