JPH01209526A - Record access system - Google Patents

Abstract

PURPOSE:To improve the storing/retrieving efficiency of records and to improve the availability of a file base by declearing the allocation of the storing blocks for each range of the record length and the number of records per block. CONSTITUTION:The block range used for each range of the record length is decleared as a definition parameter 1. A block section defining part 10 produces a block control table 2 which controls the range of blocks where the blocks are stored for each range of the length of the record to be stored in response to the input of the parameter 1. Then a randomizing process part 20 refers to the table 2 when the records are retrieved and stored and calculates the block number of a desired record. Thus an optimum block can be allocated for each range of the record length at the storage and the retrieval using a hashing system of records having different record lengths. As a result, the storing/retrieving efficiency of records is improved together with improvement of a file space.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a record access method using hashing, and more particularly to a record access method that enables uniform access efficiency in random access of records of the same type with varying record lengths. .

[Conventional technology]

Conventionally, in this type of record access method, when a key value is given and the block number on the secondary storage device in which the record containing the key value is stored is obtained, an index is generally used to identify the key value and record. A method of associating the key value with the block number stored in the key value, and a method of using hashing to calculate the block number in which the record corresponding to the key value is stored (hereinafter referred to as the hashing method) have been adopted.

The hashing method is, for example, assuming that there are n (positive integer) blocks in a file that stores records, and they are represented by addresses from 0 to n-1. In this method, the key value is randomized to a value from n-1 to determine a block corresponding to the key value.

FIG. 5 is a diagram showing an example of record storage processing using the hashing method. Referring to FIG. 5, by randomization processing, records with key value "ABCCD" and records with key value "KKKDB" are placed in block 1, records with key value "5SIDK" are placed in block 2, and records with key value "DKLLN" are placed in block 1. and “ABABB”
It is shown that the records with the following values are respectively stored in block 3.

In the hashing method, as shown in FIG. 5, randomization of 2 to different key values kl and 2 may result in the same block number. Records allocated to the same block in this way are generally called synonyms. The individual key values specified in the randomization process are used to search for the desired record among synonyms assigned to the same block.

When a large number of records (synonyms) with different key values are assigned to the same block, it becomes impossible to store all the records in one block, and another block with free space must be searched for and stored. It will stop happening. However, a feature of record access using the hashing method is that a target record can be accessed by reading a block only once, and consideration must be given to avoid reading blocks more than once. For this purpose, a method is generally used in which a spare space is secured in each block.

For example, a file with a block length of 1000 bytes has 10
In order to store 1000 0-byte records, a minimum of 100 blocks of storage space needs to be secured, but it cannot be expected that 10 records will be evenly allocated to blocks 1 to 100 in the randomization process.
When the records in this example are processed by normal randomization processing, blocks to which only 3 to 5 records are allocated and blocks to which 13 to 15 records are allocated occur. .

FIG. 6 is a diagram showing an example of a block allocation situation in normal randomization processing. Referring to Figure 6, when records are allocated evenly to each block, 60 to 70% of the blocks have Nl (positive integer) records, which is the number of records in one block, but nothing is stored. It can be seen that there are blocks that are not allocated and blocks that are allocated twice as many records as N1. Therefore,
In order to keep the number of allocated records in a block within the maximum allowable range (within 10 records in this example), measures are generally taken to increase the number of blocks used in the randomization process. In the above example, by doubling the number of allocated blocks to 200 blocks, it becomes effective to suppress the variation in records from 3 to 15 records for 100 blocks to 1 to 8 records.

However, such treatment is effective when the record length of the records stored in a block is constant, but it may be ineffective when the record length is not constant. If all the space is used up, there will be a situation where there is no space for additional records even if the number of records allocated to one block is within the allowable number of records for that block. In the above example, if some of the records stored in a block are 200 bytes in size, if only 200 byte records are allocated to a particular block, only a maximum of 5 records can be stored, and the number of allocated blocks increases. If we do not increase the margin further, synonyms within a block will not fit within the corresponding block.

Figure 7 shows that even when the number of records allocated to each block is uniform in randomization processing of records with different record lengths, there are two
FIG. 4 is a diagram illustrating an example of a case where it is necessary to read more than 1 block. Referring to FIG. 7, as a result of the randomization process, records Rml to Rm6 (indicated by a dotted line 301) are assigned to block m, and records Rn1 to Rm6 are assigned to block m.
wRn6 (indicated by a dotted line 302) is assigned to block n, and records Rol to Ro6 (shown by a dotted line 303) are assigned to block n.
) is assigned to block 0, but
Records Rm 4 to Rm6 assigned to block m
and record Rn6 assigned to block n are stored in separate blocks.

[Problem to be solved by the invention]

In the conventional record access method described above, records with varying record lengths may not be stored in the target block even if a margin is provided to account for bias in normal randomization processing. When performing a search or update, a single read operation may not complete the processing of the target record, resulting in a disadvantage that the efficiency of record storage and retrieval is reduced.

Furthermore, if a margin in the number of blocks is secured by taking into account the variation in record length, there is a drawback that the efficiency of file space usage decreases and the storage cost increases.

In view of the above-mentioned points, an object of the present invention is to enable optimal block allocation for each range of record lengths in storage and retrieval using a hashing method for records with different record lengths, thereby improving the efficiency of record storage and retrieval. The purpose of the present invention is to provide a record access method that can increase file space utilization efficiency at the same time.

[Means to solve the problem]

The record access method of the present invention applies a hashing algorithm to a given key value to randomly access records in a file stored on a secondary storage device, and calculates the block number of the target record. In a record access method determined by calculation, a block partition definition section that creates a block management table for managing the range of blocks to be stored for each record length range of records stored in response to input of definition parameters; and a randomization processing unit that calculates a block number of a target record by referring to the block management table when searching and storing the target record.

[Effect]

In the record access method of the present invention, the block partition definition unit creates a block management table for managing the range of blocks to be stored for each record length range of records stored in response to input of definition parameters, and performs randomization. When searching and storing records, the processing unit refers to the block management table and calculates the block number of the target record.

〔Example〕

Next, the present invention will be explained in detail with reference to the drawings.

FIG. 1 is a functional block diagram showing the configuration of a record access method according to an embodiment of the present invention.

The record access method of this embodiment consists of a definition parameter l that declares the range of blocks used by records stored in a file for each record length range, and a block that creates a block management table 2 by inputting the definition parameter l. It consists of a partition definition section 10 and a randomization processing section 2o that calculates the block number of the target block for the target record by referring to the block number recorded in the block management table 2 when storing and retrieving records. There is.

Referring to FIG. 2, the processing in the randomization processing unit 2° consists of a block management table search step 201, a key value random number generation step 202, a relative block number calculation step 203, and a target block number calculation step 204.

Next, the operation of the record access method of this embodiment configured as described above will be explained. Here, each process of defining a block partition, storing a record, and retrieving a record will be explained in order.

(1) Definition of block partition In order to efficiently perform random access of records with different record lengths, the range of blocks to be used for each record length range is declared as definition parameter 1. The block partition definition unit 1o The block management table 2 is created by inputting the definition parameter l specifying the length range and the storage block range.

FIG. 3 is a diagram showing an example of record processing requirements used in the following description of the operation. Referring to Figure 3, in this example, a record with a record length of 100 bytes is
It is necessary to store o records, 5000 records of 200 bytes, and 500 records of 400 bytes. Therefore, if you reserve 100% spare space to avoid overflow when storing each record, a 100-byte record will have 100*5000*2=IM bytes (
1000 blocks of IK bytes), and a 200 byte record requires 200*5000*
2 = 2M bytes (same < 2000) of space is required, and a 400 byte record requires 400*500
*2 = 400 bytes (also 400) of space is required.

Figure 4 (al and (bl are the definition parameters 1 defined based on the record processing requirements shown in Figure 3 and the block management table 2 created based on them)
It is a figure which each shows an example. Referring to FIG. 4 (ta), the maximum record length and its block range (starting block number) are specified, and 100.200 and 4000 are specified as the maximum record length. Note that in this example, the expression that should be 201 bytes or more is 40
00 bytes, and it is assumed that there are no records longer than 4000 bytes.

The block partition definition unit IO receives the definition parameter 1 and creates a block management table 2 as shown in FIG. 4(b).
Create.

(■) Randomization Processing The randomization processing unit 20 is called to determine a target block of records when storing records or searching for stored records.

(11 Record Storage Process In the record storage process, the record length of the record to be stored is calculated and passed to the randomization processing unit 20 together with the key value.

The randomization processing unit 20 refers to the block management table 2 and determines the starting block number A and the number of blocks B from the entry in the block management table 2 that corresponds to the record length of the specified record (step 201).
, then performs random number generation processing for key values (step 202
), the remainder R of dividing the resulting random value by the number of blocks B is calculated as a relative block number (step 203).
Then, the value obtained by adding the starting block number A for the corresponding record length obtained from the block management table 2 and the remainder R calculated in step 203 is used as the block number of the target block containing the record to be stored. (step 204), and returns this block number to the storage process.

(2) Record search processing In record search processing, the key value and record length of the record to be searched are given, and the randomization processing unit 2
The process of calling 0 in the randomization processing unit 20 is performed in the same way as in the case of storage processing, and after the processing is completed, the randomization processing unit 20 returns the block number of the target block containing the search target record to the search processing.

〔Effect of the invention〕

As explained above, the present invention enables storage processing using the hashing method for records with different record lengths by making it possible to allocate storage blocks for each record length range and declare record loss per block. This makes it possible to optimally allocate blocks for each record length range, thereby increasing the efficiency of record storage and retrieval, as well as the efficiency of file space usage.

[Brief explanation of the drawing]

FIG. 1 is a functional block diagram showing the configuration of a record access method according to an embodiment of the present invention, FIG. 2 is a flowchart showing an overview of the processing in the randomization processing section in FIG. 1, and FIG. Figure 4 shows an example of the record processing requirements used in Figure 4. fal and (bl are examples of the definition parameters and block management table in Figure 1, respectively. Figure 5 is an overview of the processing of the hashing method. 6 is a diagram showing an example of the storage distribution of records in the hashing method. FIG. 7 is a diagram showing an example of block usage that occurs when hashing records with different record lengths. In, 1...definition parameter, 2...block management table, IO...block partition definition section, 20...randomization processing section.

Claims (1)

[Claims] To randomly access records in a file stored on a secondary storage device, a hashing algorithm is applied to a given key value to calculate the block number of the target record. The record access method includes a block partition definition section that creates a block management table for managing the range of blocks to be stored for each record length range of records stored in response to the input of definition parameters, and a block partition definition section that handles record search and A record access method comprising: a randomization processing unit that calculates a block number of a target record by referring to the block management table during storage;