File Organization and Processing

File Organization and Processing presents theories of storing information on persistent media, such as tapes and disks. It covers issues such as how a read-write head actually moves around the surface of a platter and how search algorithms (in general) can be optimized to find requested information quickly. This book is appropriate if you're designing your own operating system, but you should look elsewhere for more concrete file system information.

The beginning of the guide covers file organization and compares and contrasts sequential, direct, and indexed sequential approaches. Author Alan Tharp highlights each system's means of storing, locating, and checking information. Then the author moves on to describe data at the bit level--the actual ones and zeroes that are encoded on a piece of media to represent data. Tharp also discusses superimposed coding, a sort of efficiency routine that conserves disk space.

Tharp features a multitude of information about trees, exploring binary trees, b-trees, hashing, tree hashing, and PATRICIA trees for the benefit of his readers. Then he gets into sorting at the file-system level, explaining all the usual sorts, plus algorithms that are unique to persistent storage media. He wraps up with some exercises that illustrate his ideas.