Browse Prior Art Database

Space Reclamation Via an Indexed Structure

IP.com Disclosure Number: IPCOM000075441D
Original Publication Date: 1971-Sep-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 4 page(s) / 54K

Publishing Venue

IBM

Related People

Hileman, RK: AUTHOR

Abstract

The disclosed reclamation technique, useful for any access method which does not assume logically sequential records to be physically contiguous, allows the reuse of previously used but available space within a data set. It reduces the overall space requirements for data sets with significant add and delete activity, and maintains awareness of, and a way to use, available space. Awareness of deleted space sizes is maintained to reduce fragmentation caused by partial use of an available space -- useful for variable-length record data sets only. Awareness of the physical location of available spaces is also maintained to allow assigning of space as close to the desired physical location as possible--useful in reducing seek time incurred when operating in a sequential manner.

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

Page 1 of 4

Space Reclamation Via an Indexed Structure

The disclosed reclamation technique, useful for any access method which does not assume logically sequential records to be physically contiguous, allows the reuse of previously used but available space within a data set. It reduces the overall space requirements for data sets with significant add and delete activity, and maintains awareness of, and a way to use, available space. Awareness of deleted space sizes is maintained to reduce fragmentation caused by partial use of an available space -- useful for variable-length record data sets only. Awareness of the physical location of available spaces is also maintained to allow assigning of space as close to the desired physical location as possible-- useful in reducing seek time incurred when operating in a sequential manner.

To point to a specific reclaimed space, using a physical address on a disk storage device, the following address components could be used: 1) DD - byte displacement of start of logical record within a physical block 2) R - physical block within the track 3) HH - head address (track) within cylinder 4) CC - cylinder address within volume 5) AA - device address.

Thus, to point to a reclaimed space, the address would be: AACCHHRDD. This assumes the system is aware that the proper volume was mounted on the addressed device.

To point to the same space using a logical address, the following components could be used: 1) DD - byte displacement of start of logical record within physical block 2) BBB - block address from start of data set 3) SS - code for data set name.

The pointer in this relative block example would become: SSBBBDD. This example assumes fixed block sizes and also assumes the system can decode this address to whatever physical address is needed. This addressing mechanism limits each data set to approximately 16,000,000 blocks.

Pointers used to point to the same space using a relative byte address, with fixed physical blocks and spanned records, would be: 1) DDDD - byte displacement from start of data set 2) SS - code for data set name.

This pointer would become SSDDDD. The remainder of this description assumes the use of relative byte addresses, but the method is equally applicable to other addressing conventions similar to those defined above.

A reclaimed space index is created. At the lowest level, a key and its associated pointer exist for each useful (larger than some small arbitrary size) available space, not including new or unused data set space. In this index, all keys are logically and physically contiguous.

Space for record insertion close to the desired physical location and reduction of possible reclaimed space fragmentation in the data set can be achieved as follows. The key portion of the key-pointer pair is a composite of the following fields: Data set, high-order two bytes of relative byte address (RBA) of space pointed to and space size. The pointer portion of each key-pointer pair is

1

Page 2...