Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-02-08
2003-04-08
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C711S112000, C711S117000, C711S122000, C711S218000
Reexamination Certificate
active
06546384
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method of indexing data on a sequential data storage medium for storing and locating data files, and a storage medium such as magnetic and optical tape, and the like incorporating the indexing data.
BACKGROUND OF THE INVENTION
The conventional method of storing encoded data files, such as those generated by a computer, on a tape medium is to write a filemark at a point on the tape at which the data file is to be stored, write a label block containing the name of the data file or other data by which the file may be identified, store the label block immediately following the filemark and then write the data immediately following the label block. In some instances, the data file archiving process involves bundling a number of files and storing the bundled files as a single file on the tape. While this process simplifies the process of storing the files on the tape, it complicates the process of retrieving individual files from the tape when required. Frequently, the entire bundle must be retrieved to operating memory of a computer in order to extract a desired file. It would be desirable to be able to retrieve a single file without these complications.
When files are stored individually, the conventional method of retrieving an individual file is to sequentially read the label block of each of the files on the tape until the desired file is located. Once located, the file is retrieved. This process is satisfactory when the number of files is relatively small, such as a few hundred or thousand files. However, the process is extremely slow and tedious when the number of files is in the order of millions. Optical tape capable of storing almost 1,000 GigaBytes of data representing potentially millions of files is now commercially available. A single tape can replace an entire tape library consisting of thousands of tapes and eliminate costly and time-consuming manual loading, unloading and tape maintenance. Clearly, retrieval of these files can be extremely time consuming with conventional file retrieval methods.
Indexing methods for sequential recording media such as magnetic or optical tape frequently involves dedicating a portion of tape for index storage separate from the data storage. Each time a file is added to the tape the tape must be reversed to the index portion to add the new index data and then back to the data storage portion to add the next file. This head movement back and forth through the tape slows the data storage system significantly. Even the above noted methods of scanning a tape for a particular file are highly dependent on tape length and speed of the reader. When a tape requires 90 seconds to travel end to end, a randomly selected file will average 45 seconds to retrieve excluding processing time for processing each file block.
Other indexing methods store index data in memory, such as the computer hard drive. Only when the tape is substantially filled is a complete index written on the tape. It is desired to have index information resident in an operating memory, such as the hard drive, RAM or other memory than the tape, for search functions when files are to be retrieved from a tape. However, for archiving purposes, the index information is not secure while stored in operating memory. A catastrophic failure such as a hard disk crash could result in the loss of all indexing data. Recreating the index is time consuming requiring reading each of the file identifiers on the tape and reassembling the indexing data. For numerous and large tapes, the risk of losing indexing data is undesirable. In addition, archiving processes involve the compilation of numerous tapes simultaneously. Completed tapes may include indices stored on tape. However, the partially completed tapes generally do not. As a result, numerous indices may be stored in memory at once greatly increasing the consequences of a data loss. Changing partially filled tapes also presents similar difficulties, since an index may not be available in the operating memory and must be compiled from the partial tape.
These prior art practices of “guess work” retrieval, or a file indexing system based on magnetic disk techniques are incompatible with archival needs and greatly complicate the handling and distribution of numerous tapes for extensive tape libraries. Conventionally, data stored on tape media is not modified. Modified files are merely written to the end of the tape, further complicating the indexing and retrieval process. That said, some tape media are rewritable. It would be preferable for any indexing method to accommodate both rewriting of data files on rewritable media and replacing files on write once media.
Accordingly, there is a need for a simpler, faster and more efficient method of storing and retrieving files stored on large tapes. In addition it is desired to store cumulative index information on the tape as data is added so that the loss of an index in memory can be quickly and easily restored from index data on the tape, without reading every file.
SUMMARY OF THE INVENTION
The present invention provides a novel tape file formatting structure and a method for storing and retrieving individual files from potentially millions stored on a single tape. In accordance with the present invention, index data is stored on the tape alongside the files as they are written so that each tape remains fully indexed all the time and for all time. All tapes are self-contained and do not require additional magnetic disk storage. Even with several million files on a tape, a single file can be quickly and easily retrieved. The present invention may be supplied as an easy to use application program which allows the user to write files to tape, read them back, and perform many other functions or as a subroutine package which allows the user to incorporate the present invention into the user's own software.
One aspect of the present invention provides a method of retrievably storing indexed data on a sequential data storage medium, the data indexed according to a predetermined order, comprising the steps of:
storing a data file on the sequential storage medium;
identifying the presence of a last written index portion including reference to locations of other previous index portions;
determining an index position for index data relating to the data file within the identified last written index portion according to the predetermined order;
for any of the identified previous index portions, determining if the addition of the index data relating to the data file results in a change to any of the index portions or if the index portions are unchanged;
storing an index on the sequential storage medium including:
references to the location of any index portions that are determined to remain unchanged; and
index portions that are changed to include the index data relating to the data file according to the predetermined order.
A further method of retrievably storing encoded data files on a sequential storage medium, in accordance with the present invention comprises the steps of:
a) locating a last file stored on the medium;
b) duplicating first indexing data of the last file stored on the medium;
c) compiling second indexing data for a new data file having a primary key and a start position of the new file on the medium;
d) modifying the duplicate of the first indexing data to include the second indexing data of the new data file;
e) inserting the modified duplicate of the indexing data in the new data file; and
f) storing the new data file sequentially on the medium following the last file stored.
A still further preferred method, in accordance with the present invention, comprises a method for locating a data file stored on a sequential recording medium having a specific entry key, absent an index for the data file stored in operating memory said method comprising steps of:
(a) locating a last file written on the medium;
(b) reading an indexing data field of the last file, said indexing data field having at least one block ordered in a hierarchy of bl
Freeman Richard
Shaath Kamel
Albrecht Ralph F.
Homere Jean R.
KOM Networks Inc.
Venable
LandOfFree
Method of determining and storing indexing data on a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of determining and storing indexing data on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining and storing indexing data on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101022