Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Promotion Modification to VSAM Index Strategy

IP.com Disclosure Number: IPCOM000086377D
Original Publication Date: 1976-Aug-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 40K

Publishing Venue

IBM

Related People

Strong, HR: AUTHOR

Abstract

The described method is a modification of the M-tree organization of the VSAM index. It requires only slight modifications in the access, insertion, and deletion programs used by VSAM. In fact, exactly the same access algorithm will work.

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

Page 1 of 2

Promotion Modification to VSAM Index Strategy

The described method is a modification of the M-tree organization of the VSAM index. It requires only slight modifications in the access, insertion, and deletion programs used by VSAM. In fact, exactly the same access algorithm will work.

For purposes of describing the modification, a VSAM index can be viewed as composed of intervals, each of which is composed of a sequence of key-pointer pairs (ordered by the key). An interval is searched for the key next greater than or equal to some given key, and its corresponding pointer is followed to another interval (either in the index or in the data).

In the M-tree organization each of these intervals (including its free space) has the same length m. This length is typically a divisor of page size. Choose any interval and add its immediate descendants and their immediate descendants, etc., to some specific depth. The result forms a tree called an M- tree with that depth. The M-tree is full if all the useable free space is used in each interval.

The modification is applied to the largest depth d of a full M-tree which will fit on a page (m is chosen so space will not be wasted on the page after the modification). The modification does not cross page boundaries and it improves page fault performance only by packing more keys onto a page. It applies to any M-tree of depth less than or equal to d. Promotion.

A single promotion consists of replacing the last key-pointer pair in s...