Browse Prior Art Database

Access Method with Good Random and Sequential Capabilities

IP.com Disclosure Number: IPCOM000080211D
Original Publication Date: 1973-Nov-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 54K

Publishing Venue

IBM

Related People

Inselberg, AD: AUTHOR [+3]

Abstract

This is an access method combining the concepts of indexed sequential and direct access methods. A record's key field is separated into two portions. A first portion, consisting of those digits that change infrequently from record-to-record in the file, is used to create an index specifying an area within which the record is to be stored. The remaining portion of the key is used to hash to a specific location within the area designated by the index. The record will be stored in this location.

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

Access Method with Good Random and Sequential Capabilities

This is an access method combining the concepts of indexed sequential and direct access methods. A record's key field is separated into two portions. A first portion, consisting of those digits that change infrequently from record-to-record in the file, is used to create an index specifying an area within which the record is to be stored. The remaining portion of the key is used to hash to a specific location within the area designated by the index. The record will be stored in this location.

Consider a record's key field to be composed of alphanumeric digits or characters C(1) ... C(k), where C(1) is the leading digit.

Assume that in this method, the lowest level index (comparable to the cylinder index in ISAM) points to areas, A, each of which can hold M records. Let C(1) ... C(t) represent the digits varying little. Then those digits will be used for indexing. However, since as few digits should be used as possible so that the index storage area is small, an algorithm must be found to determine t, the number of digits used for indexing. One way to do this is given in the following steps:
Step (i) Order the keys for a file in ascending or descending order. First, take C(1). Go through the ordered file

sequentially. Count the number of keys that must be gone

through before encountering a change in value in this

digit, and determine the maximum of these numbers which

are encounted going through the whole file. Let this

maximum number be n(1).

Step (ii) Repeat process (i) for digits C(2),...,C(k) to obtain n(2),n(3),---,n(k).

Step (iii) C(1) ... C(t) will be used for indexing if n(i) > M for

i = 1,...,t-1 but n(t) </- M where M is the number of

records that can be stored in an area A.

Fig. 1 illustrates the procedure. In this example, n(1) = 5, n(2) = 4, n(3) = 2, n(4) = 2, n(5) = 1, and n(6) =
1. Suppose M = 2. then the digits C(4) C(5) C(6) will be used for indexing and C(4) C(5) C(6) will be used for hashing. One way to accomplish hashing is using the division method as follows: Step (a) The portion of the key to be used for hashing, e.g., C(4) C(5) C(6) in the example above, is divided by M, the

number of storage locations in each area A.

Step (b) The remainder obtained from the division process is used as the storage location within area A. A new

method for creating th...