Directory Structure:
In order to store many files, we need some organization in the way we store and reference them. Commonly, there are several levels of abstraction.
First is that disks are broken-up into partitions. Each partition is logically treated as a separate hard drive. A disk can have many partitions. There is usually at least one partition on every hard drive.
Each partition (being a logical hard drive) has a directory that maintains a list of files in the directory.
Operations Performed on Directory:
Just as with files, there are several basic operations on a directory:
- Search for a file: we need to be able to search the directory for a specific file.
- Create a file: We need to be able to create files and place the entry in the directory.
- Delete a file: We need to be able to delete a file and remove its entry from the directory.
- List a directory: We need to be able to get a list of files in the directory.
- Rename a file: We need to be able to rename files in the directory.
- Traverse the file system: We need some way (or ability) to traverse the directory. This is useful in backups, compression (zipping the entire directory), etc.
Single Level Directory:
In a single-level directory system, all the files are placed in one directory. This is very common on single-user OS.
A single-level directory has significant limitations when the number of files increases or when there is more than one user. Since all files are in the same directory, they must have unique names. If there are two users who call their data file "test", then the unique-name rule is violated. Although file names are generally selected to reflect the content of the file, they are often quite limited in length.
Even with a single-user, as the number of files increases, it becomes difficult to remember the names of all the files to create files with unique names.
Two-Level Directory:
The next level of complexity is a two level directory structure. It solves some of the naming issues and perhaps has higher capacity. It can separate multiple users but cannot allow them shared access to files. It is not extendible in a general sense. Two level directories are not much better but they provide a bit more abstraction. For example, we can have several users having their own set of single-level directories.
Tree-Structured Directory:
In the tree-structured directory, the directories themselves are files. This leads to the possibility of having sub-directories that can contain files and sub-subdirectories.
An interesting policy decision in a tree-structured directory structure is how to handle the deletion of a directory. If a directory is empty, its entry in its containing directory can simply be deleted. Suppose the directory to be deleted is not empty, but contains several files, or possibly sub-directories. Some systems will not delete a directory unless it is empty. The user must first delete all the files in a directory to delete that directory. If there are any subdirectories, this procedure must be applied recursively to them so that, they can be deleted also. This approach may result in a heavy amount of work.
An alternative approach is just to assume that, when a request is made to delete a directory, all of that directory's files and sub-directories are also to be deleted.
Acyclic-Graph Directories:
The acyclic directory structure is an extension of the tree-structured directory structure. In the tree-structured directory, files and directories starting from some fixed directory are owned by one particular user.
In the acyclic structure, this prohibition is taken out and thus a directory or file under directory can be owned by several users.
General Graph Directories:
Acyclic directories suffer from the fact that they cannot have any cycles. In acyclic directories we are intentionally restricting the structure not to have any cycles. This means that every time we create a link file, we need to check and ensure that no cycle has been created. This is not an easy task.
General Graph directories allow cycles in the graph. The algorithms that traverse graphs and acyclic graphs are quite different. For a graph with possible cycles in it, we need to maintain a list of nodes we have already visited in order not to visit them again.
