Method for dynamically expanding and rapidly accessing file directories

• US 5,218,696 A
• Filed: 09/17/1992
• Issued: 06/08/1993
• Est. Priority Date: 07/24/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Myers, James J., Baird, Robert, Tetzlaff, William H., Unger, Jay H., Berbec, Robert R., Bozman, Gerald P., Lett, Alexander S.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/946,829
• Time in Patent Office: 264 Days
• Field of Search: 395/600, 395/650, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A computer-implemented method for the name-oriented accessing of files having at least zero records, any access path to files and records through an external store coupling the computer being defined by a pair of related directories. A first directory of record entries is sorted on a two-part token. The token consists of a unique sequence number assigned to the record and the sequence number of any parent record entry. Each record entry includes the token, file or record name, and external store address or pointer A traverse through the tokens constitutes a leaf-searchable B-tree.

Rapid access to target records is by way of a name-sorted, inverted directory of names and tokens as a subset and which is reconstitutable from the first directory in the event of unavailability.

Claims

1. In a system including a CPU and an external store, said external store having resistant thereon files of records and directories, said CPU having an operating system (OS), internal storage, and means including the OS and internal storage for establishing an access path to said files, records, and directories on the external store, a method for attribute oriented accessing of files having at least zero records, each record having at least one field, any access path from the CPU to files and records on said external store being defined by at least one directory, comprising the steps of:

(a) forming a first directory of records by said OS in internal storage and copied to said external store, in which each record entry includes a token, attributes, and an external storage address or pointer thereto, each token comprising a unique identifier for the record entry and a unique identifier for any parent file or record of the record entry, said entries being arranged in token sorted order, traverse of said tokens constituting a leaf search B-tree, the identifiers constituting each token being members of an infinite set such that when once the token is removed from the directory the token is never repeated;

(b) forming a second directory from said first directory by said OS in internal storage and copied to said external store, each entry including a predetermine attribute (e.g. record name) and a counterpart token, said entries being arranged in the second directory in predetermined attribute sorted order; and

(c) responsive to a selected instance of the predetermined attribute as a search argument, accessing target records by way of a leaf searchable path through the second and first directories conducted by the OS in internal storage and the accessing means.

2. The method according to claim 1, wherein said method further comprises the steps of:

(d) in the event of the unavailability of the second directory such as occasioned by external store media or write path failures, deriving said second directory from the first directory by said OS executing a sort in internal storage as a predetermined attribute oriented sorted subset thereof.

3. The method according to claim 1, wherein the second directory constitutes an inverted directory subset derived from the first directory.

4. The method according to claim 1, wherein the predetermined attribute is the record for file name, and further wherein the number tokens being very large relative to the number of names, and still further wherein tokens are associated only once with each record entry and never associated with any other record entry.

7. The method according to claim 1 or to claim 5, wherein the OS further includes a lock manager for restricting access to a file by imposing a lock thereon responsive to a read or write access request matching a file attribute defining lock status, and

wherein said method comprises the further step of, during execution of an access request and upon ascertaining the lock status of a named file, furnishing the token as a surrogate argument to the lock manager and causing said lock manager to impose a token based rather than a file name, alias, or synonym based lock instead.

8. The method according to claim 1 or claim 5, wherein said method further includes the steps of

effectuating recovery of said first directory by the OS in internal storage by duplicating at least a portion of each directory file entry, appending the duplicated portion to the counterpart file as a suffix, indivisibly recording the file and the suffix in the external store, and in the event of unavailability of the first directory, at least partially reconstructing said unavailable first directory by sorting and collating the suffix portions of the files,

causing each first directory entry to include a token as an attribute thereof, and further causing said token included suffix to be appended and recorded with each counterpart file in external store indivisibly;

and

recovering said second directory from said first directory by scanning the parent identifier and constructing a directory structure therefrom and from the attribute part of each file entry by the OS in internal storage.

9. The method according to claim 1 or claim 5, wherein said CPU includes means for effectuating recovery of said first directory by duplicating at least a portion of each directory file entry, appending the duplicated portion to the counterpart file as a suffix, indivisibly recording the file and the suffix in the external store, and in the event of map unavailability, at least partially reconstructing said map or directory by sorting and collating the suffix portions of the files, and wherein said method comprises the further steps of:

causing each map entry to include a token as an attribute thereof, and further causing said token included suffix to be appended and recorded with each counterpart file in external store indivisibly; and

recovering said second directory from said first directory by scanning the parent identifier and constructing a directory structure therefrom and from the attribute part of each file entry.

5. In a system including a CPU and an external store having resident thereon files of records and directories, said CPU having an operating system (OS), internal storage, and means including the OS and internal storage for establishing an access path to the files, records, and directories on the external store, a method for the name oriented accessing of files having at least zero records, each record having at least one field, each parent record or file having a unique sequence number assigned thereto, any access path from the CPU to files and records on said external store being defined by at least one directory, comprising the steps of:

(a) forming a first directory of record entries by said OS an internal storage and copied to said external store said record entries being sorted on a unique sequence number as the first field of an ordered pair of fields, each record entry including the ordered pair, record or file name, and external address or pointer fields, the second number of the ordered pair being the same as the unique sequence number assigned to a parent record or file of the record entry, a traverse through said ordered pairs constituting a leaf searchable B-tree, the ordered pair constituting each token being members of an infinite set such that when once the token is removed from the directory the token is never repeated;

(b) forming a second directory from the first directory by said OS in internal storage and copied to said external store, each entry including a name and an ordered pair, said entries being arranged in the second directory in name sorted order;

(c) responsive to a selected instance of a file or record name as a search argument, accessing any target records by establishing a leaf searchable B-tree path through said second and first directories as conducted by the OS in internal storage and the enclosing means; and

(d) assigning a unique sequence number by the OS, not previously assigned, responsive to causing any new record entry to be made in the first directory.

6. In a system including a CPU and an external store having resident thereon files of records and directories, said CPU having an operating system (OS), internal storage, and means including the OS and internal storage for establishing an access path to the files, records, and directories on the external store, a space efficient method for the name oriented accessing of files having key based variable length records using at least one directory, comprising the steps of:

(a) forming a leaf search B-tree organized key or storage location directory of records and their descriptive attributes by said OS in internal storage and copied to said external store, and, expanding, populating, and amending said directory responsive to a write access, said attribute directory having a domain relatively infinite to the domain of keys, each key including a unique identifier for a counterpart record and a unique identifier for any parent file or record, the identifiers constituting each key being members of an infinite set such that when once the token is removed from the directory the token is never repeated;

(b) forming from said attribute directory of a leaf search B-tree organized directory of names or pointers to said attribute directory entries, said name directory being formed by the OS in internal storage and copied to said external store; and

(c) responsive to a selected instance of a file name, accessing target records by establishing a leaf search path through the name and attribute directories as conducted by the OS in internal storage and the accessing means.