The entries in a directory block are sorted by the binary lexical order of their name fields (this happens to put them in alphabetical order for the US. alphabet). The last entry in a directory block is a dummy record that marks the end of the block. When a directory gets too large to be stored in one block, it increases in size by the addition of 2Kb blocks that are organized as a B-Tree (see B-T tees and B+ Trees ). When searching for a specific name, the file system traverses a directory block until it either finds a match or finds a name that is lexically greater than the target. In the latter case, the file system extracts the Tree pointer from the entry. If there is no pointer, the search failed otherwise the file system follows the pointer to the next directory block in the tree and continues the search. A little back-of-the-envelope arithmetic yields some impressive statistics. Assuming 40 entries per block, a two-level tree of directory blocks can hold 1640 directory entries and a three-level tree can hold an astonishing 65,640 entries. In other words, a particular file can be found (or shown not to exist) in a typical directory of 65,640 files with a maximum of three disk hits--the actual number of disk accesses depending on cache contents and the location of the file's name in the directory blockB-Tree.That's quite a contrast to the FAT file system, where in the worst case more than 4000 sectors would have to be read to establish that a filewas or was not present in a directory containing the same number of files. The B-Tree directory structure has interesting implications beyond its effect on open and find operations. A file creation, renaming, or deletion may result in a cascade of complex operations, as directory blocks are added or freed or names are moved from one block to the other to keep the tree balanced. In fact, a rename operation could theoretically fail for lack of disk space even though the file itself is not growing. In order to avoid this sort of disaster, the HPFS maintains a small pool of free blocks that can be drawn from in a directory emergency; a pointer to this pool of free blocks is stored in the Spare Block.
FIGURE 5: Here directories are anchored on an Fnode and are built up from 2Kb directory blocks. The number of entries in a directory block varies because the length of the entries depends on the filename. When a directory requires more than one block the blocks are organized as a B-Tree. This allows a filename to be located very quickly with a small number of disk accesses even when the directory grows very large.