Directory Implementation
11.3 Directory Implementation
- Directories need to be fast to search, insert, and delete, with a minimum of wasted disk space.
11.3.1 Linear List
- A linear list is the simplest and easiest directory structure to set up, but it does have some drawbacks.
- Finding a file ( or verifying one does not already exist upon creation ) requires a linear search.
- Deletions can be done by moving all entries, flagging an entry as deleted, or by moving the last entry into the newly vacant position.
- Sorting the list makes searches faster, at the expense of more complex insertions and deletions.
- A linked list makes insertions and deletions into a sorted list easier, with overhead for the links.
- More complex data structures, such as B-trees, could also be considered.
11.3.2 Hash Table
- A hash table can also be used to speed up searches.
- Hash tables are generally implemented in addition to a linear or other structure