Thomas Bushnell BSG <[EMAIL PROTECTED]> writes: > Humberto Massa <[EMAIL PROTECTED]> 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. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]