[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

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


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

Reply to: