Date: 01 Nov 1999 10:33:10 +0000 From: Randell Jesup <rjesup@wgate.com> To: freebsd-fs@FreeBSD.ORG Subject: Re: Features of a journaled file system Message-ID: <ybuiu3mh57d.fsf@jesup.eng.tvol.net.jesup.eng.tvol.net> In-Reply-To: Chang Song's message of "Sat, 30 Oct 1999 19:56:27 -0400" References: <Pine.BSF.4.05.9910301851350.44044-100000@calis.blacksun.org> <19991031014032.A3510@keltia.freenix.fr> <381B85AB.68EF4A45@zk3.dec.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Chang Song <song@zk3.dec.com> writes:
>> > Should the file system use b-trees? What other technologies should such a
>>
>> B-trees would help a lot in some cases. UFS performance has always been
>> abyssimal with large directories...
>
>I think B+ tree is too complex to maintain and implement.
>Extendible hashing (GFS uses it) is great compromise. Easier to implement
>yet competitive or sometime faster than B+ tree.
I'm a big fan of hashing for directories. Add something to (say)
cause the FS to add a hash level to a chain that grows too large (or to all
the chains of a directory that grows too large), and the benefit is almost
as large as a b+ tree for access/modify, and add/delete would be (much?)
faster (it's been a while since I looked at b+ trees for directories - OS2
uses them if I remember correctly). I slightly prefer adding hash table
levels according to chain length, but that might require some extra
bookkeeping (not a lot, just a counter per chain).
I've written FS's that kept duplicate directory lists: one hashed
(single level) for speed, and one sequential for speed at listing
directories. It has the nice side-effect of making the FS more easily
recoverable, at the cost of some disk space and slightly slower
create/delete. (The sequential blocks were heavily compressed, and the
hash tables only had the head file-header block (inode) of each chain.
(I'm not saying this design should be duplicated - it was a way to avoid
changing too much of an FS written in ASM, while speeding up dir listings;
just mentioning.)
--
Randell Jesup, Worldgate Communications, ex-Scala, ex-Amiga OS team ('88-94)
rjesup@wgate.com
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-fs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ybuiu3mh57d.fsf>