Re: you are in an fs with millions of small files

On 2005-06-08 00:52, Colin Percival <cperciva_at_freebsd.org> wrote:
> Giorgos Keramidas wrote:
> > On 2005-06-08 09:25, Dag-Erling Sm?rgrav <des_at_des.no> wrote:
> >>That's because fts's sorting code is brain-dead.  It starts by reading
> >>the entire directory into a linked list, then copies that list into an
> >>array which it passes to qsort(), and finally converts the array back
> >>into a linked list.
> >
> > Is there a better way to sort a linked list
>
> How do you define "better"?  You can merge-sort a singly-linked list
> quite easily, but converting it to an array and back would probably
> be faster.

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 :-)