Patent ID: 7287046
Filing Date: 2007-10-23
Classification: G06F,Y10S

Abstract:
1. A method of compacting sparse directories, comprising: conducting the method in a file system employing a directory structure which uses a sequence of hash tables made up of blocks, with the numbers of blocks in each hash table being the numbers of blocks of its prior hash table in sequence, multiplied by two, and the blocks in each subsequent hash table comprising a lower level of blocks than the blocks in the prior hash table, and with first predetermined blocks at any level associated with second predetermined blocks at the next lower level thereby defining a hashing scheme, the method further comprising; determining whether any first predetermined block for any hash table in the directory structure contains a number of files lower than a predetermined value; if it is determined for any first predetermined block that the number of files therein is lower than said predetermined value, determining if any second predetermined blocks at the next lower level contain any files therein, with said second predetermined blocks having hash vales corresponding to a hash value of said first predetermined block; if any second predetermined blocks at the next lower level contain files therein, migrating files in any second predetermined blocks into its corresponding first predetermined block or as many of the files in any second predetermined block corresponding to said first predetermined block sufficient to fill said first predetermined block to thereby compact sparse directories in the file system employing a directory structure in a manner preserving the bashing schemes from level to level; identifying the blocks in each hash table in binary values, and the blocks which are matched to correspond to each other from level to level for migrating files upwardly through levels being matched by a tail bit sequence of the lower level blocks from which files are to be migrated to an upper level block; and the first level of blocks comprising only one block, and the second Level of blocks comprising two blocks whose blocks correspond to the one block in the first level, and further comprising migrating files from the blocks in the second level to the one block in the first level when the number of files in the block in the first level is lower than said predetermined value to thereby compact sparse directories in the file system employing a directory structure; and setting each block to which directory entries are migrated, to equal the block from which directory entries were migrated.