JPH06103127A - Device for managing hash file data and method thereof - Google Patents

Abstract

PURPOSE:To provide the hash file data managing device which can maintain a large quantity of data at a high speed. CONSTITUTION:Plural input data are divided, based on ranges 0-10, 11-20 of a hash value, and stored in plural input files IF1, IF2. From plural input files IF1, IF2, data is inputted to a data base managing device 3 by data input devices 1, 2. A hash file for constituting one logical file is divided physically into plural sub-files SF1, SF2, based on the ranges 0-10, 11-20 of the hash value. Data inputted by plural data input devices 1, 2 are stored independently, and also, in parallel in the corresponding sub-files SF1, SF2 through plural disk controllers 6, 7.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a hash file data management device and a hash file data management method for managing data by a hashing method.

[0002]

2. Description of the Related Art There is a hashing method (randomization method) as a method for quickly searching for an arbitrary record from a plurality of records stored in a database. In the hashing method, a key for identifying a record (record key) is converted into another numerical value by a certain function, and the numerical value is used as a storage address on a storage medium. This function is called a hash function, and the function value is called a hash value.

If the key is k and the hash function is f, the hash value p can be calculated by the following equation.

P = f (k) Obtaining the hash value p from the key k by the hash function f in this way is called hashing (randomization). Each record is stored in the storage address obtained by the hash function, and the storage address of each record is determined using the same hash function at the time of access. Therefore, according to the hashing method, it is possible to quickly search for a record.

When the hash value is obtained by the above equation, the hash value may be the same for a plurality of keys. This is called a collision, and keys having the same hash value are called synonyms. The optimal hash function is selected so as to reduce such collisions.

FIG. 8 is a block diagram showing a conventional hash file data management device. A plurality of records are stored in the input file IF. The data input device 11 is
The records stored in the input file IF are read one by one. The database management device 12 is a data input device 11
Convert the key of the record given by
The record and hash value are given to the disk controller 13. The database management device 12 also instructs the disk controller 13 on the type of processing. The disk controller 13 accesses the hash file 14 based on the hash value, and executes the processing instructed to the hash file 14.

[0007]

Conventionally, in the design of hash files, the logical structure has been the main focus, and no particular consideration has been given to which data storage area to store data having a certain hash value. Therefore, even if one hash file is physically divided into a plurality of sub-files and multiple access is possible by using a plurality of disk controllers, the database management device can appropriately use the plurality of disk controllers for the disk controller. The access cannot be instructed in order, and for example, access is instructed one by one in the order of the hash value of the data key.

Therefore, a specific disk controller is intensively instructed to access the other disk controller, and the other disk controllers are in a state of waiting for access.

As described above, rapid data processing is possible when accessing individual data in the hash file, but high-speed data processing is not achieved when accessing a large amount of data.

An object of the present invention is to provide a hash file data management device and a hash file data management method capable of maintaining a large amount of data at high speed.

[0011]

A hash file data management device according to the present invention comprises a hash file means, a plurality of input means and an access means.

Data is stored in the hash file means by the hashing method. Hash file means
It is physically divided into a plurality of sub-files and constitutes one logical file by a continuous range of hash values of the data to be stored. The plurality of input means are respectively assigned continuous ranges of different hash values, and each input data having a hash value of the assigned range. The access means calculates a hash value of the data input by each of the plurality of input means, and accesses the corresponding subfile based on the calculated hash value. The access means can simultaneously access at least two subfiles. The hash file data management method according to the present invention includes the following steps.

A hash file that constitutes one logical file is physically divided into a plurality of subfiles according to a continuous range of hash values of data to be stored. The data to be input is assigned in advance to a plurality of input means according to a continuous range of hash values. Data assigned respectively by a plurality of input means are simultaneously input. Each hash value of the input data is calculated, and the corresponding subfiles are simultaneously accessed based on the calculated hash value.

[0014]

In the hash file data management device and the hash file data management method according to the present invention,
The hash files that make up one logical file are
The data to be stored is physically divided into a plurality of subfiles according to the range of hash values, and the data to be input is assigned to a plurality of input means according to the range of hash values, and is input at the same time. Thereby,
Concentration of simultaneous access to a specific subfile is reduced, and input processing is performed in parallel.

Therefore, the processing time is shortened when a large amount of data is collectively maintained. As a result, a large amount of data can be maintained at high speed without impairing the quick data search function.

[0016]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of a hash file data management device according to an embodiment of the present invention. This hash file data management device includes data input devices 1 and 2, a database management device 3, a hashing device 4, a related table 5, disk controllers 6 and 7, and a hash file 8. Hash file 8
Is physically divided into two subfiles SF1 and SF2. The two subfiles SF1 and SF2 form one logical file.

The data input device 1 reads data from the input file IF1 and gives it to the database management device 3. The data input device 2 reads data from the input file IF2 and gives it to the database management device 3.
The input file IF1 stores a plurality of records having hash values “0” to “10”, and the input file IF2
Stores a plurality of records having hash values “11” to “20”.

The hashing device 4 is a data input device 1,
The key of each record input by 2 is converted into a hashing value by a predetermined hashing method (hashing function).

The relation table 5 shows the correspondence between the range of hash values and subfiles. FIG. 2 shows an example of the relation table 5. In the relation table of FIG. 2, hash values “0” to “10” are assigned to the subfile SF1, and hash values “11” to “20” are assigned to the subfile SF.
It is assigned to 2.

The database management device 3 refers to the relational table 5 and sets each of the records given by the data input devices 1 and 2 and the hash value converted by the relational table 5 to one of the disk controllers 6 and 7. Give to.

The disk controllers 6 and 7 respectively access the subfiles SF1 and SF2 in the hash file 8 based on the record given from the database management device 3 and the corresponding hash value.

The database management device 3 and the hashing device 4 can simultaneously process the records given from the data input devices 1 and 2. Therefore, the disk controllers 6 and 7 can also access the subfiles SF1 and SF2 independently and in parallel.

Next, the operation of the hash file data management device of FIG. 1 will be described with reference to the flowchart of FIG.

FIG. 4 shows an example of the input files IF1 and IF2. A key for each of the input files IF1 and IF2,
Eight records including data and processing classification are stored. Here, the processing division “1” represents addition and the processing division “2” represents change.

Here, it is assumed that the data input devices 1 and 2 read the input files IF1 and IF2 shown in FIG.

First, the data input device 1 reads the first record having the key "5-A" from the input file IF (step S11). The database management device 3 is
The record is stored and given to the hashing device 4. The hashing device 4 obtains the hash value "5" from the key "5-A" by a predetermined hashing method (step S12).

The database management device 3 refers to the relational table 5 and selects the subfile SF as the file to be processed.
1 is selected (step S13). Further, the database management device 3 obtains the address of the data storage area in the subfile SF1 based on the hash value “5”.
Then, the type of processing is determined from the processing classification of the record. In this case, since the processing classification is "1", the record excluding the processing classification is given to the disk controller 6 and the record addition processing is instructed.

As a result, the disk controller 6 accesses the sub-file SF1 (step S14) and performs record addition processing (step S15). As a result, as shown in FIG. 5, the key "5" is stored in the data storage area corresponding to the hash value "5" in the subfile SF1.
A record with -A "is added.

On the other hand, the data input device 2 reads the first record having the key "14-A" from the input file IF2 (step S21). Database management device 3
Stores the record and gives it to the hashing device 4. The hashing device 4 uses the predetermined hashing method to change the hash value “14” from the key “14-A”.
Is calculated (step S22).

The database management device 3 refers to the related table 5 and selects the subfile SF as the processing target file.
2 is selected (step S23). Further, the database management device 3 obtains the address of the data storage area in the subfile SF2 based on the hash value “14”. Then, the type of processing is determined based on the processing classification of the record. In this case, since the processing classification is “2”, the record excluding the processing classification is given to the disk controller 7 and the record changing processing is instructed.

As a result, the disk controller 7 accesses the sub-file SF2 (step S24) and performs a record changing process (step S25). As a result, as shown in FIG. 5, the record of the data storage area corresponding to the hash value “14” in the subfile SF2 is replaced with the record having the key “14-A”.

The processing of steps S11 to S15 and the processing of steps S21 to S25 are performed independently and in parallel. Therefore, the subfiles SF1 and SF2 can be accessed simultaneously.

Similarly, the sub file SF1 is processed based on the second to eighth records in the input file IF1, and the sub file SF1 is processed based on the second to eighth records in the input file IF2. The process is performed on the file SF2. As a result, as shown in FIG. 5, the contents of the subfiles SF1 and SF2 in the hash file 8 are updated.

In the hash file data management apparatus of FIG. 1, since the sub files SF1 and SF2 can be accessed independently and in parallel, the hash file 8
It becomes possible to perform maintenance of a large amount of data in a short time.

FIG. 6 shows a range of hash values divided into input files IF1 and IF2 and subfiles SF1 and SF2.
It is a block diagram which shows operation | movement of a hash file data management apparatus when the range of the hash value divided into 2 differs.

A hash value "0" is stored in the input file IF1.
~ A plurality of records having "1010" are stored, and hash values "1011" to "20" are stored in the input file IF2.
A plurality of records having "00" are stored.

The database management device 3 basically has
The data supplied from the data input device 1 is supplied to the disk controller 6, and the data supplied from the data input device 2 is supplied to the disk controller 7. Thereby,
Normally, the hash value “0” to the sub file SF1
A record having “1010” is stored, and a record having hash values “1011” to “2000” is stored in the subfile SF2.

However, if the range of hash values given from the data input device 1 and the range of hash values of the sub-file SF1 are different, the database management device 3 receives the range of hash values given from the data input device 2 and the sub-file. When the range of the hash value of SF2 is different, a part of the data supplied from the data input device 1 can be supplied to the disk controller 7, or a part of the data supplied from the data input device 2 can be supplied to the disk controller 6. Can also be given to.

In the example of FIG. 6, hash values "0" to "1000" are assigned to the subfile SF1, and hash values "1001" to "2000" are assigned to the subfile SF2. In this case, the database management device 3 gives the data having the hash values “0” to “1000” among the data given from the data input device 1 to the disk controller 6, and makes the hash values “1001” to “101”.
Data having 0 ″ is given to the disk controller 7.

The configuration and operation of the other parts are the same as the configuration and operation of the hash file data management device of FIG.

The hash file data management device shown in FIG. 6 has substantially the same effect as the hash file data management device shown in FIG. This will be described with reference to FIG.

As shown in FIG. 7, the hash file is divided into three sub-files SF1, SF2 and SF3 using the hash values H1 and H2 as division points, and the input data is divided into three sub files SF1 to SF2 using the hash values H1 'and H2'. Group DA
1, DA2, DA3 are assumed to be divided. Here, H1 <H1 ′ and H2 <H2 ′.

Input data of each group DA1, DA2, DA3 are simultaneously input from three data input devices, and
Subfile SF using one disk controller
1, SF2 and SF3, respectively. However, a part of the data HA in the group DA1 is stored in the subfile SF2 like the data in the group DA2. Similarly, a part of the data HB in the group DA2 is stored in the sub-file SF3 like the data in the group DA3.

Therefore, two disk controllers may access one subfile at the same time. In this case, the access speed of the subfiles that are accessed at the same time decreases. However, some data HA, H
Most of the data except B is stored in the corresponding subfiles.

Therefore, even in the above case, the time required to process all the data in the hash file is about 1 / (the number of divisions) as compared with the conventional hash file data management device.

However, if the input data and the hash file are divided within the same hash value range, the data can be stored most efficiently.

Although the input data and the hash file are divided into two in the above embodiment, the input file and the hash file may be divided into three or more parts. In that case, the data in the hash file can be maintained in a shorter time.

[0049]

As described above, according to the present invention, it is possible to reduce concentrated simultaneous access to a specific subfile. Therefore, a large amount of data can be maintained at high speed without impairing the quick data search function.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a hash file data management device according to an embodiment of the present invention.

FIG. 2 is a diagram showing an example of a relation table.

FIG. 3 is a flowchart for explaining the operation of the hash file data management device of FIG.

FIG. 4 is a diagram showing an example of an input file.

FIG. 5 is a diagram showing a state after processing of a hash file.

FIG. 6 is a block diagram showing a configuration of a hash file data management device according to another embodiment of the present invention.

FIG. 7 is a diagram for explaining the effect of the hash file data management device of FIG.

FIG. 8 is a block diagram showing a configuration of a conventional hash file data management device.

[Explanation of symbols]

 1, 2 Data Input Device 3 Database Management Device 4 Hashing Device 5 Related Table 6, 7 Disk Controller 8 Hash File IF1, IF2 Input File SF1, SF2 Subfile In the drawings, the same reference numerals indicate the same or corresponding parts.

Claims (2)

[Claims] 1. Data is stored by the hashing method,
Hash file means that is physically divided into a plurality of sub-files and constitutes one logical file by a continuous range of hash values of data to be stored, and continuous ranges of different hash values are allocated and allocated. A plurality of input means for respectively inputting data having hash values in a range, and a hash value of the data input by each of the plurality of input means, and a corresponding subfile based on the calculated hash value A hash file data management device, wherein the access means is capable of simultaneously accessing at least two subfiles. 2. A hash file that constitutes one logical file is physically divided into a plurality of subfiles according to a continuous range of hash values of data to be stored, and the data to be input is divided into hash values. Assigned to a plurality of input means in advance by a continuous range, simultaneously input the data assigned respectively by the plurality of input means, calculate hash values of the input data, and respond based on the calculated hash values Hash file data management method to access sub files simultaneously.