100W个文件存放1个目录和平均存放在10个目录，哪种方式访问更快

最近突发奇想：100W个文件存放1个目录和平均存放在10个目录，哪种方式访问更快。

要想回答这个问题，首先得明白Linux是怎么定位文件的。Linux文件系统作为一种树状接口，定位文件是一层一层向下查找的。

A Linux filename has the same format as all Unix filenames have. It is a series of directory names separated by forward slashes (/) and ending in the file’s name. One example filename would be /home/rusling/.cshrc where /home and /rusling are directory names and the file’s name is .cshrc. Like all other Unix systems, Linux does not care about the format of the filename itself; it can be any length and consist of any of the printable characters. To find the inode representing this file within an EXT2 file system the system must parse the filename a directory at a time until we get to the file itself.

The first inode we need is the inode for the root of the file system and we find its number in the file system’s superblock. To read an EXT2 inode we must look for it in the inode table of the appropriate Block Group. If, for example, the root inode number is 42, then we need the 42nd inode from the inode table of Block Group 0. The root inode is for an EXT2 directory, in other words the mode of the root inode describes it as a directory and it’s data blocks contain EXT2 directory entries.

home is just one of the many directory entries and this directory entry gives us the number of the inode describing the /home directory. We have to read this directory (by first reading its inode and then reading the directory entries from the data blocks described by its inode) to find the rusling entry which gives us the number of the inode describing the /home/rusling directory. Finally we read the directory entries pointed at by the inode describing the /home/rusling directory to find the inode number of the .cshrc file and from this we get the data blocks containing the information in the file.

Simplified structure of the UNIX file system.

以/home/you 举例，首先需要访问根节点的inode，然后迭代访问/的目录内容，匹配到home得到inode，然后读取home目录的内容，匹配得到you的inode，最后根据inode去读data block。

所以查找文件是一个O(N)的操作，大量文件存放在多个目录，访问更快。

参考：
[0x01]http://www.porcupine.org/forensics/forensic-discovery/chapter3.html#figure3.2
[0x02]http://www.tldp.org/LDP/tlk/fs/filesystem.html#ext2fs-dir-figure