Method of determining and storing indexing data on a sequential data storage medium for supporting random access of data files stored on the medium

• US 6,546,384 B2
• Filed: 02/08/2002
• Issued: 04/08/2003
• Est. Priority Date: 07/31/1998
• Status: Expired due to Term

• Current Assignee: KOM Software Inc.
• Original Assignee: KOM Networks, Inc.
• Inventors: Shaath, Kamel, Freeman, Richard
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US10/067,916
• Publication Number:
  US 20020073096A1
• Time in Patent Office: 424 Days
• Field of Search: 707/2, 707/3, 707/100, 711/112, 711/117, 711/122, 711/218
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/80 in storage media based on magnetic or optical technology, e.g. disks with sectors preventing unauthorised reproduction or copying of disc-type recordable media G11B20/00
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: G06F 3/0682 Tape device
• CPC Class Codes: G11B 2220/90 Tape-like record carriers
• CPC Class Codes: G11B 27/309 Table of contents
• CPC Class Codes: G11B 27/328 on a tape [TTOC]
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A format structure for storing retrievable data on a sequential data storage medium, which includes in an exemplary embodiment a start field for indicating the start of a data file, an index field for storing indexing data respecting the data file, and a data field. Stored encoded data on the storage medium can use the last file written on the storage medium to create indexing data that can be stored alongside the data files as they written so that each sequential data storage medium remains fully indexed.

Claims

1. 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 indexing the last previously written data on the sequential data storage medium including reference to locations of other previous index portions comprising portions of an index range according to the predetermined order;

determining an index position for index data relating to the stored 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 stored data file results in a change to any of the index portions or if the index portions are unchanged;

storing an index within an index field of the stored data file on the sequential storage medium including;

references to the location of any index portion that are determined to remain unchanged; and

index portions that are changed to include the index data relating to the stored data file according to the predetermined order.

2. A method of retrievably storing indexed data as defined in claim 1, wherein the last written index portion includes reference to locations of index portions comprising portions of an index range according to the predetermined order.

3. A method of retrievably storing indexed data as defined in claim 2, wherein an index portion includes up to a predetermined plurality of entries within the portion of the index range.

4. A method of retrievably storing indexed data as defined in claim 3, wherein an index portion is changed, to add a new entry, or when the predetermined plurality of entries is exceeded to redefine the portion of the index range comprising an index portion.

5. A method of retrievably storing indexed data as defined in claim 4, wherein the index portions are stored in a hierarchical structure of blocks, including at least one final leaf level block, each entry in each said final leaf level block containing the actual address of a data file.

16. An apparatus as defined in claim 5 wherein the means for traversing a tree branch comprises means for reading successive index portions and determining from each successive index portion either a next index portion location or the location of the file.

6. A method of retrievable storing encoded data files on a sequential storage medium, comprising 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, the first indexing data comprising a start position of a sequence of one or more other files;

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.

7. A method of retrievably storing encoded data files as defined in claim 6, further including the step of sorting the entries by entry key prior to inserting the modified duplicate of the indexing data in the new data file.

8. A method of retrievably storing encoded data files as defined in claim 6, wherein the indexing data of the last file stored on the medium comprises:

a start position of a sequence of one or more of other files, including indexing data, leading in one direction from a current position on the medium toward one end of the medium, the indexing data including;

one or more blocks arranged in a hierarchy for storing indexing data, each block including;

a block level indicator;

an entry field for storing a plurality of entries including the other start positions, each entry including;

an entry key;

a block indicator for storing the identity of an associated higher level of block in the one or more blocks; and

an entry address indicating the position on the medium of at least one of the other start positions; and

,

an end of block indicator.

9. 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 data file written on the medium, the last file having an adjacent indexing data field;

b) reading an indexing data field of the last file, said indexing data field having at least one block ordered in a hierarchy of block levels, each block including a block level indicator and an entry field for storing a start position of a sequence of one or more other data files;

c) extracting a lowest level block and finding an indication of an immediately higher level block having information relating to the data file by comparison of the specific entry key of the data file with information contained in the lowest level block;

d) moving to a position on the medium of a data file having the immediately higher level block;

e) reading an index field adjacent the data file and extracting from the immediately higher level block a indication of a further immediately higher level block having information relating to the data file by comparison the specific entry key of the data file with information contained in the immediately higher level block;

f) repeating the steps (d) and (e) until a final leaf level block is extracted;

g) moving to a data file position having the data file indicated by information contained in the final leaf level block.

10. A sequential recording medium for retrievably storing a plurality of data files, each data file indexed according to a predetermined order, each data file comprising;

a start field for marking the start of a data file;

an index field for storing indexing data respecting the associated data file, and for. storing a sequence of one or more positions of other start fields respecting other data files leading in reverse direction on from a current position on the medium toward the beginning of said medium; and

,

a data field for storage data which forms said data file,

wherein the index field identifies an ordered range of data files stored on the medium, and locations of previous index files on the medium containing additional portions of the ordered range.

11. A sequential recording medium as defined in claim 10, wherein the sequential recording medium is optical tape and each file is stored adjacent a previous file.

12. A sequential recording medium as defined in claim 10, where the associated index field comprises one or more hierarchically structured blocks of indexing data, each said block including:

an indexing level indicator in accordance with the defined indexing hierarchy;

an entry field for storing up to a determined plurality of entries indicative of the positions of other start fields; and

an end of block indicator field.

13. A sequential recording medium as defined in claim 12, wherein the defined indexing hierarchy in each said index field includes at least one final leaf level block, each entry in each said final leaf level block containing the address of a data file.

14. A sequential recording medium as defined in claim 13, wherein the defined indexing hierarchy further includes one or more subsidiary levels each having one or more indexing blocks, each said block in said subsidiary levels including an entry corresponding to at least one block in a next higher level.

15. An apparatus for retrieving a data file stored on a sequential recording medium, the data file indexed according to a predetermined order, absent a separate index for the data file, the apparatus comprising:

a data reader for reading data from a current location on the storage medium;

a mechanism for varying the current location; and

a processor for controlling the mechanism and the data reader and for receiving data from the data reader, the processor comprising;

means for locating a current index field adjacent a current data file stored on the medium and for controlling the data reader to read the current index field and provide the read data to the processor,

means for traversing a tree branch determined from the provided current index field, the tree branch having at least an additional index field forming a leaf level storing a location of the file on the storage medium, the additional index field stored at another location on the storage medium adjacent another data file, and

means for controlling the mechanism to move the storage medium to the location of the file and for controlling the data reader to retrieve the file therefrom.