Slide 1.8: Pros and cons of using file systems
Slide 1.10: AVL trees and B-trees
Home

A Short History of File Structure Design

Compared to computer memory, disks are slow. The tension between a disk's relatively slow access time and its enormous, nonvolatile capacity is the driving force behind file structure design. All file structure designs focus on minimizing disk accesses and maximizing the likelihood that the user will want is already in memory.

1950s (Magnetic Tapes)
IBM and 3M introduced tape in 1950s that stored 1.4 Mbytes of data. Today high-end tape holds 1 Tbytes of data. File access was sequential, and the cost of access grew in direct proportion to the size of the file.

1950s – Present (Hard Disks)
IBM introduced hard disks, which can store data anywhere from few Gbytes to more than few hundred Gbytes. To speed up the file access, indexes were added to files. Indexes are a list of keys, each of which identifies a unique record. Indexes make it faster to find specific records by using the sorted index field—the field used to identify each record.

1960s (Trees)
Unfortunately, simple indexes have some of the same sequential flavor as the data files as the indexes grew. Tree structures were then applied to indexes to solve this problem. For example, the figure shows one example of tree structures, a binary tree, which is a tree in which each node has at most two successors or child nodes. A binary search tree is 		 
a binary tree where every node's left subtree has values less than the node's value, and every right subtree has values greater.