Directory Implementation Strategies
You'll learn: How file systems organize directory entries using linear lists and hash tables, and why the choice matters for performance.
The Problem
A directory maps file names to their corresponding file control blocks (FCBs) or inodes. When you open a file, the OS must search the directory to locate its metadata. How should we store these name-to-inode mappings for fast lookups?
Linear List Approach
The simplest strategy stores directory entries as an ordered or unordered list of (name, inode_number) pairs.
Pros:
- Simple to implement
- Easy to extend with new entries (just append)
- Works well for small directories
Cons:
- Linear search time: O(n) for lookups
- Slow for large directories (imagine a folder with 10,000 files)
- Deleting requires searching, then shifting or marking entries
Think of it like searching for a contact in an unsorted phone book—you might have to scan every page.
Hash Table Approach
A hash table computes an index from the file name, directly jumping to the entry's location.
Pros:
- Average O(1) lookup time
- Excellent for large directories
- Much faster for common operations (open, stat)
Cons:
- More complex implementation
- Requires handling collisions (chaining or probing)
- Fixed table size may need resizing
- Hash computation overhead for small directories
It's like having an index in the phone book—calculate the page number from the name instantly.
Practical Considerations
Many modern file systems use hybrid approaches: linear lists for small directories (avoiding hash overhead), switching to B-trees or hash tables when size exceeds a threshold.
Key Takeaway: Linear lists trade simplicity for speed; hash tables provide fast O(1) lookups but add complexity. The best choice depends on expected directory sizes and access patterns.