Date: Thu, 26 Sep 2002 19:30:11 +0100 From: David Malone <dwmalone@maths.tcd.ie> To: Terry Lambert <tlambert2@mindspring.com> Cc: freebsd-current@FreeBSD.ORG Subject: Re: Journaled filesystem in CURRENT Message-ID: <200209261930.aa30657@salmon.maths.tcd.ie> In-Reply-To: Your message of "Thu, 26 Sep 2002 11:16:35 PDT." <3D934F03.EB9A6616@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> > 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 majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi? <200209261930.aa30657>