Browse Prior Art Database

Implicit Table Look Up Access Method

IP.com Disclosure Number: IPCOM000076196D
Original Publication Date: 1972-Jan-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 46K

Publishing Venue

IBM

Related People

Cooper, DW: AUTHOR

Abstract

This algorithm provides the mapping function from record name space to the more restricted record location space. In an immediate access storage with direct access storage environment, it is designed to reduce the number of accesses required to locate a record and to conserve storage space required for indices. Unlike the "hash" methods utilizing random-number generation, this algorithm does not result in redundant physical record addresses. Storage Requirements.

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

Page 1 of 2

Implicit Table Look Up Access Method

This algorithm provides the mapping function from record name space to the more restricted record location space. In an immediate access storage with direct access storage environment, it is designed to reduce the number of accesses required to locate a record and to conserve storage space required for indices. Unlike the "hash" methods utilizing random-number generation, this algorithm does not result in redundant physical record addresses. Storage Requirements.

The simplest application of the algorithm will require two types of information resident in immediate access storage. 1. Physical Location Address List. This is a list of record locations in direct access storage sequenced on the associated record name, in the order defined by the "Algorithm for Generation of All Subsets of Any Set in a Special Order" (hereafter called implicit order algorithm) where the bit pattern for the record name is a particular subset. See illustration in Fig.
1. 2. Existence String. This string of binary values is developed by tracing out the tree representation of the name space. A tree for names with n bits will have nodes at n levels plus the root node. The root node represents a name with all binary zeros in its bit pattern. An example tree is shown in Fig. 2. For each tree node reached in the trace, binary values are added to a string based on the following rules: a. For the root node, make the first binary string value 1 if a record of that name is in the file; zero otherwise. b. For nodes in levels from n to 3, add three binary values as follows: 1) Make the first bit a "1" if a record of the name associated with this node is in the file; zero otherwise. 2) Make the second bit a 1 if one or more records e...