File Structures

File Structures

Course Overview:

The Course will cover the following materials: File concepts, basic file operations, physical file organization and compression techniques, sequential file structures, hashing and direct organization structures, indexed structures, list file structures (inverted, multi-key, ect.), tree structures (B trees, B+ trees,... etc.), external sorting techniques, searching techniques.

Course Objectives:

· Provide a solid introduction to the topic of file structure design.

· Discuss, in detail, the data structures necessary for achieving its efficiency objectives.

· Introducing techniques for organization and manipulation of data in secondary storage including the low level aspects of file manipulation which include basic file operations, secondary storage devices and system software.

· Introducing the most important high-level file structures tools which include indexing, co-sequential processing, B trees, Hashing.

· Applying the techniques in the design of C++ programs for solving various file management problems.

Learning Outcomes:

After completing this course, the student should demonstrate the knowledge and ability to:
· Explain the importance of file structures in the Data Storage and Manipulation.
· Show how various kind of secondary storage devices to store data.
· Show how the File Structure approach differs from the data base approach.
· Know the low level aspects of file manipulation.
· Know the importance of data compression.
· Know some of the high-level file structures tools and recognize the difference between various indexing techniques.
· Implement some of the learned techniques and concepts using C++ for solving various file management problems.

Teaching Methods:

The course will be based on the following teaching and learning activities:
· Lectures covering the theoretical part using both Power Point presentations and White board.
· Visit some websites that provide animation for some of the techniques presented in the course.
· Review questions and class discussion.
· Programming assignments.
· Using the Internet to find the recent information related to the course.

Teaching Resources:

Main Text Book

File Structures, an Object Oriented Approach with C++, M.J.Folk, B. Zoellick and G.Riccardi, Addison-Wesley, 1998.

Supplementary Books:

· Deitel and Deitel, C++ How to Program, 5th edition. Prentice Hall. 2006.

---

Course Plan: Get the PDF version of the Course Syllabus

Week 1 : Introduction Get Slide in PDF

· Course Description Get Slide in PDF

· Review some concepts from the Data structure Course

· Introducing the File Structure

· The Heart and aim of File Structure Design

· A short history of File Structure Design

Week 2: Fundamental File Processing Operations (1) Get Slide in PDF

· Physical Files and Logical Files

· Introducing types of files

· Text File Operations and Functions in C++

· Manipulating Text Files

· Writing Sample Programs to solve various problems

Week 3 : Fundamental File Processing Operations (2)

· Binary File Operations and Functions in C++

· Manipulating Binary Files in C++ (File of Records)

· Writing Sample Programs to solve various problems

· Seeking in C++

Week 4: Secondary Storage Get Slide in PDF

· Introducing the various kinds of storages media

· Types Disks

· Organization of Disks

· Disk Access

· Some Calculations related to Disk Capacity

· Some Calculations related to Disk Access

Week 5: System Software

· A journey of a Byte

· Disk Bottleneck

· Buffers and Buffer Management

First Exam

Week 6: Fundamental File Structure Concepts Get Slide in PDF

· Field and Record Organization

· Record Access (Sequential and Direct)

· Header Records and Metadata

· Portability and Standardization

Week 7: Organizing Files for Performance Get Slide in PDF

· Introducing the Data Compression concept

· The RLE technique

· Huffman compression technique Visit this Site for an Animated version of the Huffman Code algorithm: Huffman

Week 8 : Reclaiming Space in Files

· Main file operations

· Deleting records from file

· Deleting record from fixed length record files dynamically

· Deleting record from Variable length record files dynamically

Week 9: Finding Things Quickly

· Internal Sorting and Binary Searching

· Keysorting

Week 10: Indexing Get Slide in PDF

· What is an Index

· Simple Index for Entry-Sequenced Files

· Large Index Files

· Inverted Lists and Selective Indexes

· Advantages and Disadvantages of Indexing

Week 11: Consequential Processing and the Sorting of Large Files Get Slide in PDF

· Matching and Merging Sorted Files

· Merging as a way of sorting large files on Disk

Week 12: Indexing using Tree Structured File Organizations

· Statement of the problem

· Indexing with Binary Search Trees

· Indexing with Paged Binary Search Trees

Second Exam

Week 13 and 14: Multilevel Indexing Get Slide in PDF

· Introducing the B-tree Index: Statement of the problem

· Manipulating B-Trees (Creating, Searching, and Inserting )

· Deleting a key from a B-Tree

· Introducing the B+ tree file structure

· Manipulating B+Trees (Creating, Searching, and Inserting )

Week 15: Hashing Get Slide in PDF

· Introduction to Hashing

· Collisions

· A Simple Hashing Algorithm

· Hashing Functions

· Collision Resolution Techniques