Browse Prior Art Database

Minimize the Seek Time in Accessing of Data Strings Stored on DASD

IP.com Disclosure Number: IPCOM000088135D
Original Publication Date: 1977-Apr-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 4 page(s) / 84K

Publishing Venue

IBM

Related People

Bayer, R: AUTHOR [+3]

Abstract

The invention relates to a method for minimizing the seek time in the accessing of data normally stored on the tracks of a direct access storage device (DASD), which strings are to be subsequently n-way merged. The method comprises the reiterative step of recording the strings on the DASD tracks in the order of exhaustion of the blocks of the different strings in the next merge pass. The method step includes the steps of: 1) deriving of lower and upper limits of the high key of a merge block, and 2) allocating the placement of the blocks on the tracks of the disk volumes as a function of the key magnitudes and recording gaps.

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

Page 1 of 4

Minimize the Seek Time in Accessing of Data Strings Stored on DASD

The invention relates to a method for minimizing the seek time in the accessing of data normally stored on the tracks of a direct access storage device (DASD), which strings are to be subsequently n-way merged. The method comprises the reiterative step of recording the strings on the DASD tracks in the order of exhaustion of the blocks of the different strings in the next merge pass. The method step includes the steps of: 1) deriving of lower and upper limits of the high key of a merge block, and 2) allocating the placement of the blocks on the tracks of the disk volumes as a function of the key magnitudes and recording gaps.

Each string of blocks to be allocated is formed from r-strings by an r-way merge. Of these r-strings, m different strings are allocated together for placement on cylinders of the same DASD. This allocation is executed by first placing one block of the first string with a known high key and to allocate the placement of m-1 blocks of the remaining strings which are to be later merged. A gap must be reserved for the blocks of each string which may have to be read either before or after the next block. Since the strings are independent, each gap must be separately determined. Since m-1 strings are independent, then the total gap size is (m-1) (r-1).

Preplanning is explained and illustrated for a two-way merge. Assume, string g = ce is currently created and will be merged with string d = ab in the next merge phase, e.g., f = gd.

(Image Omitted)

While blocks in string g are formed, the exact values of high keys of the blocks in g are known. We can also estimate the values of the high keys of the blocks in d. Let the rooted sequence of the exact high values of blocks in c and e be <Theta(1), Theta(2), Theta(3),..., (Theta(1)). This is an upper bound on the high value of keys in d; i.e., the high value of the ith block in d is </= Theta(i).

In preplanning for a 2-way merge, one block of g with known high key has to be preplanned with another block of d whose upper limit of the value of high key is known.

(Image Omitted)

Where d(i) < ! g(k) means the blocks d(i) is read before g(k), and di < ! g(k) means than the lock d(i) may have to be read before or after g(k). When block g(k) is formed, then: a) if Theta(i) <or = Eta(k) We leave a slot (space for one block) for d(i), and then place g(k) in the next slot. b) if Theta(i) > Eta(k) If both d(i) and g(k) can be placed in the same cylinder, then a slot is left for d(i), and g(k) is placed in the same plot. If both cannot be placed in the same cylinder, then a slot is left for d(i) in the current and next cylinder. g(i) is placed in the next cylinde...