ext3的dir_index特性
前几次开发中，研究了一下硬盘的layout，看到ext2下的目录都是把自己的子文件的信息——更准确的说是ext2_dir_entry结构——放在自己的data block里（当然，可能是多个data block），存放顺序就是创建这些子文件的顺序。
前天李勇同学点拨，才知道从ext3开始，还多了一个"dir_index"特征（默认的），启用后，ext3_dir_entry（目录下的文件名信息）将以类似btree的形式存放在目录的data block里，其中用于排序的是子文件信息的hash值。
如上图。目录inode的第一个data block（标注为index_block）里是由一堆dx_dentry结构组成的，这个data block还有个struct dx_root作为头部。
在我的实验里，一个目录里创建了1000个文件，且文件系统的block size是1024字节，此时目录的index_block里有22个dx_entry结构，这22个dx_entry是按照其第一个成员变量——hash来排序的，而第二个成员变量——block分别指向22个磁盘块，这些被指的磁盘块里才放着ext3_dir_entry结构。这个index_block就相当与btree里的索引节点，而被指向的磁盘块就相当于btree里的叶子节点
对于非dir_index的ext3文件系统，在目录里寻找某个文件名只能是顺序遍历，一旦文件数多了速度就会很慢；而在使用了dir_index后，就能迅速定位到在哪一个磁盘块了。可惜，在定位到某个磁盘块以后，只能是遍历这个磁盘块里的所有ext3_dir_entry了。
====== 2011.3.21 ======
1. 一个目录刚创建或目录里文件数很少的时候，并不采用dir_index（从inode的i_flags字段也可以看出这一点），当目录下的文件数越来越多，其ext2_dir_entry结构占用超过一个block后，才会将该目录变为dir_index
2. 即使是dir_index，一个目录下可放的文件数也不是无限的，从我们的实验来看，对于一个block size为4K的文件系统，如果用户的文件名很大（我们的实验是100个字节），一个目录下也就最多放500万个文件，超过这一限制，内核就会狂报"dir index full“的错误。因为dir_index在设计上就最多只允许两层索引节点加一层叶子节点。
====== 2011.5.19 ======
1. 不管在ext3还是在ext4,dir_index都只允许两层索引，也就是说，inode指向一个存满了dx_entry的block，其中某个dx_entry指向另一个存满了dx_entry的block，这第二层的dx_entry就只能指向一个存ext3_dir_entry的block，不能再指向一个存dx_entry的block ...... 但愿我说明白了。
2. 从coly同学那里新学到的：随着目录下文件的增加，这个dir_index的tree会保持平衡，但是如果删除目录下的文件，这个tree不会再作 rebalance 操作（也许是怕代码太复杂），tree有可能会慢慢变得“歪”起来。
相关文章
- ext2/ext3/ext4 文件系统初探 - 01 20, 2011
- linux在多核处理器上的负载均衡原理（幻灯片） - 10 22, 2010
- [kernel] 内核缓冲的锁 - 08 11, 2010
兄弟，有空可以研究一下zfs，开源，zfs当之无愧的真的是其说的“the last word of filesystem”，其思想基于wafl，但是很多地方远高于wafl，几近完美。
多谢推荐，我有空就看看 :)
讲的很清楚，感谢
凑巧也了解到dir_index的内容，这篇文章为我省了很多时间，thx！
“ 一个目录刚创建或目录里文件数很少的时候，并不采用dir_index（从inode的i_flags字段也可以看出这一点），当目录下的文件数越来越多，其ext2_dir_entry结构占用超过一个block后，才会将该目录变为dir_index”
刚好人肉看到代码，ext3_add_entry会检查is_dx(dir)，如果成立再做ext3_dx_add_entry。
is_dx检查的逻辑就是文件系统设置了dir_index feature，并且EXT3_I(dir)->i_flags & EXT3_INDEX_FL)。
粗看代码，的确是占满一块之后，开始调用make_indexed_dir，会设置EXT3_INDEX_FL。
这里想问个问题，有没有工具可以查看inode的i_flags？我找了stat和debugfs，好像都看不了。
@xanpeng，就是用stat ，出来的信息如下：
Inode: 56673 Type: directory Mode: 0755 Flags: 0x1000
Generation: 917510159 Version: 0x00000000
User: 0 Group: 0 Size: 20480
File ACL: 0 Directory ACL: 0
Links: 2 Blockcount: 40
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x5080dd18 -- Fri Oct 19 12:54:48 2012
atime: 0x5080dd0b -- Fri Oct 19 12:54:35 2012
mtime: 0x5080dd18 -- Fri Oct 19 12:54:48 2012
Size of extra inode fields: 4
BLOCKS:
(0-4):256000-256004
TOTAL: 5
第一行的Flags就是inode的i_flags，0x1000就是EXT3_INDEX_FL的值
@DongHao，的确！突然犯傻了，不好意思 :-(
@DongHao. 初看你的stat输出，顿时觉得自己看错了自己的stat输出。但结果不是，仔细一看，我的stat输出还真没有flags。
# /usr/local/bin/stat --version
stat (GNU coreutils) 8.19
...
# /usr/local/bin/stat coreutils-8.19.tar
File: ‘coreutils-8.19.tar’
Size: 47011840 Blocks: 91928 IO Block: 4096 regular file
Device: 807h/2055d Inode: 10262 Links: 1
Access: (0644/-rw-r--r--) Uid: ( 0/ root) Gid: ( 0/ root)
Access: 2012-10-19 17:18:37.000000000 +0800
Modify: 2012-10-19 17:16:52.000000000 +0800
Change: 2012-10-19 17:13:12.000000000 +0800
为啥，你们用的是自己修改过的吗？
@xanpeng，喔，你得用最新的e2fsprogs，可以自己拿源码编译：http://git.kernel.org/?p=fs/ext2/e2fsprogs.git;a=summary
@DongHao, 的确需要新的e2fsprogs, 而且要用debugfs的stat。搞定，多谢:)