Date: Wed, 8 Jun 2005 01:13:26 -0700 (PDT) From: Arne "Wörner" <arne_woerner@yahoo.com> To: Giorgos Keramidas <keramida@freebsd.org>, Colin Percival <cperciva@freebsd.org> Cc: freebsd-fs@freebsd.org, Randy Bush <randy@psg.com>, FreeBSD Current <freebsd-current@freebsd.org>, Robert Watson <rwatson@freebsd.org>, Julian Elischer <julian@elischer.org>, Eric Anderson <anderson@centtech.com> Subject: Re: you are in an fs with millions of small files Message-ID: <20050608081326.3455.qmail@web41206.mail.yahoo.com> In-Reply-To: <20050608080234.GA1226@orion.daedalusnetworks.priv>
next in thread | previous in thread | raw e-mail | index | archive | help
--- Giorgos Keramidas <keramida@freebsd.org> wrote: > Better, in this case, would be any of: > > a. faster > b. faster and less demanding in memory > > The red-black tree des mentioned is certainly faster to > traverse, but not necessarily less demanding in memory. > The memory load when a red-black tree is used will be > amortized to a range of "add FTSENT" operations, so > it seems nice :-) > I just remembered or found this algorithm and data structure: 1. a dynamic array of char* L (resized by realloc or so) 2. a dynamic array of char D (resized by realloc or so) 3. the number of char* entries in L C 4. the first unused entry of D L's entries would point into the data in D D contains the data that should be sorted If ls(1) wants to insert a new directory entry, it adds the data to the tail of D, and it adds the pointer to the former tail of D at the right position in L. But I do not know if the shift operations in L are not so good... But the memory usage looks quite good to me... I say, the sort of the directory entries should have a time complexity of O(N*log(N))? Do you think, I should try to implement it? -Arne __________________________________ Discover Yahoo! Get on-the-go sports scores, stock quotes, news and more. Check it out! http://discover.yahoo.com/mobile.html
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050608081326.3455.qmail>