06IS65 - File Structures |
PART – A |
UNIT 1 |
INTRODUCTION: File Structures: The Heart of the file structure Design,
A Short History of File Structure Design, A Conceptual Toolkit;
Fundamental File Operations: Physical Files and Logical Files, Opening
Files, Closing Files, Reading and Writing, Seeking, Special Characters, The
Unix Directory Structure, 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,
Physical Organization, Strengths and Weaknesses; Storage as Hierarchy, A
journey of a Byte, Buffer Management, Input /Output in UNIX. |
UNIT 2 |
FUNDAMENTAL FILE STRUCTURE CONCEPTS, MANAGING
FILES OF RECORDS: Field and Record Organization, Using Classes to
Manipulate Buffers, Using Inheritance for Record Buffer Classes, Managing
Fixed Length, Fixed Field Buffers, An Object-Oriented Class for Record
Files, Record Access, More about Record Structures, Encapsulating Record
Operations in a Single Class, File Access and File Organization. |
UNIT 3 |
ORGANIZATION OF FILES FOR PERFORMANCE, INDEXING:
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 for Indexed, Entry-Sequenced Files of Data Objects,
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. |
UNIT 4 |
COSEQUENTIAL PROCESSING 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
Mutiway Merging, A Second Look at Sorting in Memory, Merging as a Way
of Sorting Large Files on Disk. |
PART – B |
UNIT 5 |
MULTI-LEVEL INDEXING AND B-TREES: The invention of B-Tree,
Statement of the problem, Indexing with Binary Search Trees; Multi-Level
Indexing, B-Trees, Example of Creating a B-Tree, An Object-Oriented
Representation of B-Trees, B-Tree Methods; Nomenclature, Formal
Definition of B-Tree Properties, Worst-case Search Depth, Deletion, Merging
and Redistribution, Redistribution during insertion; B* Trees, Buffering of
pages; Virtual B-Trees; Variable-length Records and keys.
|
UNIT 6 |
INDEXED SEQUENTIAL FILE ACCESS AND PREFIX B + TREES:
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 and its maintenance, Index Set Block Size,
Internal Structure of Index Set Blocks: A Variable-order B- Tree, Loading a
Simple Prefix B+ Trees, B-Trees, B+ Trees and Simple Prefix B+ Trees in
Perspective |
UNIT 7 |
HASHING: Introduction, A Simple Hashing Algorithm, Hashing Functions
and Record Distribution, How much Extra Memory should be used?,
Collision resolution by progressive overflow, Buckets, Making deletions,
Other collision resolution techniques, Patterns of record access. |
UNIT 8 |
EXTENDIBLE HASHING: How Extendible Hashing Works,
Implementation, Deletion, Extendible Hashing Performance, Alternative
Approaches. |
REFERENCE |
TEXT BOOKS: |
1. File Structures-An Object Oriented Approach with C++ -
Michael J. Folk, Bill Zoellick, Greg Riccardi, 3rd Edition, Addison-
Wesley, 1998.
|
Reference Books |
1. File Structures Using C++ - K.R. Venugopal, K.G. Srinivas, P.M.
Krishnaraj, Tata McGraw-Hill, 2008.
2. C++ Components and Algorithms - Scot Robert Ladd, BPB
Publications, 1993.
3. Database Management Systems - Raghu Ramakrishan and
Johannes Gehrke, 3rd Edition, McGraw Hill, 2003. |
|