Browse Prior Art Database

High Record Access, First Fit String Construction Method for a Set of File Blocks on Disk or Drum Storage

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

Publishing Venue

IBM

Related People

Conner, WM: AUTHOR [+2]

Abstract

A typical general purpose sort consists of an input phase, an output phase, and possibly an intermediate phase. The input phase reads the file to be sorted and distributes its data to a workfile in strings of sequenced records. The output phase creates the sorted file by merging the workfile strings to a single string on the output device. If the number of strings distributed by the input phase exceeds the capacity of the output merge, the intermediate phase reduces this number by repetitively merging sets of workfile strings into single workfile strings.

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 68% of the total text.

Page 1 of 2

High Record Access, First Fit String Construction Method for a Set of File Blocks on Disk or Drum Storage

A typical general purpose sort consists of an input phase, an output phase, and possibly an intermediate phase. The input phase reads the file to be sorted and distributes its data to a workfile in strings of sequenced records. The output phase creates the sorted file by merging the workfile strings to a single string on the output device. If the number of strings distributed by the input phase exceeds the capacity of the output merge, the intermediate phase reduces this number by repetitively merging sets of workfile strings into single workfile strings.

The records of the distributed strings are grouped in blocks on the workfile to reduce the access time and storage requirement. In a conventional sort 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 HF 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.

The string S(1) constructed by algorithm HF is the longest string that can be constructed from the blocks in the file, and for i > 1, S(i) is the longest string that can be constructed from the blocks on S(i),...,S(n). Because of this characteristic, the set of strings constructed by algorith...