Browse Prior Art Database

Minimum Seek Two Way Merge

IP.com Disclosure Number: IPCOM000077762D
Original Publication Date: 1972-Sep-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Melen, E: AUTHOR

Abstract

The basic idea if that when one of the string parts in core depletes, to read as much as possible from the string at which the disk arm is positioned, rather than going directly to the needed string.

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

Page 1 of 3

Minimum Seek Two Way Merge

The basic idea if that when one of the string parts in core depletes, to read as much as possible from the string at which the disk arm is positioned, rather than going directly to the needed string.

Assume G input buffers are available. G-1 blocks are read from one string, and a seek is made to the other.

Here one block is read, and records are merged until one of the string parts depletes. If the string part that the disk arm is at is depleted, all empty buffers are read into (command-chained) from that string. If the other string is depleted, all but one of the empty input buffers are filled from the string arm is at and a seek is made.

At the point where a seek is made, there will on the average be (G-1.5) blocks from one string in core (one half-filled buffer and one empty reserved for the other string). These records will merge with equally many (on average) from the other string, and core is again filled with (G-1.5) blocks. Thus, the number of blocks passed per seek is on the average (2G-3).

The number of blocks read at the first read after a seek is 1, and each read on the average doubles the number of blocks read together. Thus, the number of reads/seek, N, is found by solving:

(Image Omitted)

Should the same amount of core space been used for a conventional two- way merge, the number of blocks passed per seek & latency would be G/2. Thus for sufficiently large G, seek time is improved by a factor 4.

The number of blocks/latency is (2G-3)/log(2)(2G-2) compared to G/2. For large G this is a degradation (-3...