> > On Thu, Sep 26, 2002 at 10:36:27AM -0700, Terry Lambert wrote:
> > > I think that what you were probably testing was directory entry
> > > layout and O(N) (linear) vs. O(log2(N)+1) search times for both
> > > non-existant entries on creates, and for any entry on lookup
> > > ( / 2 on lookup) .
> >
> > Though dirhash should eliminate most of this...
> Everybody alsways says that, and then backs off, when they realize
> that a traversal of a mail queue of 100,000 entries, in which the
> destination is known by the contents of the file, rather than the
> file name, is involved. 8-).
If you are searching based on contents of a file, then any directory
layout scheme will require mean N/2 probes on success and N on
failure surely? And if these probes are linear (ie. in the order
they are in the directory) then this really is O(N) both with and
without dirhash 'cos the probles will be O(1).
David.
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
