Browse Prior Art Database

Key File Overflow

IP.com Disclosure Number: IPCOM000049851D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 51K

Publishing Venue

IBM

Related People

Johnson, RD: AUTHOR

Abstract

An arrangement is described for adding new "keys" to the index of "keys" that is maintained for a file of records stored on a magnetic disk at predetermined addressable locations where each recorded record is formatted to include a key field.

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 3

Key File Overflow

An arrangement is described for adding new "keys" to the index of "keys" that is maintained for a file of records stored on a magnetic disk at predetermined addressable locations where each recorded record is formatted to include a key field.

Fig. 1 illustrates the main key index and the format of each key entry for the main index. It is assumed that the key field 9 per se has a length which may vary from a minimum of 1 byte to a maximum of 28 bytes, but is constant for a given file. These keys have been sorted and appear in some predetermined order in the main index, as indicated by address column 15. In addition to the key field 9, the key entry for the main, or primary, index includes a 1-byte flag field 11 and a 3-byte pointer 12 which points to the relative address (RRN) of the record on the disk.

Fig. 2 illustrates the overflow area of the index where new keys are stored sequentially as they are entered. The overflow area may include a field (not shown) which defines the byte length of the over-flow area. A plurality of overflow keys are stored in the overflow area in the sequence in which they occur.

As shown in Fig. 2, each overflow key entry comprises the key field 9' which varies from 1 to 28 bytes, the 1-byte flag field 11', and the 3-byte pointer 12'. In addition, the overflow key entry includes a forward pointer 16 and a backward pointer 17, each of which is 3 bytes in length. Fig. 2 also includes the address column 15' for the overflow area. It should be understood that the index address columns shown in Figs. 1 and 2 are not recorded in the index, but are logical addresses to storage locations of the index where the key entry begins.

When a new key is added to the index, the main index is searched to find the two keys that would bracket the new key. On the assumption that the new key is the first to be added between these two keys, their respective flags are updated and the new key is added to the overflow area. The update to the first bracket key flag is to indicate that the next key is in the overflow area, and the update to the second bracket key flag is to indicate that the previous key is in the overflow area.

For example, as shown in Fig. 1, the main index includes a sequence of keys which, as illustrated, are the numbers K0010, K0020, etc., through K0100. The flag portion of each key will be coded to reflect one of the following situations: 1. None of the below.

2. Next key is in the overflow area.

3. Previous key is in the overflow area.

(Flags can also be defined to indicate such things as the

following or previous key is a duplicate of this one. or

that this key is the last key in the primary area.)

The first new key presented to the system is, for example, K0035, as shown. In searching the main index, the comparison logic will determine that that the

1

Page 2 of 3

point of inserti...