Re: /usr/lib vs /usr/libexec
Thomas Bushnell BSG <tb@becket.net> writes:
> Goswin von Brederlow <brederlo@informatik.uni-tuebingen.de> writes:
>
>> 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?
>
> Not if it's hashed. (But then why is it O(log n) in the worst case?
> That sounds like a search tree strategy, not a hash.)
If the hash is split up over multiple data blocks then you end up with
a tree or list structure on top of it. The tree is O(log n), the later
O(n). The base of the logarithm would be fairly big (the tree very
wide) but that is just a constant and disapears in O().
>> PS: I don't know if reiserfs is doing it this way, just wanted to show
>> how it could be done.
>
> Right. I have no doubt it can be done. It's been done for decades in
> non-Unixoid systems. I'm asking about Debian, here and now, under
> default installation options, not under "what can be done" in the
> abstract.
It's doing something better than a plain list.
MfG
Goswin
Reply to: