CSci2111 Data and File Structures


Nathalie Japkowicz, Room 214, CS Building, x3157,

Meeting Times and Locations

Office Hours and Locations



Although secondary storage such as disks, magnetic tapes and CD-ROMs allow us to store thousands of megabytes, access to such storage is very slow as compared to other kinds of computer operations. A file structure is a combination of representations for data in files and of operations for accessing these data, and the study of file structure design is geared at improving the efficiency of data access. The topic of file structure design is closely linked to that of advanced data structures as a number of interesting data structures (including AVL Trees, B Trees, B+ Trees and Hash Tables) are useful for achieveing high efficiency in file operations. This course will provide a solid introduction to the topic of file structure design and will discuss, in detail, the data structures necessary for achieving its efficiency objectives.


Computer Science III (CSci2110) and Topics in Applied Computer Science (CSci2131). Knowledge of C++ or Java.


Students will be evaluated on:



In order to print a postscript file, first save the file onto your borg directory by pressing the ESC key and the right-mouse button simultaneously. Call it, say, Then you can print this file by typing "lw -Pprinter-name -ps" from borg (unless you own a postscript printer, you will not be able to print the file at home).

Late Policy

Late assignments will receive a 10% penalty per day (Saturdays and Sundays count as late days as well) unless a Doctor's note is provided.

Required Textbooks

File Structures, An Object-Oriented Approach with C++, by Michael J. Folk, Bill Zoellick and Greg Riccardi, Addison Wesley.

Preliminary Syllabus (the lecture slides can be retrieved by clicking on the links attached to each topic):





Chap. 1 & 2


Secondary Storage and System Software (Part I)

Chap. 3 (Begining of chapter to Section 3.5 (excluded))


Chap. 3 (Section 3.5 (included) to end of chapter)


Chap. 4, Chap. 5 & Chap. 6


Indexing Slide Viewer
Powerpoint File

Chap. 7


Cosequential Processing and the Sorting of Large Files Slide Viewer
Powerpoint File

Chap. 8


MidTerm Week (Review + Exam)

Chaps. 1, 2, 3, 4, 5, 6, 7 & 8


Multilevel Indexing and B Trees Slide Viewer
Powerpoint File

Chap. 9


Indexed Sequential File Access and Prefix B+ Trees Slide Viewer
Powerpoint File

Chap. 10


Hashing Slide Viewer
Powerpoint File

Chap. 11


Extendible Hashing

Chap. 12


Extendible Hashing; Final Review

Chap. 12; All Chapters

Note: We may not have enough time to cover all the topics discussed in the textbook. Announcements will be made in class regarding the section that we skipped.