On Sat, Mar 18, 2000 at 11:59:39AM -0500, andy huhn wrote:
> I thought linear was O(n)? What are some more modern file systems
linear is O(n).
But the programs are not reading the directories once, they open
every file once - n*(n/2).
> that speed this up, and how do they do it? Do they use a hash for
> the structure of the directory?
usually they use binary searching. HPFS from OS/2 was a well-known
example. Reiserfs for linux uses another tree structure (i don't
know exactly what method they use).
Note that reiserfs isn't generally considered to be of production
quality at this time.
Regards, Uwe (who'd like ext3 + binary searches)
