大容量内存文件系统设计及μC/OS下的实现 02

samwalton

（2）Hash表的组织和查找在获得Hash值后，如何将8个字节的Hash值有效地组织在全局Hash表中来获得最高的查找速度是一个关键问题。根据数据结构算法理论可知，将Hash表顺序组织为一个有序表，可以通过折半查找法来获得最高的查找效率。其比较次数最多为└log2n┘+1（n为表中的记录个数），其平均查找长度ASL（Average Search Length）近似为log2(n+1)-1。然而，随着文件的动态增加或删除，每个文件对应的Hash值或大或小，这样系统的Hash表并不能保证是一个顺序表，因此就不能采用折半查找法。如果首先将无序的Hash表排列为有序表再采用折半法查找，那么即使在最好的情况下，排序操作所需要的时间复杂度也为O（nlogn），同时还需要其它的辅助存储，这样在排序操作上就要花费大量的时间和存储空间，使整个系统的查找效率大大降低。针对此不足，本文采用链地址法组织全局Hash表，将全局Hash表分为两部分：其本表和溢出表。其基本思想为：首先分配一个固定大小（这里假设取1024项）的顺序表作为基本表，每个文件计算得出的Hash值通过对1024取模得到个介于0～1023之间的模值。如果此模值在基本表中的对应项没有被占用，那么该项就作为此文件的Hash项；如果此模值在基本表中的对应项已被其它文件占用，那么就溢出表中申请一个此文件的Hash项，并将此Hash项链接到具有相同模值的链表中。通过这种顺序表和链表相结合的结构，既会影响查找速度又不会增加额外存储空间，从而提高EMFS的查找效率而且不增加系统的时间和空间复杂度。
1.2 文件状态表
文件状态表用来存放文件系统中文件的各个属性，包括文件名称、文件大小、读写标志、创建和修改时间。同时，为了提高内存空间的利用率，可以对文件进行选择性压缩存储，因此文件状态表也包括文件压缩标志，压缩前的原始大小和压缩后的文件大小。从图2可以看到，文件状态表是和Hash表以及数据块链表连在一起的，那么一旦定位到文件对应的Hash项，就可以对文件状态表进行读写。
1.3 数据块链表
在EMFS中，文件数据内容保存在内存数据块中，内存数据块的大小可以在建立文件系统时动态设定。数据块链表的作用是对内存块进行管理。由于数据块链表中每一项对应一个内存块，所以当添加文件时，系统根据文件大小动态地从数据块链表中申请一定数量的数据块；当删除文件时，系统将数据块插入到此链表中。