为什么单目录下子文件过多会影响性能?

玛莉隔壁

为什么单目录下子文件过多会影响性能?如1个目录下有10000个子文件，那么读取某个文件的速度将会明显慢下来？这和文件索引有关吗？索引中如何组织这些节点？谢谢大家帮忙

fhzxt

大致说一下，硬盘的基本单位是块，块有独立地址，文件的地址（类似于指针）由一个索引块组织，因为一个块的大小是有限的，所以只能存储一定数量的文件地址，当一个目录的文件数超过这个数量时，就需要将索引块也索引起来，就是索引的索引，即为2重索引，如果还不够就要3级索引，这自然会影响速度。一些名词可能用错，大致意思就是这样。
ps：据说现在有些文件系统（比如杀人犯的那个）使用btree作为索引结构，可以提高小文件的查找速度

玛莉隔壁

b+tree的结构应该不用考虑单个目录文件过多问题吧？

fhzxt

按Btree的结构就查找看影响很小，如果排序合理的话，可以减少数量级的查找量。
具体还是做个实验比较好，毕竟我们并不知道现在bsd的ufs的确切查找和管理方式。

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

prolj

原帖由 fhzxt 于 2009-2-25 21:09 发表
大致说一下，硬盘的基本单位是块，块有独立地址，文件的地址（类似于指针）由一个索引块组织，因为一个块的大小是有限的，所以只能存储一定数量的文件地址，当一个目录的文件数超过这个数量时，就需要将索引块也 ...

Reiser 的特点不是 B Tree，而是实现了其变种的 B* Tree ，小文件性能好是不给小文件分配 inode （直接存在 Tree 里面？记不清楚了）

fhzxt

无聊得很，就随便编了一个能自动创建文件的程序，参数是：a.out 首起文件名 数量
发现单一目录下文件再多（数10w）也不影响查找，不过似乎对创建和删除有严重的影响，类似于溢出，看记录：
[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
（最后一步，实践太长了，我不得不终止了。）
数量已经超出ls和rm的范围：
/sbin/ls: Argument list too long.
/bin/rm: Argument list too long.

fhzxt

原帖由 prolj 于 2009-2-25 22:35 发表

Reiser 的特点不是 B Tree，而是实现了其变种的 B* Tree ，小文件性能好是不给小文件分配 inode （直接存在 Tree 里面？记不清楚了）

恩，是这样，我没注意到那个*，我查了下，他的查找用的是平衡树，存储是B*Tree

prolj

性能好的原因是小文件直接存储在 Tree 节点中？好像还叫什么压缩。
Reiser4 是更好的选择。

fhzxt

LZ，突然发现这种问题似乎没必要去想，看别人的讨论不就完了，请看同一个人在cu和freebsdchina分别和G版及delphij的讨论（看的时候，千万不能细想那些计算啊，因为本身基础可能是错的）：
http://bbs.chinaunix.net/viewthread.php?tid=1320304
http://www.freebsdchina.org/forum/topic_43473.html
ps：Reiser及linux下多种文件系统对比，参考资料http://www.ibm.com/developerworks/cn/linux/l-jfs/

玛莉隔壁

谢谢