(All chapters, except Chapter 1, contain a Summary, Key Terms, Exercises and Further Readings.)
Introduction to File Structures.
The Heart of File Structure Design.
A Short History of File Structure Design.
A Conceptual Toolkit: File Structure Literacy.
Summary.
Key Terms.
Fundamental File Processing Operations.
Physical Files and Logical Files.
Opening Files.
Closing Files.
Reading and Writing.
Seeking.
Special Characters in Files.
The UNIX Directory Structure.
Physical and Logical Files in UNIX.
File-related Header Files.
UNIX Filesystem Commands.
Secondary Storage Devices and System Software.
Disks.
Magnetic Tape.
Disk Versus Tape.
Storage as a Hierarchy.
A Journey of a Byte.
Buffer Management.
I/O in UNIX.
Fundamental File Structure Concepts.
Field and Record Organization.
Record Access.
More about Record Structures.
File Access and File Organization.
Beyond Record Structures.
Portability and Standardization.
C Programs.
Pascal Programs.
Organizing Files for Performance.
Data Compression.
Reclaiming Space in Files.
Finding Things Quickly: An Introduction to Internal Sorting and Binary.
Searching.
Keysorting.
Indexing.
What Is an Index?
A Simple Index with an Entry-Sequenced File.
Basic Operations on an Indexed, Entry-Sequenced File.
Indexes That are Too Large to Hold in Memory.
Indexing to Provide Access by Multiple Keys.
Retrieval Using Combinations of Secondary Keys.
Improving the Secondary Index Structure: Inverted Lists.
Selective Indexes.
Binding.
Cosequential Processing and the Sorting Process and the Sorting of Large Files.
A Model for Implementing Cosequential Processes.
Application of the Model to a General Ledger Program.
Extension of the Model to Include Multiway Merging.
A Second Look at Sorting in RAM.
Merging as a Way of Sorting Large Files on Disk.
Sorting Files on Tape.
Sort-Merge Packages.
Sorting and Cosequential Processing in UNIX.
B-Trees and Other Tree-Structured File Organizations.
Introduction: The Invention of the B-Tree.
Statement of the Problem.
Binary Search Trees as a Solution.
AVL Trees.
Paged Binary Trees.
The Problem with the Top-down Construction of Paged Trees.
B-Trees: Working up from the Bottom.
Splitting and Promoting.
Algorithms for B-Tree searching and Insertion.
B-Tree Nomenclature.
Formal definition of B-Tree Properties.
Worst-case Search Depth.
Deletion, Redistribution, and Concatenation.
Redistribution During Insertion: A Way to Improve Storage Utilization.
B+ Trees.
Buffering of Pages: Virtual B-Trees.
Placement of Information Associated with the Key.
Variable-length Records and Keys.
C Programs to Insert Keys into a B-Tree.
Pascal Programs to Insert Keys into a B-Tree.
The B+ Tree Family and Indexed Sequential File Access.
Indexed Sequential Access.
Maintaining a Sequence Set.
Adding a Simple Index to the Sequence Set.
The Content of the Index: Separators Instead of Keys.
The Simple Prefix B+ Tree.
Simple Prefix B+ Tree Maintenance.
Index Set Block Size.
Internal Structure of Index Set Blocks: A Variable-order B-Tree.
Loading a Simple Prefix B+ Tree.
B+ Trees.
B-Trees, B+ Trees, and Simple Prefix B+ Trees in Perspective.
Hashing.
Introduction.
A Simple Hashing Algorithm.
Hashing Functions and Record Distributions.
How Much Extra Memory Should Be Used?
Collision Resolution by Progressive Overflow.
Storing More Than One Record per Address: Buckets.
Making Deletions.
Other Collision Resolution Techniques.
Patterns of Record Access.
Extendible Hashing.
Introduction.
How Extendible Hashing Works.
Implementation.
Deletion.
Extendible Hashing Performance.
Alternative Approaches.
Appendix A.
Using This Appendix.
Introduction to CD-ROM.
Physical Organization of CD-ROM.
CD-ROM Strengths and Weaknesses.
Tree Structures on CD-ROM.
Hashed Files on CD-ROM.
The CD-ROM File System.
Appendix B: ASCII Table.
Appendix C: String Functions in Pascal.
Appendix D: Comparing Disk Drives.
Bibliography.
Index. 0201557134T04062001
