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

--- Giorgos Keramidas <keramida_at_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