[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Using hash directories


On Fri, 23 May 2003 10:24:33 +0200 Emmanuel Lacour
<elacour@easter-eggs.com> wrote:

> I would like to understand why some softwares such as postfix or squid
> uses hash of directories like:
> a/a/
> b/a/
> d/a/darmond
> for their spools.

Quite a number of filesystems still do linear search when trying to
access a file. So accessing the mailbox for Zacharias Zulu (zzulu) among
20.000 users will give the OS probably 19.998 filenames too look up
before finding the correct one. Personal (negative) record due to this
effect was 3,5 seconds to access a file (of quite some thousands) an on
old MS-Dos/FAT harddisc - under 386ish hardware, so not THAT shabby...

Newer filesystems (ReiserFS, probably JFS and XFS too (not checked)) use
BTree or similar techniques to reduce lookups to the order of log(N)
instead of N.

So if using a classic filesystem creating such a directory tree will
mimick a number of hierarchies of a tree search thus saving quite some
file access time. But with new file systems they will come with a slight
access time penalty compared to a flat hierarchy.


Volker Tanger


Besuchen Sie unsere neuen Internet-Seiten http://www.detewe.de .
Neues Highlight: Wunschproduktberater fuer den Home & Office-Bereich.

Visit our new Internet Pages on http://www.detewe.de .
Our Highlight: Online Product Adviser for Home & Office.
(Currently available in German only)

Reply to: