File Structures: The Heart of the file structure Design, A ShortHistory of File Structure Design, A Conceptual Toolkit; Fundamental FileOperations: Physical Files and Logical Files, Opening Files, Closing Files,Reading and Writing, Seeking, Special Characters, The Unix DirectoryStructure, Physical devices and Logical Files, File-related Header Files,UNIX file System Commands; Secondary Storage and System Software:Disks, Magnetic Tape, Disk versus Tape; CD-ROM: Introduction, PhysicalOrganization, Strengths and Weaknesses; Storage as Hierarchy, A journey ofa Byte, Buffer Management, Input /Output in UNIX.
Field and Record Organization, Using Classes to Manipulate Buffers, UsingInheritance for Record Buffer Classes, Managing Fixed Length, Fixed FieldBuffers, An Object-Oriented Class for Record Files, Record Access, Moreabout Record Structures, Encapsulating Record Operations in a Single Class,File Access and File Organization.
Data Compression,Reclaiming Space in files, Internal Sorting and Binary Searching,Keysorting; What is an Index? A Simple Index for Entry-Sequenced File,Using Template Classes in C++ for Object I/O, Object-Oriented support forIndexed, Entry-Sequenced Files of Data Objects, Indexes that are too largeto hold in Memory, Indexing to provide access by Multiple keys, RetrievalUsing Combinations of Secondary Keys, Improving the Secondary Indexstructure: Inverted Lists, Selective indexes, Binding.
A Model for Implementing Cosequential Processes, Application of the Model to a GeneralLedger Program, Extension of the Model to include Mutiway Merging, ASecond Look at Sorting in Memory, Merging as a Way of Sorting Large Fileson Disk.
The invention of B-Tree, Statement ofthe problem, Indexing with Binary Search Trees; Multi-Level Indexing, BTrees,Example of Creating a B-Tree, An Object-Oriented Representation ofB-Trees, B-Tree Methods; Nomenclature, Formal Definition of B-TreeProperties, Worst-case Search Depth, Deletion, Merging and Redistribution,Redistribution during insertion; B* Trees, Buffering of pages; Virtual BTrees;Variable-length Records and keys.
Indexed Sequential Access, Maintaining a Sequence Set, Adding a Simple Index to the SequenceSet, The Content of the Index: Separators Instead of Keys, The Simple PrefixB+ Tree and its maintenance, Index Set Block Size, Internal Structure ofIndex Set Blocks: A Variable-order B- Tree, Loading a Simple Prefix B+Trees, B-Trees, B+ Trees and Simple Prefix B+ Trees in Perspective.
Introduction, A Simple Hashing Algorithm, Hashing Functions andRecord Distribution, How much Extra Memory should be used?, Collisionresolution by progressive overflow, Buckets, Making deletions, Othercollision resolution techniques, Patterns of record access.
How Extendible Hashing Works, Implementation,Deletion, Extendible Hashing Performance, Alternative Approaches.