[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: /usr/lib vs /usr/libexec



Thomas Bushnell BSG <tb@becket.net> writes:

> Humberto Massa <humberto.massa@almg.gov.br> writes:
>
>> with the possible exception of FAT and Minix. Q: are they used by a
>> default? A: Last time I installed Debian (15 days ago), it asked me if
>> I wanted my partition ext3, xfs, or reiserfs IIRC; I chose reiserfs,
>> and I am pretty sure finding a file in a directory in reiserfs is
>> O(log n) in the worse case. (Actually, I think that except for HUGE
>> directories [far larger than /usr/lib] it accesses two or three blocks
>> of disk in every case, hence being O(1)).
>
> How many directory entries do you think fit in a block?

Does that matter?

Make a big hash table containing all filenames and spaning many
blocks.

Make index blocks containing the size and the block numbers of that
hash table with primary, secondary and tertiary indirection.

With 2 indirections you can easily cover 1 MB of data filled with 512
byte structures of filename, inode number and any other flags you want
to keep in the hash directly. That is enough for >1000000 files
(alowing for wasted space for hash collisions). And you still only
need 3 reads to open a file.

Do you think you have more than 1000000 libs? Say a dir entry has 1K,
do you have more than 500000 libs? Even with 4K that gives 125000
entries.

MfG
        Goswin

PS: I don't know if reiserfs is doing it this way, just wanted to show
how it could be done.



Reply to: