directory implementation

A directory, from the user's side, is just a folder full of named files. But underneath, a directory is really a little table that maps each name to the file's metadata — most often a list of (file name, inode number) pairs stored in a file of its own. Directory implementation is the question of how to store that table so that looking up a name is fast even when the folder holds thousands of entries.

The simplest scheme is a linear list: the directory is just a sequence of entries you scan from the top. Looking up holiday.jpg means comparing it against each entry until you find it — fine for a folder with ten files, painfully slow for one with fifty thousand, because every lookup is O(n) and creating a file must first scan the whole list to check the name is not already taken. A better scheme is a hash table: hash the name to an index and jump near-directly to the entry, giving roughly O(1) lookups, though it needs care to handle collisions and to resize as the directory grows. The scheme used by modern file systems for large directories is a balanced tree, typically a B-tree (or B+-tree) keyed on the name (often on a hash of the name): lookups, insertions, and deletions are all O(log n), and the tree stays shallow even with millions of entries, so a few block reads find any file. NTFS keeps directory entries in a B-tree; ext3 and ext4 added an htree (a hashed B-tree-like index) on top of the old linear list.

The trade-off is the familiar one: the linear list is trivially simple and great for small directories, while trees and hash indexes pay extra complexity (and on-disk space for the index) to keep lookups fast as directories grow huge. Whatever the structure, deleting a file usually just marks its directory entry free rather than physically compacting the list, so directories can carry empty slots until they are cleaned up.