Browse Prior Art Database

Variable String Interleave Technique

IP.com Disclosure Number: IPCOM000080848D
Original Publication Date: 1974-Feb-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Melen, E: AUTHOR

Abstract

An interleave technique in connection with strings of variable length should follow an algorithm that can accommodate any distribution of string lengths, efficiently utilize disk space, simplify the formatting problem and give an efficient seek pattern at variable-string lengths.

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

Page 1 of 2

Variable String Interleave Technique

An interleave technique in connection with strings of variable length should follow an algorithm that can accommodate any distribution of string lengths, efficiently utilize disk space, simplify the formatting problem and give an efficient seek pattern at variable-string lengths.

When considering seek times using interleave, only the intercylinder distribution of blocks is significant. Within a cylinder, blocks could be distributed in any fashion without affecting the week pattern.

Each string that goes into an interleave group (group of interleaved strings) is sliced up into parts, such that each part is contained entirely within a cylinder. Simplifying formatting is achieved by writing parts sequentially onto a cylinder as they are produced.

Achieving an efficient seek pattern at varying string lengths within a group is achieved, by making the size of the parts within a cylinder related approximately as the string lengths. This approach requires knowledge of string lengths before they are written, which could be achieved easily for intermediate passes of a merge.

The size of a part is computer in the following fashion:

Given an array S of string lengths within a group, the number of cylinders the group will occupy can be computed. An array C is then created containing the number of free blocks within a cylinder. The parts are then allocated to strings proportional to the remaining string length, one cylinder at a time.

To relieve the input side of the merge from the burden of interleave algorithm computations, the output...