Directory Organization

01 Introduction

Lesson 10.1 introduced the directory as a mapping from names to files: an entry in a directory associates a human-readable name with an inode number, and the inode number identifies the file within the file system. Lesson 10.2 examined the metadata that the inode holds, and Lesson 10.3 presented the inode itself — its layout, its lifetime, and its role in path resolution. This lesson turns to the directory's internal structure: how the entries are stored, how a name is looked up, how the structure is updated, and how it scales.

The directory is easy to overlook. From the user's perspective, a directory is just a folder: a container for files, with operations like create, delete, rename, and list. From the file system's perspective, it is a data structure with a defined layout on disk, a lookup algorithm that runs on every path resolution, and a performance profile that matters more and more as directories grow. A directory with a handful of entries can be searched linearly with negligible cost; a directory with a million entries cannot. The choice of structure is therefore a scalability decision, and it is one of the file system's most visible performance characteristics.

The classical Unix directory is a simple file whose contents are a sequence of entries: each entry is a name and an inode number, and a lookup is a linear scan of the file. The structure is simple to implement and works well for small directories, but it degrades to O(n) for a directory with n entries. For a system with millions of small files — a mail spool, a build cache, a Git object store — the linear scan is the bottleneck. Modern file systems address this with indexed structures: ext4 uses the HTree (a B-tree-shaped hash table), XFS and Btrfs use B-trees, and the classical BSD file system uses a variant of the linear list with a cache. Each of these structures has its own trade-offs, and each is designed for a specific range of workloads.

This lesson presents the directory as a data structure. It defines the directory entry and the operations the file system performs on it. It presents the classical linear-list directory, its implementation, and its limitations. It presents the linked-list and hash-table alternatives, and it presents the indexed structures — HTree and B-tree — that modern file systems use to scale. It examines the directory entry cache (dcache) and explains how caching turns a slow lookup into a fast one. It closes with a discussion of the directory's performance characteristics and of the design choices that shape them.

02 Learning objectives

This lesson contributes to U10.4 and U10.5, and to course learning outcomes CLO1, CLO5, and CLO6.

03 Required reading

• Operating System Concepts — Chapter 14, Section 14.3, Directory Implementation. The standard treatment of the linear-list and hash-table directory structures.
• OSTEP — Chapter 40, File System Implementation, and Chapter 41, Locality and The Fast File System. OSTEP's treatment of the directory as a file of entries, and of the Fast File System's directory organization, is the clearest available account, and it is the basis for the worked example in this lesson.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 4, Section 4.3.3, Directory Implementation. A complementary treatment that develops the linear list and the hashed directory from first principles.
• McKusick, M. K., Joy, W. N., Leffler, S. J., & Fabry, R. S. — A Fast File System for UNIX. ACM Transactions on Computer Systems, 1984. Section 4 discusses the directory implementation and the performance considerations.
• Bach, M. J. — The Design of the UNIX Operating System. Prentice Hall, 1986. Chapter 5, Section 5.3. The classical System V directory entry format and the directory operations.
• Kerrisk, M. — The Linux Programming Interface, Chapter 14, File Systems. The directory-related interfaces: opendir, readdir, seekdir, telldir, and the getdents system call.
• Love, R. — Linux Kernel Development, 3rd ed., Chapter 13, The Virtual File System. The VFS directory operations and the dentry cache.
• Linux man pages: man 3 opendir, man 3 readdir, man 3 seekdir, man 3 telldir, man 2 getdents, man 2 mkdir, man 2 rmdir, man 2 link, man 2 unlink, man 2 rename, man 5 proc (for the /proc/<pid>/fd interface), man 8 tune2fs (for the dir_index feature), man 1 debugfs.

04 Core content

4.1 The directory entry

A directory entry is a record in a directory that associates a name with an inode number. The simplest possible entry has two fields:

• The name. A human-readable string, typically a sequence of bytes up to 255 bytes long (the classical Unix limit). The name is what the user types and what the file system looks up.
• The inode number. An integer that identifies the file within the file system's inode table (Lesson 10.3). The inode number is what the file system uses internally to refer to the file, and it is the link between the directory and the file's metadata.

Real directory entries also have fields that support the directory's data structure: a record length (or record size) that allows the entry to be padded to a specific length; a file type (a small code indicating whether the entry refers to a regular file, a directory, a symbolic link, and so on); and, on some file systems, additional metadata for the entry itself. The exact format varies between file systems, and it is one of the aspects of the file system that is not standardised across Unix-like systems.

The directory's entries are stored in the directory's data blocks, which are located through the directory's own inode — a directory is a file, and the file system uses the same mechanisms (the inode's multi-level pointer scheme, or extents) to locate the directory's contents as for any other file. When a program calls readdir, the kernel reads the directory's data through its inode and returns the entries one at a time.

4.2 Directory operations

The file system performs four operations on a directory, each of which interacts with the directory's internal structure.

Lookup

Given a name, find the corresponding entry and return its inode number. This is the most common operation: every path resolution, every open, every stat, and every link begins with a lookup. The performance of the lookup dominates the performance of the directory.

Insert

Add a new entry with a given name and inode number. Used when a file is created (creat, open with O_CREAT) or when a hard link is added (link). The operation must find space in the directory's data, or extend the data if necessary, and must preserve the directory's structure.

Delete

Remove the entry with a given name. Used when a file is unlinked (unlink) or when a directory is removed (rmdir). The operation must find the entry, mark it as free (typically by adjusting the previous entry's record length), and possibly update the directory's structure.

Rename

Change the name of an entry, or move it to a different directory. Used by rename. The operation must remove the entry from its old location and insert it in the new one, and must do so atomically (a concurrent lookup sees either the old state or the new, never an intermediate state).

The four operations have different performance characteristics depending on the directory's structure. In a linear list, a lookup is O(n), an insert is O(n) (to find the end of the list), a delete is O(n) (to find the entry), and a rename is O(n) plus the cost of the insert. In an indexed structure, the same operations are O(log n) or O(1), which is why indexed structures are used for large directories.

4.3 The classical linear-list directory

The linear-list directory is the simplest possible structure: the directory's data is a sequence of entries, and a lookup is a linear scan through the sequence, comparing the name of each entry with the name being searched for. The entry is found when the names match, or the lookup fails when the end of the sequence is reached without a match.

The classical implementation of the linear list is the linked-list directory, in which each entry contains the length of the entry and a pointer (or offset) to the next entry. The chain of pointers makes it easy to insert and delete entries: an insert can add the new entry at the front of the list (or in the first free slot), and a delete can adjust the previous entry's length to absorb the deleted entry's space. The linked-list structure is the one used by the classical Unix file system (System V, ext2) and by the BSD Fast File System, and it remains the basis of the modern ext2/ext3/ext4 directory.

The linear list's performance is straightforward:

• Lookup: O(n) in the worst case, O(n/2) on average. Every entry must be examined until the target is found.
• Insert: O(n) to find the end of the list, unless a free slot is maintained at the front (in which case it is O(1)).
• Delete: O(n) to find the entry, O(1) to absorb its space into the previous entry.

For a small directory — say, up to a few hundred entries — the linear scan is fast enough that the constant factor dominates: a scan of 100 entries is a few hundred nanoseconds on modern hardware, which is negligible compared to the cost of the other operations (the inode read, the data read, and the disk access). But for a large directory — say, 100,000 entries — the scan is expensive: 100,000 comparisons, each requiring a memory load and a comparison, plus the disk accesses if the directory's data spans multiple blocks. The linear list is therefore adequate for small directories but does not scale.

4.4 The ext2/ext3/ext4 directory entry format

The classical Unix file system's directory entry is a simple structure whose fields are worth examining, because the design illustrates the trade-offs of the linear-list approach.

struct ext2_dir_entry_2 {
    __le32  inode;        /* inode number (0 means "free") */
    __le16  rec_len;      /* length of this record, in bytes */
    __u8    name_len;     /* length of the name, in bytes */
    __u8    file_type;    /* file type code (regular, dir, ...) */
    char    name[];       /* the name, not null-terminated */
};

The structure has four fields plus the name:

• inode — the inode number that the entry refers to. An inode number of 0 marks the entry as free.
• rec_len — the length of the record, in bytes. The record is padded to a multiple of the alignment (typically 4 bytes), so the rec_len may be larger than the name's length would require. The padding leaves space that a later insert can use without extending the directory.
• name_len — the length of the name. The name is not null-terminated: its length is given by name_len.
• file_type — a small code indicating the file's type: EXT2_FT_REG_FILE for a regular file, EXT2_FT_DIR for a directory, EXT2_FT_SYMLINK for a symbolic link, and so on. The file type is redundant with the type stored in the inode, but it allows the file system to return the type without reading the inode, which is a performance optimisation for readdir.

The record's length is variable, and the variable length is the key to the structure's simplicity. When a new entry is inserted, the file system finds the first record with enough free space (either at the end of the directory, or in a padded region of an existing record), splits the space, and adds the new entry. When an entry is deleted, the file system sets its inode field to 0 and merges its space into the previous entry by increasing that entry's rec_len. The merge is what keeps the directory's free space available for future inserts, and it is why a directory's size grows but rarely shrinks: the space freed by deletes is absorbed into neighbouring records, and the directory's data blocks are not returned to the file system until the directory is compressed (which most file systems do not do).

A lookup in the ext2/ext3/ext4 directory is a linear scan of the records. The scan is fast because the records are small and the file system reads them sequentially, but the cost is still O(n). For a directory with a few hundred entries, the cost is negligible; for a directory with tens of thousands of entries, the cost becomes significant, and for a directory with millions of entries (as in a mail spool or a Git object store), the linear scan is a serious bottleneck.

4.5 The HTree indexed directory

The linear-list directory's O(n) lookup became a practical problem in the 2000s, as file systems grew and workloads with many small files became common. Ext3 (and later ext4) addressed the problem by adding an indexed directory structure, called the HTree, that keeps the classical entry format but organizes the entries into a tree of blocks.

The HTree is a B-tree-shaped hash table. Each directory has a hash of its entries' names, and the entries are grouped into logical blocks (each of which is typically one file-system block, i.e., 4 KB). The tree has a root node that spans the hash values, and internal nodes that split the hash range into sub-ranges. A lookup hashes the name, traverses the tree to find the leaf block whose hash range contains the name's hash, and scans the entries in that block — a small number, because each block holds only the entries whose hashes fall in its range.

The HTree's structure is a compromise between the classical entry format and a full hash table. The directory's data blocks are still sequences of ext2-style entries, so a program that reads the directory with readdir sees the same format as before. But the entries are not stored in insertion order: they are stored in hash order, with the entries for each hash range in its own block. The directory's inode points to the tree's root, and the tree's internal nodes point to the leaf blocks.

The HTree has three important properties:

• Lookup is O(log n) — typically two or three block reads, regardless of the directory's size. A directory with 10 million entries has a tree with three levels, so a lookup reads the root, one internal node, and one leaf — three disk accesses instead of 10 million.
• Insert and delete are O(log n) — the file system finds the leaf block whose hash range contains the new name's hash and inserts the entry there, splitting the block if it is full.
• The directory's size grows but does not shrink — like the classical ext2 directory, the HTree does not return freed blocks to the file system. The directory can be rebuilt (with e2fsck -D) to reclaim space.

The HTree is enabled by default on ext3 and ext4 file systems that are created with the dir_index feature, which is the default on modern systems. It is what allows ext4 to handle directories with millions of entries without the performance collapse that a linear list would suffer.

4.6 B-tree and B+tree directories

Other modern file systems use B-trees or B+trees as their directory structure. XFS uses a B+tree indexed by name (not by hash), and Btrfs uses a B-tree that is shared with the rest of the file system's metadata.

A B-tree is a balanced tree in which each node holds a sorted sequence of keys and pointers, and the tree's leaves hold the actual entries. The structure is self-balancing: when a node becomes full, it is split, and the tree's height grows logarithmically with the number of entries. A lookup traverses from the root to a leaf in O(log n) steps, comparing the target name with the keys at each node.

The B-tree's advantage over the HTree is that the entries are stored in name order, not in hash order. This allows efficient range queries: a program can ask for all entries whose names fall in a range (for example, all files whose names begin with "config-"), and the file system can find the range's start and iterate through the leaves. The HTree does not support range queries efficiently, because the entries are stored in hash order, which does not correspond to name order. Linux exposes the range-query interface through the getdents system call with the d_type field and through the readdir family, but the underlying file system determines whether the query is efficient.

The B-tree's cost is that the names are compared in order, so each comparison is a string comparison rather than a hash comparison. The string comparison is more expensive than the hash comparison, but the difference is small for typical names, and the benefit of the range query is significant for the workloads that use it. XFS's directory B+tree is the classical example, and Btrfs's directory B-tree is the modern one.

4.7 Directory entry caching (the dcache)

Whatever the on-disk directory structure, the kernel maintains an in-memory cache of recently resolved directory entries. This cache is called the directory entry cache (the dcache), and it is the reason that most file operations are fast: once a path has been resolved, the resolution of the same path (or a path that shares a prefix) is served from memory, without any disk access.

The dcache is not a cache of names to inode numbers. It is a cache of directory entries: for each entry, the kernel stores the parent directory, the name, and the inode. The entries are organized in a hash table keyed by the parent-inode-and-name pair, and they are also linked into a tree that mirrors the directory hierarchy. The tree structure allows the kernel to walk a path from a cached component to the next, using the cached entries when possible and reading from disk only when a component is not cached.

The dcache's behaviour is similar to the other caches in the system (Lesson 9.3's TLB, Lesson 9.4's page cache). On a system with good locality — where programs repeatedly access the same directories and files — the cache hit rate is very high, and the cost of path resolution is dominated by the memory access rather than the disk access. On a system with poor locality — where programs traverse many directories and open many files — the cache hit rate is lower, and the cost of path resolution is dominated by the on-disk directory lookups.

The dcache's size is bounded by a tunable limit, and when the limit is reached, the kernel evicts the least recently used entries. An entry is in use if it is part of an open file's path (so the kernel cannot evict it), or if it is referenced by another cached entry; the kernel evicts only entries whose reference count is zero. On a modern system with gigabytes of memory, the dcache can hold hundreds of thousands of entries, and the eviction is rare.

4.8 Scaling and the cost of directory operations

The choice of directory structure has a direct effect on the performance of the operations that use it. The following table summarizes the costs of the classical and modern structures for a directory with n entries:

The table makes the trade-offs clear. The linear list is the simplest structure and is adequate for small directories, but it does not scale. The hash table gives O(1) lookups on average but does not support range queries. The HTree gives O(log n) lookups and inserts and is the standard for ext4, but it stores entries in hash order, so range queries are expensive. The B-tree gives O(log n) for all operations and supports range queries efficiently, which is why XFS and Btrfs use it.

In practice, the choice between the structures is made by the file system designer, and the user cannot change it. The user's lever is the directory's size: keeping directories reasonably small (a few thousand entries) keeps the cost of operations low regardless of the structure, and spreading a large set of files across many directories is the standard technique for managing a large collection. The classic example is Git's object store, which distributes its objects across 256 subdirectories (one per two-hex-digit prefix of the object's SHA-1 hash) precisely to avoid the scaling problems of a single large directory.

4.9 Directory operations in practice

The four operations — lookup, insert, delete, and rename — have specific implementations in the file system, and it is worth examining how they work on the linear-list structure and on the indexed structures.

On a linear list, the operations are direct:

• Lookup scans the entries, comparing names.
• Insert finds the first entry with enough free space (a deleted entry whose space has not been merged, or the end of the directory), splits the space, and writes the new entry.
• Delete sets the entry's inode field to 0 and merges the entry's space into the previous entry's record length. If the deleted entry is the first in the directory, the file system must handle the case specially (the entry remains as a free record, because there is no previous entry to merge into).
• Rename is a delete followed by an insert, but with the additional requirement that the operation be atomic. If the target directory is the same as the source directory, the rename can be done in place; if the directories differ, the entry is removed from the source and added to the target, and the two operations must be atomic with respect to concurrent lookups.

On an indexed structure, the operations are similar but use the index to find the right block first:

• Lookup hashes the name (for HTree) or compares it (for B-tree), traverses the tree to the appropriate leaf, and scans the entries in the leaf.
• Insert finds the leaf, inserts the entry, and if the leaf is full, splits it and updates the tree. The split may cascade up the tree, which is what makes the insert O(log n) in the worst case.
• Delete finds the entry, marks it free, and merges the space into the previous entry. If the leaf becomes sparse, the file system may merge it with a sibling, which also cascades up the tree.
• Rename is the same as on the linear list, but the file system must also update the tree's keys if the renamed entry's hash or name changes its position.

The operations must be crash-consistent: if the system crashes during an insert or a delete, the directory must be left in a valid state (either the old state or the new one, never an intermediate). This is the subject of journaling (Lesson 10.6), and it is one of the reasons directory operations are more complex than they first appear.

4.10 Common misconceptions

05 Worked example

The following example traces a directory's linear-list structure through a sequence of inserts and deletes, computes the cost of a lookup for different directory sizes, and demonstrates the scaling of the HTree.

# Check the directory's size
du -sh /var/spool/mail

# Rebuild the directories (requires unmounting the file system
# or running on a non-mounted device)
sudo umount /dev/sda1
sudo e2fsck -fD /dev/sda1
sudo mount /dev/sda1 /mnt

# Or, on a mounted file system, use tune2fs to enable
# the dir_index feature and e2fsck to rebuild the directories
sudo tune2fs -O dir_index /dev/sda1
sudo e2fsck -fD /dev/sda1

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• A directory entry is a record that associates a name with an inode number. The entry may also contain a record length, a file type, and other metadata. The file system performs four operations on a directory: lookup, insert, delete, and rename.
• The classical linear-list directory stores entries in a sequence in the directory's data blocks. A lookup scans the sequence, so the cost is O(n). The structure is simple and adequate for small directories, but it does not scale.
• The ext2/ext3/ext4 directory entry format is a variable-length record with an inode number, a record length, a name length, a file type, and the name. The record length allows the file system to insert and delete entries efficiently by splitting and merging records, but the directory's size grows but does not shrink.
• The HTree is ext4's indexed directory structure. It is a B-tree-shaped hash table that stores entries in hash order and reduces the lookup cost to O(log n) — typically two or three block reads. Its limitation is that it cannot support efficient range queries, because the entries are not stored in name order.
• A B-tree or B+tree directory stores entries in name order, which allows both O(log n) lookups and efficient range queries. XFS and Btrfs use B-trees for their directories, and the structure is the most general of the options.
• The directory entry cache (dcache) is the kernel's in-memory cache of recently resolved entries. It is keyed by the parent-inode-and-name pair and holds entries in a hash table and a tree. On a system with good locality, the dcache hit rate is very high, and the cost of path resolution is dominated by memory access rather than disk access.
• Negative caching is the dcache's caching of failed lookups. It matters for programs that search for files by trying many names (a shell's $PATH search, a dynamic linker's library search), because without it, each failed lookup would require a disk access.
• The choice of directory structure determines the file system's performance on directory-heavy workloads. The linear list is adequate for small directories; the hash table is fast for lookups but cannot support range queries; the HTree scales to millions of entries but stores entries in hash order; the B-tree scales and supports range queries. The choice is made by the file system designer, and the user cannot change it.
• Directory compression is necessary on file systems whose directories grow but do not shrink. The e2fsck -D command rebuilds ext2/ext3/ext4 directories, reclaiming the wasted space and (optionally) building the HTree index.
• The directory is becoming a database: the B-trees and HTrees used by modern file systems have the same structure as the indexes used by database systems, and the file system's metadata operations are increasingly transaction-like. The classical name-to-inode mapping remains the interface, but the implementation has grown significantly more sophisticated.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 14, Section 14.3.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 40 and 41. Available online at ostep.org.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 4, Section 4.3.3.
• McKusick, M. K., Joy, W. N., Leffler, S. J., & Fabry, R. S. A Fast File System for UNIX. ACM Transactions on Computer Systems, 1984.
• Bach, M. J. The Design of the UNIX Operating System. Prentice Hall, 1986. Chapter 5.
• Kerrisk, M. The Linux Programming Interface. No Starch Press, 2010. Chapter 14.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 13, The Virtual File System. The VFS directory operations and the dentry cache.
• Bovet, D. P., & Cesati, M. Understanding the Linux Kernel, 3rd ed. O'Reilly, 2005. Chapter 12.
• Mathur, A., Cao, M., Bhattacharya, S., Dilger, A., Tomas, A., & Vivier, L. The New Ext3 Directory Index. Ottawa Linux Symposium, 2007. The paper that describes the HTree directory.
• Linux man-pages: man 3 opendir, man 3 readdir, man 3 seekdir, man 3 telldir, man 2 getdents, man 2 mkdir, man 2 rmdir, man 2 link, man 2 unlink, man 2 rename, man 5 proc, man 8 tune2fs, man 1 debugfs, man 8 e2fsck.