Browse Prior Art Database

Low Record Access String Construction Method for a Set of File Blocks on Disk or Drum Storage

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

Publishing Venue

IBM

Related People

Conner, WM: AUTHOR [+2]

Abstract

The intermediate and output phases of a sort program merge strings of ordered records, which are grouped in blocks on the sort's workfile to decrease the access time and storage requirement. In a conventional merge the block sequence of any string merged is identical to the block sequence of a previously distributed string, even though this restriction is unnecessary for disk and drum workfiles. Algorithm L which is the figure eliminates this unnecessary restriction, and assigns each workfile block to one of strings S(1),S(2),...,S(n) without regard to the prior distribution order.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 74% of the total text.

Page 1 of 2

Low Record Access String Construction Method for a Set of File Blocks on Disk or Drum Storage

The intermediate and output phases of a sort program merge strings of ordered records, which are grouped in blocks on the sort's workfile to decrease the access time and storage requirement. In a conventional merge the block sequence of any string merged is identical to the block sequence of a previously distributed string, even though this restriction is unnecessary for disk and drum workfiles. Algorithm L which is the figure eliminates this unnecessary restriction, and assigns each workfile block to one of strings S(1),S(2),...,S(n) without regard to the prior distribution order.

Algorithm L operates on an index I which contains the high key, low key and location of each workfile block. In the figure, MINLO(I) is the current entry in I with the lowest key. Two entries are said to be peers if the high-key value of one lies between the low and high-key values of the other.

For any file, the number of strings created by algorithm L is a theoretical minimum; therefore, the number of merge operations required by the intermediate phase of a conventional sort algorithm can be minimized. Furthermore, a slight modification of the string selection process in the step marked by an asterisk in the figure will cause algorithm L to create strings well- suited for a nonconventional sort algorithm.

A block is termed exempt if it does not belong to any set of m mutually overlapping blo...