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,349,294 B1
• Filed: 03/15/1999
• Issued: 02/19/2002
• Est. Priority Date: 07/31/1998
• Status: Expired due to Term

• Current Assignee: KOM Software Inc.
• Original Assignee: KOM Inc.
• Inventors: Shaath, Kamel, Freeman, Richard
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/267,788
• Time in Patent Office: 1,072 Days
• Field of Search: 707/200, 707/2, 707/3, 707/100, 707/7, 711/112, 711/122, 711/218, 711/117
• US Class Current: 707/715
• 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 retrievably encoded data on a recording medium is disclosed. A start field for indicating the start of a data file is provided. Immediately following the start field there provided an index field for storing indexing data respecting the data file. In the index field a sequence of one or more positions of other start fields leading in one direction from a current position on the medium toward one end of the medium is stored. Immediately following the index field there is a field for storage data, which forms the data file. A method for storing encoded data on a storage medium is also disclosed. The last file stored on the medium is located. The index field of the last stored file is then retrieved. The index field associated therewith is duplicated for later use. The system then moves the storage medium to the end of the last stored file. At the current position of the medium a filemark is inserted. Then a final leaf block is inserted having a new entry containing the entry key of the new file and the current position of the medium. The indexing data is stored immediately following the filemark and finally the encoded data is stored immediately following the indexing data.

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 including reference to locations of other previous index portions comprising portions of an index range according to the predetermined order, wherein an index portion includes up to a predetermined plurality of entries within the portion of the index range;

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, 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;

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,

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, and

wherein the index 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 higher level.

2. A method of retrievably 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 comprising;

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;

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 by the steps of;

i) extracting a block having a lowest level indicator and locating a target entry in the block by comparison between said entry key of each entry and said new entry key of said new file;

ii) modifying said extracted block to indicate a block in a higher level associated with the new file at a new file position;

iii) moving to a start position indicated by said target entry and reading an indexing data field of a file at the start position;

iiii) extracting a particular block having a higher level indicator indicated by the target entry and locating a next target entry in the block by comparison between an entry key of each entry and the new entry key of the new file;

v) repeating the steps (ii), (iii) and (iiii) until a block having a final leaf level indicator is extracted;

vi) inserting an entry indicating the new file into said final leaf level block; and

vii) including each modified extracted block and the final leaf level block including the entry indicating the new file into the duplicate of the indexing data;

e) inserting the modified duplicate of the indexing data in the new data file;

f) storing the new data file sequentially on the medium following the last file stored; and

,

g) sorting the entries by entry key prior to inserting the modified duplicate of the indexing data in the new data file.

3. A method of retrievably storing encoded data files as defined in claim 2, further including the step of splitting a block into two separate blocks when the number of entries in the block exceeds a threshold.

4. A method as defined in claim 3, the splitting step including the steps of

a) without dividing any of the entries, moving approximately the last half of the entries in the original block into a new block having the same level as the original block;

b) forming a new block in a sublevel, one level below the level of said original block;

c) inserting an entry into the new sublevel block indicating each of the blocks including entries from the original block, the sublevel entries being in entry key order, each of the sublevel entries corresponding to the first entry of each of the blocks including entries from the original block, each entry having a block indicator which is one greater than that of its preceding entry, and an entry address corresponding to the address of the filemark of the new file; and

,

d) storing the two blocks including entries from the original block and the new sublevel block following the filemark.

5. A method as defined in claim 2, wherein the entry fields are arranged in such a way that the entry keys of all the entries in the block remain in entry key order.

6. An optical tape for retrievably storing a plurality of files, each file stored adjacent a previous file, each file comprising:

a start field for marking the start of a file;

an index field for storing indexing data respecting the associated file, and for storing a sequence of one or more positions of other start fields respecting other files leading in a 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 files stored on the medium, and locations of previous index files on the medium containing additional portions of the ordered range,

wherein the index field is positioned adjacent the start field and the data field immediately follows the index field.

7. An optical tape for retrievably storing a plurality of files, each file stored adjacent a previous file, each file comprising:

a start field for marking the start of a file;

an index field for storing indexing data respecting the associated file, and for storing a sequence of one or more positions of other start fields respecting other files leading in a 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 files stored on the medium, and locations of previous index files on the medium containing additional portions of the ordered range,

wherein the index field is positioned adjacent the start field and the data field immediately follows the index field,

wherein the data field is positioned adjacent the start field and the index field immediately follows the data field.

8. A sequential recording medium for retrievably storing a plurality of files, each file comprising:

a start field for marking the start of a file;

an index field for storing indexing data respecting the associated file, and for storing a sequence of one or more positions of other start fields respecting other files leading in a 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 files stored on the medium, and locations of previous index files on the medium containing additional portions of the ordered range,

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,

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, and 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 and

wherein each entry includes;

an entry key;

a block indicator identifying a particular block in a particular level of blocks; and

an entry address field for storing the position on said medium of one of said other start positions.

9. A sequential recording medium as defined in claim 8, wherein the entry address is a filemark count.

10. A sequential recording medium as defined in claim 8, wherein the entry address is an absolute location on the medium.