3

In "The Art of Unix Programming", on the topic of The Terminfo Database I read:

If you look in the terminfo directory, you'll see subdirectories named by single printable characters. Under each of these are the entries for each terminal type that has a name beginning with that letter. The goal of this organization was to avoid having to do a linear search of a very large directory; under more modern Unix file systems, which represent directories with B-trees or other structures optimized for fast lookup, the subdirectories won't be necessary.

I wonder if there are widespread (i.e. production ready) filesystems with this quality.

Improve this question

2 Answers 2

Reset to default
4

There are several, e.g. ext4, Microsoft's NTFS, Apple's HDF+, or the up and coming btrfs that use B-Trees. There are also HDF and Reiser4 which use B*-Trees, a more densely packed version of B-Tree.

Improve this answer
1
  • 3
    ext4 actually uses a modified version of B-tree called H-tree. This functionality is also available in ext3 through the dir_index option.
    – ire_and_curses
    Commented Sep 29, 2012 at 18:34
1

The ext3 file system also uses a hash (discussion in debian-user). However, IMHO, this can have a bad consequence, at least for a traditional hard disk: this destroys some possible regularity / locality on disk. For instance, when files have been created one after the other in the directory, reading these files in the directory order can be very slow (see some tests I've done). This is apparently why the Mutt mail user agent does a sort by inode when reading a maildir folder (commit f2eef427, old changeset 3828).

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .