為什么單目錄下子文件過(guò)多會(huì)影響性能?

瑪莉隔壁

為什么單目錄下子文件過(guò)多會(huì)影響性能?如1個(gè)目錄下有10000個(gè)子文件，那么讀取某個(gè)文件的速度將會(huì)明顯慢下來(lái)？這和文件索引有關(guān)嗎？索引中如何組織這些節(jié)點(diǎn)？謝謝大家?guī)兔?/td>

fhzxt

大致說(shuō)一下，硬盤(pán)的基本單位是塊，塊有獨(dú)立地址，文件的地址（類(lèi)似于指針）由一個(gè)索引塊組織，因?yàn)橐粋�(gè)塊的大小是有限的，所以只能存儲(chǔ)一定數(shù)量的文件地址，當(dāng)一個(gè)目錄的文件數(shù)超過(guò)這個(gè)數(shù)量時(shí)，就需要將索引塊也索引起來(lái)，就是索引的索引，即為2重索引，如果還不夠就要3級(jí)索引，這自然會(huì)影響速度。一些名詞可能用錯(cuò)，大致意思就是這樣。
ps：據(jù)說(shuō)現(xiàn)在有些文件系統(tǒng)（比如殺人犯的那個(gè)）使用btree作為索引結(jié)構(gòu)，可以提高小文件的查找速度

瑪莉隔壁

b+tree的結(jié)構(gòu)應(yīng)該不用考慮單個(gè)目錄文件過(guò)多問(wèn)題吧？

fhzxt

按Btree的結(jié)構(gòu)就查找看影響很小，如果排序合理的話，可以減少數(shù)量級(jí)的查找量。
具體還是做個(gè)實(shí)驗(yàn)比較好，畢竟我們并不知道現(xiàn)在bsd的ufs的確切查找和管理方式。

[ 本帖最后由 fhzxt 于 2009-2-25 21:33 編輯 ]

prolj

原帖由 fhzxt 于 2009-2-25 21:09 發(fā)表
大致說(shuō)一下，硬盤(pán)的基本單位是塊，塊有獨(dú)立地址，文件的地址（類(lèi)似于指針）由一個(gè)索引塊組織，因?yàn)橐粋�(gè)塊的大小是有限的，所以只能存儲(chǔ)一定數(shù)量的文件地址，當(dāng)一個(gè)目錄的文件數(shù)超過(guò)這個(gè)數(shù)量時(shí)，就需要將索引塊也 ...

Reiser 的特點(diǎn)不是 B Tree，而是實(shí)現(xiàn)了其變種的 B* Tree ，小文件性能好是不給小文件分配 inode （直接存在 Tree 里面？記不清楚了）

fhzxt

無(wú)聊得很，就隨便編了一個(gè)能自動(dòng)創(chuàng)建文件的程序，參數(shù)是：a.out 首起文件名 數(shù)量
發(fā)現(xiàn)單一目錄下文件再多（數(shù)10w）也不影響查找，不過(guò)似乎對(duì)創(chuàng)建和刪除有嚴(yán)重的影響，類(lèi)似于溢出，看記錄：
[zhpalt@freebsd]~> time ./a.out /tmp/a/test 30000
0.074u 1.022s 0:05.66 19.2%     5+178k 0+765io 0pf+0w
[zhpalt@freebsd]~> time ./a.out /tmp/a/test2 30000
0.014u 1.263s 0:05.06 25.0%     5+182k 0+871io 0pf+0w
[zhpalt@freebsd]~> time ./a.out /tmp/a/test3 30000
0.060u 1.277s 0:05.57 23.8%     5+176k 0+879io 0pf+0w
[zhpalt@freebsd]~> time ./a.out /tmp/a/test4 30000
0.036u 1.228s 0:05.95 21.0%     5+182k 2+1109io 0pf+0w
[zhpalt@freebsd]~> time ./a.out /tmp/a/test5 30000
^C0.123u 67.972s 1:10.30 96.8%  5+181k 38+1038io 0pf+0w
（最后一步，實(shí)踐太長(zhǎng)了，我不得不終止了。）
數(shù)量已經(jīng)超出ls和rm的范圍：
/sbin/ls: Argument list too long.
/bin/rm: Argument list too long.

fhzxt

原帖由 prolj 于 2009-2-25 22:35 發(fā)表

Reiser 的特點(diǎn)不是 B Tree，而是實(shí)現(xiàn)了其變種的 B* Tree ，小文件性能好是不給小文件分配 inode （直接存在 Tree 里面？記不清楚了）

恩，是這樣，我沒(méi)注意到那個(gè)*，我查了下，他的查找用的是平衡樹(shù)，存儲(chǔ)是B*Tree

prolj

性能好的原因是小文件直接存儲(chǔ)在 Tree 節(jié)點(diǎn)中？好像還叫什么壓縮。
Reiser4 是更好的選擇。

fhzxt

LZ，突然發(fā)現(xiàn)這種問(wèn)題似乎沒(méi)必要去想，看別人的討論不就完了，請(qǐng)看同一個(gè)人在cu和freebsdchina分別和G版及delphij的討論（看的時(shí)候，千萬(wàn)不能細(xì)想那些計(jì)算啊，因?yàn)楸旧砘�礎(chǔ)可能是錯(cuò)的）：
http://72891.cn/viewthread.php?tid=1320304
http://www.freebsdchina.org/forum/topic_43473.html
ps：Reiser及l(fā)inux下多種文件系統(tǒng)對(duì)比，參考資料http://www.ibm.com/developerworks/cn/linux/l-jfs/

瑪莉隔壁

謝謝