Browse Prior Art Database

Index Block With Randomized Keys

IP.com Disclosure Number: IPCOM000075281D
Original Publication Date: 1971-Aug-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Related People

Perry, OR: AUTHOR

Abstract

The index block forms described use randomized keys to provide compactness and allow rapid searching. A variation provides logically sequential retrieval of records. The forms are useful only for the lowest level of an index. Upper levels using conventional forms are assumed. Basic Block Form.

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

Page 1 of 3

Index Block With Randomized Keys

The index block forms described use randomized keys to provide compactness and allow rapid searching. A variation provides logically sequential retrieval of records. The forms are useful only for the lowest level of an index. Upper levels using conventional forms are assumed. Basic Block Form.

Assume that a key transformation T produces random numbers k from record keys K as follows: T(K(i))=k(i)

T can be any good randomizing transformation such as divide/ remainder using a prime number. Assuming the record Ri is stored at auxiliary storage address Ai, an index block could be formatted as seen in FIG. 1.

To determine the location of a record R(i), calculate k(i) and search the appropriate index block for that value.

The entries within a block can be in order by:
. K(i) to optimize logical sequential processes
. k(i) to optimize index block search time
. A(i) to optimize direct-access device time by semi-physical

sequential processing

Extended Block Form

It is possible to provide both binary search of the k's and logical sequential retrieval of records by using the block form seen in FIG. 2. where: A(1) is the address of the record with key K(i) K(i) K(i+1) i=1,2,...,127

k(j) k(j+1) j=1,2,...,127

and Lj)=i implies that T (ki)=k(j)

K, k, and A are defined as before. L(j) is a 1-byte value.

To retrieve records in sequence of ascending keys, simply begin with A(1) and proceed in order through A(128). To retrieve an individual record at random, perform the following steps:
1) Transform the record key to a k-value.
2) Perform binary search for the matching value of k in the

index block. Assume the matching value is k(j).
3) Assuming L(j)=i, then A(i) is the address of the desired

record.

Inserting Records at Random.

To insert a record at random, a binary search of the already stored records could be conducted. For 128 keys, this search would require that 7 or 8 actual records be retrieved so that their keys could be inspected. A technique that reduces the number of records that must be retrieve...