Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 4 down vote accepted

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.

share|improve this answer
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 Sep 29 '12 at 18:34

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 (changeset 3828).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.