Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Key Directed Interleave

IP.com Disclosure Number: IPCOM000078021D
Original Publication Date: 1972-Oct-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Parkinson, J: AUTHOR

Abstract

The principle of interleave is to bring records from different sequences but with similar keys, to approximately the same part of a disk, so as to save seek time while merging. However, with many types of presequencing, it is not true that first keys, last keys, middle keys, etc., of the sequences are approximately equal. Hence the purpose of interleave is not always achieved by standard methods.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Key Directed Interleave

The principle of interleave is to bring records from different sequences but with similar keys, to approximately the same part of a disk, so as to save seek time while merging. However, with many types of presequencing, it is not true that first keys, last keys, middle keys, etc., of the sequences are approximately equal. Hence the purpose of interleave is not always achieved by standard methods.

If however, the distribution of keys is approximately known in advance, it would be possible to assign keys to the (logical) cylinders available, and then assign each block to the cylinder of its first key. Blocks from the same sequences would have to be chained together, so that a block should not be written until the first record for the next block had been identified. A whole key needs not necessarily be defined for each cylinder, but only sufficient fields to ensure a reasonably smooth spread of data across the space available.

Within each cylinder, space would be used sequentially, obviating formatting problems. There would be no restriction on sequence lengths.

If there were no space left in a cylinder, a block would be written in the nearest available slot. In order to avoid such overflow occurring too often, it would be desirable to give the file more logical cylinders than strictly necessary.

This method should be particularly appropriate, where an interleave factor equal to the expected number of sequences would otherwise be used.

An alternative merging technique could be supported as follows. While writing the output of the internal sort, sections of sequences lying in the same (logical) cylinder could be chained together. To do this, the address of the first block used for the last sequence will be kept, together with the address of the next available block, for each cylinder. When blocks from a new sequence are written in a cylinder, the address of the last sequences' first block within that cylinder, is added to the first output block, and the stored address is updated. Hence at the completion of the internal sort, each cylinder contains sections of sequences, and the heads of these sections are chained together in the reverse order in which they were produced. It may also be convenient to keep a count of the number of sequences appearing in each cylinder.

If a cylinder should overflow, a section of anothe...