On Tue, Jul 03, 2001 at 12:45:09PM +0000, Jost Krieger wrote:
[snip]
> I thought it would be better to take a number about the square root of the
> top queue size, which minimizes search length on a classical file system.
>
> For 23000 your on the order of 151, which happens to look prime.
Search length is O((number of messages)/(conf-split)+(conf-split)).
Why?
If qmail wants to access message 12345, which is, for example, in
5/12345, the OS has to:
- linear search to find directory 5/
- inside this dir, linear search for 12345
Finding 5/ will take O(conf-split) steps. Finding 12345 within that
dir will take O((number of messages)/(conf-split)) steps.
This is all on classical filesystems. On filesystems like ReiserFS
that use search trees and other fancy stuff, it all basically comes
down to O(lg n), or even O(1) with hashing.
Greetz, Peter
--
Against Free Sex! http://www.dataloss.nl/Megahard_en.html
