Browse Prior Art Database

Reordering the Records of a File

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

Publishing Venue

IBM

Related People

Bennett, BT: AUTHOR [+2]

Abstract

This method is for reordering of a file, whereby the records constituting the file are arranged such that the order of their key values is biased in a sequential direction. The file is thus advantageously preconditioned for being sorted, particularly by a distribution sort technique.

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

Page 1 of 3

Reordering the Records of a File

This method is for reordering of a file, whereby the records constituting the file are arranged such that the order of their key values is biased in a sequential direction. The file is thus advantageously preconditioned for being sorted, particularly by a distribution sort technique.

The method first entails the performing of an internal sort by replacement selection on the file, to provide a plurality of strings of ordered records. As the strings are created, their records are blocked and written out on a direct-access storage device such as a disk. When this file is read, the first block should be read from each string and then the second block from each string, etc., whereby the envisaged reordering will have been accomplished.

A disk consists of a plurality of cylinders, each cylinder consisting of a plurality of tracks. Each of these tracks has to be capable of holding at least one block of records. A point to be noted is that a time penalty is involved when movement is made from one cylinder to another. Now first consider the case in which each track can hold precisely one block.

Let u and v be integers such that uv is less than or equal to the number of tracks per cylinder. The number of tracks per cylinder which are actually used will have the value of uv. The file produced by the replacement selection sort process is written out as follows: the first u block of the first string are written into the first u tracks of the first cylinder. The next u blocks of the first string are written into the first u tracks of the second cylinder, etc., until all of the blocks of the first string have been written out. Then, the first u blocks of the second string are written into tracks u+1, ..., 2u of cylinder 1, etc. This process is continued until the first v strings have been written out. One of these first v strings will be a longest string and will be spread over some number of cylinders, say the quantity
w. The next v strings are written out in an entirely analogous fashion starting at cylinder w+1. In this manner, all the records are written out onto the disk.

According to the method d...