| 主权项 |
一种分布式文件系统中基于后缀树的目录组织方法，其特征在于：包含以下步骤：A、将目录项分成若干组，分别存储在不同的磁盘上。分组的方式采用简单的字符串哈希的方式，给定字符串S以及总的组数N，则S所处的组序号n为：n＝hash(S)％N；B、根据应用中后缀相同的目录项，建立后缀树；C、在本实施方案中，目录的内容分为两个部分：第一部分是后缀树的节点，该项长度不定，包含该节点到其父节点的边所对应的字符串，父节点在其所处层的序号，以及该节点对应的目录项号；第二部分是目录项，该项定长，包含除了目录项名称以外的其他信息，如目录项所代表的文件或目录的索引节点号等；存储时，将后缀树从根节点开始，采用广度优先的方法，将树节点按照层次顺序存储到同一个文件；然后将目录项信息存储在另一个文件中去。D、需要访问目录时，先将后缀树节点分层从文件读入内存，然后根据节点中记录的父节点在其所处层次中的序号，找到其父节点后，挂入父节点的孩子队列，如此处理，直到节点文件处理完毕；需要访问具体目录项时，根据后缀树节点中记录的目录项索引号，在目录项信息文件中寻址到该项后读出；E、为后缀树设定一个节点数目限制，当后缀树的节点数目超过该门限时，需要对后缀树进行分裂；分裂时，将树根节点的所有子节点按照后缀的首字母分为两组，分别构建出一棵新的后缀树；记录下分布在每个子节点到根节点的边对应的字符串首字母，存储起来；当后缀树分裂后，每棵后缀树需要单独存储；随着时间的推移，那些长时间没有被访问的后缀树，可以回收以释放内存。 |
