Browse Prior Art Database

Double Transformation for Index Block Entries

IP.com Disclosure Number: IPCOM000075898D
Original Publication Date: 1971-Dec-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Perry, OR: AUTHOR

Abstract

To conserve space, the keys in an index block may be replaced by pseudo-random representations. The double-transformation technique described here resolves synonyms without the cost of retrieving unwanted records. Assume: 1) Two records with keys Ki and Kj are to be indexed in a particular index block. 2) The two records are stored at addresses Ai and Aj. 3) The pseudo-random values ki and kj are related to Ki and Kj. 4) And ki=kj; that is, ki and kj are synonyms.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 91% of the total text.

Page 1 of 1

Double Transformation for Index Block Entries

To conserve space, the keys in an index block may be replaced by pseudo-random representations. The double-transformation technique described here resolves synonyms without the cost of retrieving unwanted records. Assume: 1) Two records with keys Ki and Kj are to be indexed in a

particular index block.

2) The two records are stored at addresses Ai and Aj.

3) The pseudo-random values ki and kj are related to Ki and

Kj.

4) And ki=kj; that is, ki and kj are synonyms.

The user could simply retrieve either record and, if that record proves to be the wrong record, he could retrieve the other record. A better solution is to rerandomize Kj to derive a unique kj, thereby resolving the synonym at the time the index-block entry is being made.

The following steps are required: 1) Designate two unused bits in each address A as flags F and G. 2) Flag Ai by setting F. 3) Flag Aj by setting G. 4) Rerandomize Ki using a different algorithm to derive a new kj.

When records have been indexed in this way, a record with key Kn can be retrieved using the following steps: 1) Use the first randomizing algorithm to derive kn. 2) If address An does not include flag F, then An is the address of the desired record. 3) If An includes flag F, use the second randomizing algorithm to calculate a new value km. 4) If the value km is not in the index block, then An is the address of the desired record. 5) If km is in the index block but the related Am...