采用扩展哈希技术实现Ext2文件系统目录索引

文章编号：!(()*#(++（’((+）!’*(!"#*(+

收稿日期：’((+*("*’"

采用扩展哈希技术实现$%&’文件系统目录索引

乔川龙，罗

军

（国防科技大学计算机学院，湖南长沙，,!((-+）

摘

要：提出了一种用扩展哈希技术实现$%&’文件系统目录索引的方法。介绍了扩展哈

希技术的基本概念及采用该技术实现$%&’目录索引的具体方法，并将该方法与.&/00进行了性能比较，比较结果表明，扩展哈希方法性能优于.&/00。关键词：扩展哈希技术；目录索引；$%&’文件系统；.树中图分类号：12+!

文献标识码：3

$%&’作为@CDE%的本地文件系统，在设计实现时兼顾了对@CDE%很多特点的支持F由于其技术上的成熟性而比其他@CDE%支持的文件系统更为可靠。$%&’文件系统采用线性目录入口表的方法存储目录，对小目录而言，这种方法能很好地满足目录操作的要求。但是，随着目录入口数目的不断增加，目录操作的性能就会急速下降，从而成为文件系统整体性能的一个瓶颈。一般说来，采用线性目录入口方法，查找一个入口的平均搜索长度为!7’（，也就是说要读!7’个!为目录中数据块的数目）数据块，这不仅要占用大量的52G时间，而且要进行频繁的67;操作。

近年来，很多主流的文件系统采用.&/00或其变种方法实现了目录索引，并且达到了比较理想的效果。用.&/00的方法实现$%&’目录索引也有很多文章进行过讨论。

本文提出用扩展哈希技术（$%&0DHCIJ08KLMCDN）的思想实现$%&’文件系统目录索引的方法，称之为$%8KLM，实现目录入口的快速查找。假设则对所有目录入口的查找只需读+次$%&’文件系统数据块大小为,O.，

数据块即可完成；而不采用该方法，对稍大的目录，均要超过+个数据块的读取。下面，笔者将对扩展哈希技术的概念、如何利用扩展哈希技术实现目录索引、$%8KLM与.&/00方法的性能比较以及对.&/00方法的完善等几个方面进行具体描述。

是’的$次幂。当要向一个已经满了的“叶块”中插入新的入口时，这个

“叶块”就要分裂成两个单独的“叶块”，哈希表中指向原来“叶块”的指针一半继续指向原始“叶块”，另一半则指向新的“叶块”，而入口则分布在两个“叶块”中，以保证指针的正确指向。当一个“叶块”要进行分裂，而此时却只有一个指针指向该“叶块”时，那么首先哈希表就要进行翻倍增长，这样就会有两个指针指向要分裂的“叶块”，然后该“叶块”就可以正常地进行分裂了。

’采用扩展哈希技术实现$%&’目录索引

在$%&’的6DQH0节点中，通常有!)个指向数据块的域，分别为!’

个直接索引指针，!个一级间接索引指针，!个二级间接索引指针和!个三级间接索引指针，下面将利用一级间接索引指针来间接指向扩展哈希表。

在目录6DQH0节点中设置一个标志位CUPJKN，如果该标志位置位则说明当前目录索引为$%8KLM，对目录的搜索操作采用扩展哈希技术，在这种情况下将目录6DQH0节点中指向数据块的一级间接索引指针解释为指向哈希表（如图!所示），同时还要在目录6DQH0中添加$%MKLMULCV0用来记录以块为单位的当前哈希表的大小。

!扩展哈希技术

扩展哈希技术（的基本思想是通过哈希函数为每$%&0DHCIJ08KLMCDN）

一个文件7目录名映射一个+’位的哈希值，用这+’位哈希值中的一部分位的集合作为哈希表的索引项，相应的哈希表项的指针指向含有目录（入口的“叶块”。在扩展哈希目录中寻找一个特定入口的步骤J0KPIJQRO）

是：计算文件7目录名的哈希值，取哈希值的左"位（"通常与哈希表的大小相关，即哈希表的大小为’的"次幂，因为哈希表的大小是随着目录增大而不断增加的，所以"不是一个定值），作为哈希表的索引项找到相应的指针，通过指针找“叶块”，将该“叶块”读入内存，然后采用线性查找法搜索相应的入口。

扩展哈希技术的哈希表是随着入口的增加而动态增长的。哈希表的大小为’的#次幂，相应文件7目录名的哈希值的左#为作为哈希表的索引，按照+’位哈希值计算，哈希表项指向“叶块”指针占,.C&，哈希表的最大尺寸可为!#S.空间，假设每个“叶块”可以容纳’((个目录入口，每个“叶块”的空间占有率为-)T的话，那么目录入口数最多可以达到#((S.，这么大的目录目前对$%&’文件系统来说是不能达到的，因为$%&’支持的最大文件大小限制在’S.，所以我们对哈希表的大小要做一个限制，后面将会讨论这个问题。当随着入口数的不断增加而哈希表变得过小时，哈希表便增长!倍，用哈希值定位哈希表项时也就增加!位，这也是扩展哈希表名字的由来。

对于“叶块”而言，可以有多个哈希表项指针指向同一个“叶块”，而

“”图!

扩展哈希表$%&’目录索引

图!采用扩展哈希表的$%&’目录索引形式，假设数据块大小为,

指向数据块的指针为,.C&，每个“叶块”平均可容纳’((个目录入口，O.，

“叶块”空间占用率为-)T，则目录最大可以容纳!(’,W!(’,W!)(X这个目录大小目前来讲已经足够大。如果目录一旦!)-’Y#,((个入口，

超过这个极限，那么也不再对哈希表进行扩充，也就是说哈希表最大只能占用!(’,个数据块，而对具有相同哈希索引的“叶块”之间建立线性链表，这样虽然增加了搜索的时间，但是由于这种情况发生的可能性极小，!"#