The study of files is too often a mixture of hardware characteristics, data structures, and ad hoc solutions found in various operating systems. This book, however, presents a clear view of how to structure data on storage devices. The goal of most books in this genre is to teach file organizations. What we see is the result of the design process without getting much insight into the requirements, constraints, and history that went into that design. We learn the details of manufacturers’ specific systems without coming away with any general application design principles.
Folk and Zoellick reverse this approach by helping the reader develop design judgment. They teach a toolkit of design concepts (hence the title), that the reader can take away and apply in any systems environment, including future ones. The book is not for reference or for scanning but is intended to be read cover to cover. The authors carefully develop ideas from chapter to chapter, starting with the simple view of a file as a stream of bytes and logically building more powerful and complex file structures.
This approach is ideal for one intended audience: computer professionals who want to learn more about file structure design. Its readability will also make it attractive to its main audience of undergraduate computer science majors. It is not a background book for an existing file course. Rather it is a comprehensive file structures course in itself. To use this book effectively, an instructor must be willing to take a new view towards the teaching of file structures.
Chapter 1 provides an excellent introduction to the differences between file strutures and data structures. Chapters 2 to 5 lay out the fundamentals. The file processing operations of creating, opening, reading, writing, and seeking are shown in both Turbo Pascal and C. There is a clear discussion on secondary storage devices and how their organization affects performance. Both magnetic tape and disk are presented in detail, with spacing and timing calculations. Fields, records, fixed length versus variable length data, and the need for file maintenance are covered.
Chapters 6 and 7 present simple retrieval stragies, that is, techniques suitable for files that fit in memory. This includes internal sorting, binary searching, and memory resident indexes. “Consequential Processing” is the title of chapter 8, by which the authors mean the matching, merging, and updating of sequential files. Tree-structured files are covered in chapters 9 and 10. B-trees are extensively discussed. Algorithms are given for searching and inserting, while deletion is shown with examples. B+-trees are presented as the basis of indexed sequential file access. The emphasis is on how these concepts can be implemented in practical database applications. A surprisingly thorough discussion of hashing algorithms, collision resolution, and the use and performance of hashed files completes the text with chapter 11.
Chapters are organized with objectives, a summary, key terms, exercises, programming exercises, and further readings. Algorithms are most often described with a Pascal-like psuedocode. Programming examples are given in Turbo Pascal and C. Appendices provide additional technical information on file processing in Turbo Pascal and an introduction to C. An instructor’s manual containing answers to exercises and example examination questions is also available.
