Syllabus of Andhra University BTech Computer Science Engineering - CSE 3.1.5 - File Structures

Third year - First Semester

Instruction: 3 Periods & 1 Tut /week
Univ. Exam : 3 Hours

Sessional Marks: 30
Univ-Exam-Marks:70

File Processing Operations

Physical and logical files, opening, reading & writing and closing files in C, seeking and special charactersin files, physical devices and logical files, file-related header files in C

Secondary Storage

Disks – organization, tracks, sectors, blocks, capacity, non-data overhead, cost of a disk access,MagneticTape – types, performance, organization estimation of tape length and data transmission times, disk vstape,CD-ROM – CD-ROM as a file structure, physical organization, strengths and weakness of cd-roms,storage hierarchy

Byte Journey and buffer Management

File manager, I/O buffer, I/O processing, buffer strategies and bottlenecks

File Structure Concepts

A stream file, field structures, reading a stream of fields, record structures and that uses a length indicator,Mixing numbers and characters – use of a hex dump, reading the variable length records from the files

Managing records in C files

Retrieving records by keys, sequential search, direct access, choosing a record structure and record length,header records, file access and file organization

Organizing files for performance

Data compression, reclaiming space – record deletion and storage compaction, deleting fixed-lengthrecords for reclaiming space dynamically, deleting variable-length records, space fragmentation,replacement strategies.

Indexing

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 usingcombination of secondary keys, improving the secondary index structure – inverted lists

Indexed sequential file access and prefix B⁺ Trees

Indexed sequential access, maintaining a sequence set, adding a simple index to the sequence set, thecontent of the index: separators instead of keys, the simple prefix B⁺ tree, simple prefix B⁺ treemaintenance, index set block size, internal set block size, internal structure of index set blocks: a variableorder B-tree, loading a simple prefix B⁺ tree

Special Note: Implementation in C only

Hashing

Collisions in hashing, a simple hashing algorithms, hashing functions and record distributions, memory requirements, collision resolution by progressive overflow, buckets, deletions

Extendable hashing

Working of extendable hashing, implementation, deletion, extendable hashing performance

Designing file structure for CD-ROM

Tree structure on CD-ROM, hashing files on CD-ROM, CD-ROM file structure

Text Book:

File Structures – An Object Oriented Approach with C++ by Michael J. Folk, Bill Zoellickand Greg Riccardi,, Pearson