lkml.org 
[lkml]   [1996]   [Jul]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Newsgroups: linux.dev.kernel
Path: not-for-mail
From: Olaf Titz <olaf@bigred.inka.de>
Subject: Re: Is any file system on Linux appropriate for very large
directories?
Message-ID: <duurdl.awl@bigred.inka.de>
Date: 20 Jul 1996 19:32:06 +0200
References: <Pine.LNX.3.91.960715145524.2080C-100000@linux.cs.Helsinki.FI>
<Pine.LNX.3.93.960715082512.341C-100000@titan.usask.ca>
Organization: private Linux site, southern Germany
Lines: 37
Adam McKee <amm130@mail.usask.ca> wrote:
> Lookups should be more common than updates in most environments. So, the
> rule "make the common case fast" seems to be served by a hashed directory.
> The worst update situation would probably be the case where you need to
> grow the directory -- in that case, you would probably have to rewrite the
> whole directory (double its size, and then rehash all the entries into the
> new, larger table). However, this high price would only have to be paid
> occasionally. I don't see why the other update operations would
> necessarily be much more costly. In fact, many of them (i.e. delete)
> involve a lookup, so they should be expedited.

No. A file system has to be designed for the case where insert,
update, delete, lookup, scan and sorted scan operations all occur with
high frequency. The data structure that satisfies this best, along
with the need to pack several nodes together in one disk block, is the
B* tree, as implemented on the Macintosh HFS.

Unix and DOS filesystems use linear tables for only one reason:
simplicity. This was a concern with PDP-11s but I won't count that
nowadays (hint: divide LOC of the complete Linux kernel by LOC of the
ext2fs... :-)

> However, I understand the additional performance could be very minimal,
> given Linux's caching of directory entries. If most lookups are satisfied
> by that cache (?), then the extra performance provided by hashed
> directories might not justify the added complexity after all. I was
> unaware Linux had such a cache. Of course, I should have assumed it did

Again, that depends on the access pattern. E.g. the access pattern of
a news server defeats every cache no matter how big and clever.

olaf
--
___ Olaf.Titz@inka.de or @{stud,informatik}.uni-karlsruhe.de ____
__ o <URL:http://www.inka.de/~bigred/> <IRC:praetorius>
__/<_ >> Just as long as the wheels keep on turning round
_)>(_)______________ I will live for the groove 'til the sun goes down << ____

\
 
 \ /
  Last update: 2005-03-22 13:38    [from the cache]
©2003-2011 Jasper Spaans