Browse Prior Art Database

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

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

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 HC which is the figure, eliminates this unnecessary restriction, and assigns each work-file 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 100% of the total text.

Page 1 of 2

High Record Access, Closest Fit 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 HC which is the figure, eliminates this unnecessary restriction, and assigns each work-file block to one of strings S(1),S(2),...,S(n) without regard to the prior distribution order.

For any file, the number of strings created by algorithm HG is a theoretical minimum; therefore, the total number of intermediate merges required during the sort is minimized.

Algorithm HC operates on an index I which contains the high key, low key, and location of each workfile block. In the figure, MINHI(I) is the current entry in I with the lowest high 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. The closest fit string for an entry B is the string which, among those strings that do not have a peer for B, contains the entry with the highest key.

1

Page 2 of 2

2

[This page contains 2 pictures or other non-text objects]