Memory archiving indexing arrangement

• US 5,301,286 A
• Filed: 01/02/1991
• Issued: 04/05/1994
• Est. Priority Date: 01/02/1991
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: Rajani, Purshotam
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): WHITFIELD, MICHAEL
• Application Number:
  US07/636,310
• Time in Patent Office: 1,189 Days
• Field of Search: 395/400, 395/600
• US Class Current: 711/202
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A facility is provided for locating a file in a backup memory, in which each of the components forming a hierarchical pathname identifying the file is converted into a unique identity using a minimum of bytes, and in which the location of the file in backup memory is determined as a function of each such identity rather than the component names forming the hierarchical pathname.

Claims

1. A method of locating a file in a backup memory, said file being one of a group of related files stored in said backup memory, said files being identified by a name common to said files, said name common to said files being one component in a sequence of N components identifying a path name associated with said file, where N≧

=1, said method comprising the steps of

converting each of said components into a respective identity value, and

determining the location at which said file is stored in said backup memory as a function of each of said identity value beginning with the identity value associated with a first component in said sequence of N components, and wherein said method further comprises the steps of

storing each of said components in an available location of a first table of locations such that the address of said available location defines the unique identity value of the component stored thereat, and

deriving for each of said components an associated hashing number and storing in a second table of locations at a location identified by said hashing number the address of the available location.

2. The method set forth in claim 1 wherein said step of converting includes the step of

passing each component of said sequence of components through a hashing algorithm to derive the associated hashing number and then retrieving the respective identity value from said second table using said hashing number as an index into said second table.

3. The method set forth in claim 1 wherein said method further comprises the step of

storing as respective entries in a third table each said identity value and other identity values associated with respective ones of other files and/or directories such that individual ones of said entries are formed into groups of linked entries in said third table based on their order within said sequence of components, and

storing in each of said entries first and second indices, in which said first index points indirectly to a next subordinate group of entries and in which said second index points indirectly to a backup memory location at which the file identified by the associated identity value is stored, and wherein said step of determining includes the steps of

identifying in the order that said components appear in said sequence a first entry forming the associated one of said groups of entries and then locating within the associated group of entries the entry containing the associated unique identity value, and

retrieving said second index from an entry forming a last one of said identified groups of entries and containing the unique identity value associated with said file name.

4. A method of associating a backup memory index with a file identified by a file name, said file name being one component in a sequence of components defining a pathname, in which said file name may be associated with a group of related files stored in said backup memory and in which each of said related files is an individual version of said file, said method comprising the steps of

establishing in memory a table of records, a group of said records being associated with respective ones of the files forming said group of related files, each of said records of said group of records being linked to one another and having at least one field containing an index identifying the location in said backup memory at which its associated one of said files is stored,

converting said components forming said sequence into respective identity values,

determining, as a function of each of said values, the location in said memory at which a first one of said group of related records is stored,

traversing said linked group of related records to locate that one of said group of records associated with said file,

retrieving from said one of said group of records the associated backup memory index identifying the backup memory location at which said file is stored, and wherein said method further comprises the steps of

storing each of said components in an available location of a first table of locations such that the address of said available location defines the unique identity value stored thereat, and

deriving for each of said components an associated hashing number and storing in a second table of locations at a location identified by said hashing number said address of said available location.

5. The method set forth in claim 4 wherein said step of converting includes the step of

passing each component of said sequence of components through a hashing algorithm to derive the associated hashing number and then retrieving the associated identity from said second table using said hashing number as an index into said second table.

6. The method set forth in claim 4 wherein said method further comprises the step of

storing as entries in a third table each said identity value and other identity values associated with respective ones of other files and/or directories such that individual ones of said entries are formed into groups of linked entries in said third table based on their level within said sequence of components, and

storing in each of said entries first and second indices, in which said first index points indirectly to a next subordinate group of entries and in which said second index points indirectly to a backup memory location at which the file identified by the associated unique identity value is stored, and wherein said step of determining includes the steps of

identifying in the order that said components appear in said sequence a first entry forming the associated one of said groups of entries and then locating within the associated group of entries the entry containing the associated unique identity value, and

retrieving said second index from an entry forming a last one of said identified groups of entries and containing the unique identity value associated with said file name.