JPH0727531B2 - File control method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of use] The present invention relates to a file control system adopted in a computer system such as a database system, and in particular,
When storing data as a data record in a data file, store the stored data in the storage unit in the data file that corresponds to the search key value so that subsequent search processing can be performed quickly based on the search key value. File control method.

[Conventional technology]

A conventional file control system of this type is shown in FIG. In the figure, reference numeral 91 is a data file on an external storage medium for storing data as a data record, and is composed of a plurality of storage units D as shown in FIG. 9, and each storage unit D is a data file 91. Have an address that is unique within.

When the storage means 93 receives the data to be stored, all or a part of the data is used as a search key value, and this is passed to the address conversion means 92. In response to this, the address conversion means 92 obtains, for example, the remainder obtained by dividing the search key value by the number of storage units D included in the data file 91 as a hash value,
The storage unit 93 is notified of the address of the storage unit D corresponding to the hash value.

When the storage means 93 receives the address from the address conversion means 92, it stores the present data as a data record in the storage unit D indicated by the address. Usually, a plurality of data records can be stored in one storage unit D, and they are managed by being linked to a control record for each storage unit by a data pointer. Further, when the number of data having the same hash value increases and the storage unit D corresponding to that hash value becomes full, for example, an empty storage unit D corresponding to another hash value is temporarily used for storage. Then, after the overflowed data record is stored in it, a method is taken to establish a link between the storage units D.

[Problems to be solved by the invention]

In the conventional method described above, one storage unit is assigned to each hash value. Therefore, if the search key value selection or the hash value calculation method is not good, the amount of data records for each storage unit becomes uneven, and the following problems occur.

If the number of possible hash values is increased, a large storage unit is required, and if the number of data records to be stored is small, useless free space increases and it becomes difficult to effectively use the data file 91. That is, if the number of hash values is increased and a large number of storage units D are used as shown in FIG. 10 (a), the number of data records stored in each storage unit D is hatched in the same figure. However, as shown in the portion where the data file becomes smaller, the free area in each storage unit D increases and the data file cannot be effectively used.

Conversely, if the number of hash values is reduced in order to effectively use the data file, the number of data records corresponding to the same hash value increases and the probability of overflow increases, and the processing at the time of search locally deteriorates. . That is, as shown in FIG. 10B, if the number of hash values is reduced and the storage unit D is reduced, the free area in each storage unit D is reduced, but the data record corresponding to the same hash value is reduced. The probability that SR will overflow and be stored across multiple storage units will increase, and the speed of the search processing of the data record corresponding to that hash value will decrease.

The purpose of the present invention is to enable effective use of data files,
Another object of the present invention is to provide a file control method that can perform search processing relatively efficiently.

[Means for solving problems]

In order to achieve the above object, the present invention comprises a data file for storing data as a data record on an external storage medium, the data file comprising:
In a system composed of a plurality of storage units each having a unique address in the data file and being managed in two states, in use and unused, a plurality of address storages for storing the addresses of the storage units Address storage means, each address storage area corresponding to a hash value, and a hash value from the search key value of the data, and the search key value from the address storage area corresponding to the calculated hash value. Address conversion means that obtains the address of the storage unit that currently corresponds to, and a part of multiple address storage areas that store the address of the same storage unit by incorporating an unused storage unit as the storage unit that is in use The address set in the address storage area is changed to the address of the built-in storage unit, and the changed address storage area Storage unit dividing means for transferring the corresponding data record from the original storage unit to the built-in storage unit; and a search key by the address conversion means using a search key value of data when searching data from the data file. Searching means for finding a storage unit corresponding to a value and finding a data record having a matching search key value from the found storage unit; and the address converting means using the search key value of the data when storing data in the data file. The storage unit corresponding to the search key value is obtained by the above, and if the obtained storage unit has a free area in which the data can be stored as a data record, the data is stored as a data record in the storage unit and there is no free area. In this case, the storage unit dividing means is activated to divide the storage unit having no free space to secure a free space. After that, a storage unit for storing the data as a data record in a storage unit corresponding to the search key value of the data is provided.

[Action]

The operation of the present invention will be described with reference to the drawings showing a simplified example for easy understanding.

Now, as shown in FIG. 1 (a), two address storage areas (Ai, Aj (Ai is a hash value Hi, A
j corresponds to the hash value Hj)
It is assumed that the address di of is stored. The data record group RHi, RHj whose address storage area corresponding to the hash value obtained by the address conversion means by the search key value of the data to be searched is Ai, Aj is the first as long as the storage unit Di has a free area. It is stored in the storage unit Di as shown in FIG.

If data to be stored newly is generated and the address storage area corresponding to the hash value obtained by the address conversion means by the search key value is, for example, Ai and there is not enough free area in the storage unit Di, the storage unit The dividing means is activated. When the storage unit dividing means is started, as shown in FIG. 1B, one unused storage unit is in use.
Built in as Dj, one of address storage areas Ai and Aj, eg A
The address di set in j is the address d of the storage unit Dj
The data record corresponding to the changed address storage area Aj, that is, the data record having the hash value Hj (the data record included in the data record group RHj) is transferred to the storage unit Dj. This allows storage unit D
Since the vacant areas are generated in i and Dj, the data record R of the current data is stored in the corresponding storage unit (Di in this case).

〔Example〕

 Next, embodiments of the present invention will be described with reference to the drawings.

Referring to FIG. 2, an embodiment of a file control system to which the present invention is applied is a data file 1, an address storage device 2, an address converting means 3, a storage unit dividing means 4,
The storage unit 5 and the search unit 6 are included.

The data file 1 is a file on an external recording medium for storing data as a data record, and is composed of a plurality of storage units D1, D2, etc. as shown in FIG. 3, and each storage unit D1, D2, etc. It has unique addresses d1, d2, etc. in the data file 1. Each storage unit D1, D2, etc. is managed in two states, in use and unused, the storage unit in use is managed as a used area U, and the unused storage unit is managed as an unused area NU.

The address storage device 2 is composed of a plurality of address storage areas A1 to Am for storing addresses of storage units, as shown in FIG. 4, for example. The total number m of the address storage areas A1 to Am is determined according to the number of hash values to be adopted. The sequential number from the beginning of the address storage device 2 of each address storage area A1 to Am indicates the hash value corresponding to that address storage area.

When the search key value K is notified from the storage unit 5 or the search unit 6, the address conversion unit 3 sets the remainder Q obtained by dividing K by the number m of the address storage areas as a hash value, and the address corresponding to this hash value. This is means for notifying the storage means 5 or the search means 6 of the request source of the address stored in the storage area. Note that the hash value calculation method is not limited to the above, and various other methods can be adopted. FIG. 5 shows an example of processing of the address conversion means 3.

When the storage unit dividing means 4 is activated from the storage means 5,
This is a means for acquiring a new storage unit in use, updating the address storage device 2, dividing the data record stored in the corresponding storage unit in the data file 1, and the like. An example of the processing is shown in FIG.

When the storage unit 5 is notified of the data to be stored from the outside, the storage unit 5 notifies the address conversion unit 3 of the search key value of the data and returns the address of the storage unit, and the storage unit indicated by the address has an empty area. If there is a free space, the data to be stored is stored in the storage unit, and if there is no free space, the data record is stored in the free space of the storage unit generated by activating the storage unit dividing means 4. An example of the processing is shown in FIG.

When the search unit 6 receives a reference or update request specifying a search key value from the outside, the search unit 6 notifies the address conversion unit 3 of the search key value and has the address of the storage unit returned, and the storage unit indicated by the address. By searching inside, the data record with the search key value is acquired, the data of the acquired data record is returned to the request source at the time of reference request, and the data record is updated with the requested value at the time of update request. Then, the data is stored again in the original position in the data file.

Next, the operation of this embodiment configured as described above will be described.

In the initial state where no data record is stored in the data file 1, various methods can be adopted as to which address of each address storage area A1 to Am of the address storage device 2 is stored. . For example, in an extreme case, only one storage unit D1 in use is reserved, and the address of that storage unit D1 is stored in all the address storage areas A1 to Am.
d1 can be stored, or two storage units D1 and D2 in use are reserved, and the address storage area A1 to Am is divided into two, and the address of the storage unit D1 is stored in all address storage areas on one side. Storage unit of d1 in all address storage areas on the other side
It is also possible to store the address d2 of D2 respectively.
Further, it is also possible to secure the number of storage units in use that is half the number m of the address storage areas and set the same address in two address storage areas. In short, how many storage units are in use in the initial state,
It is determined depending on how much an address storage area having the same address value is prepared from the beginning.

Now, with the initial address set in the address storage device 2 (hence, some storage units are secured as in use), the storage means 5 is notified of the data to be stored from the outside. Then, as shown in FIG. 7, the storage means 5 first notifies the search key value of the data to be stored this time and activates the address conversion means 3. (S21).

As shown in FIG. 5, the activated address conversion means 3 divides the notified search key value by the number m of the address storage areas A1 to Am, and the remainder is the hash value corresponding to the search key value, that is, the address. The storage area number is set (S1), the address is taken out from the address storage area, and the storage means 5 is notified (S2).

The storage means 5 that has received the return address checks whether or not there is a sufficient free area for storing the current data in the storage unit in the data file 1 pointed to by the address (S22). If it exists (YES in S23), the data of this time is stored as a data record in the storage unit (S25), and the process ends.

On the contrary, when there is no free area in the storage unit (NO in S23), the address of the storage unit is notified and the storage unit dividing means 4 is activated (S24).

As shown in FIG. 6, the activated storage unit dividing means 4 first incorporates one storage unit from the unused area NU into the use area U (S11), and the same address as the address notified from the storage means 5 is set. The storage incorporated in the used area U in step S11 in some of the plurality of address storage areas of the stored address storage device 2 (how many address storage areas are arbitrary) The address of the unit is stored (S12). Then, the data record having the search key value (that is, the hash value) corresponding to the address storage area in which the address is re-stored is searched from the original storage unit, and they are transferred to the built-in storage unit (S1
3). Then, the control is returned to the storage means 5.

When the storage unit 5 returns the control from the storage unit dividing unit 4, the storing unit 5 starts the process again from step S21, and the address converting unit 3 notifies the address corresponding to the current search key value again (this notification address). May be different from the same as the last time). Then, when the address is returned, there are free areas at this time, so steps S22, S2
After step 3, the process proceeds to step S25, the data record of this time is stored in the corresponding storage unit, and the process ends.

A large number of data records are stored in the data file 1 by repeating the above processing. In addition,
When the number of address storage areas for storing the addresses notified from the storage means 5 becomes one, for example, the storage unit division means 4 notifies the storage means 5 that the division is not possible, and the storage means 5 overflows as in the conventional case. Although the accompanying processing is performed, in the present invention, by appropriately increasing the number m of address storage areas, the probability that such a situation will occur becomes sufficiently small.

When the search means 6 receives a search request specifying a search key value from the outside, the search means 6 notifies the address conversion means 3 of the search key value. The address conversion means 3 is the fifth
Since the address of the storage unit corresponding to the search key value is returned by the process shown in the figure, the search means 6 has the search key value of this time by searching the storage unit in the data file 1 pointed to by the address. Search data records. Then, the processing corresponding to the reference and update is performed.

〔The invention's effect〕

As described above, in the present invention, the hash value obtained by the address conversion means only corresponds to the address storage area in the address storage device, and does not have to correspond one-to-one with the storage unit. Therefore, when the number of data records is small, the addresses of the same storage unit can be stored in a plurality of address storage areas, that is, the data records having different hash values can be stored in the same storage unit. The number of uses can be reduced.

Also, when a certain storage unit runs out of free space and a new data record cannot be stored, a new address is added to a part of the address storage areas in which the addresses of the storage unit are set. The address of the storage unit installed during use is set, and the data record corresponding to the address storage area whose address has been changed is transferred to the newly secured storage unit, and an empty area for storage is created. . In other words, the number of storage units in use is dynamically controlled according to the increase in the number of data records to be stored, so that the data file can be effectively used, and the number of address storage areas, that is, the hash value By increasing the number that can be taken, it is possible to avoid the situation of having to search across a plurality of storage units and improve the efficiency of the search processing.

[Brief description of drawings]

 FIG. 1 is an explanatory diagram of the operation of the present invention, FIG. 2 is a configuration diagram of an embodiment of the present invention, FIG. 3 is a diagram showing a configuration example of a data file 1, and FIG. 4 is a configuration example of an address storage device 2. FIG. 5 is a flow chart of a processing example of the address conversion means 3, FIG. 6 is a flow chart of a processing example of the storage unit dividing means 4, FIG. 7 is a flow chart of a processing example of the storage means 5, and FIG. FIG. 9 is a block diagram of a conventional system, FIG. 9 is a block diagram of a data file 91 of the conventional system, and FIG. 10 is an explanatory diagram of problems of the conventional system. In the figure, 1 ... Data file 2 ... Address storage device 3 ... Address conversion means 4 ... Storage unit dividing means 5 ... Storage means 6 ... Search means Di, Dj ... Storage unit di, di ... Address Ai of storage unit Di, Dj Aj ... address storage area

Claims (1)

[Claims] 1. A data file for storing data as a data record on an external storage medium, wherein the data file has two unique states each having an address unique within the data file. In a system composed of multiple storage units managed by, the storage unit is composed of multiple address storage areas for storing the addresses of the storage units, and each address storage area corresponds to the hash value. An address conversion unit that obtains a hash value from the search key value of the data and obtains the address of the storage unit currently corresponding to the search key value from the address storage area corresponding to the obtained hash value; Incorporate a storage unit as the storage unit in use, and store some addresses in multiple address storage areas that store the address of the same storage unit. Address stored in the storage unit is changed to the address of the built-in storage unit, and the data record corresponding to the changed address storage unit is transferred from the original storage unit to the built-in storage unit. And a storage unit dividing unit for performing a data search from the data file, the storage unit corresponding to the search key value is obtained by the address conversion unit using the search key value of the data, and the search key value is obtained from the obtained storage unit. Searching means for finding a matching data record, and when storing data in the data file, a storage unit corresponding to the search key value is obtained by the address converting means using the search key value of the data, and the storage unit thus obtained is If there is a free area that can store data as a data record, store the data as a data record in the storage unit. If there is no free area, the storage unit dividing means is activated to divide the storage unit having no free area to secure an empty area, and then the data is stored in the storage unit corresponding to the search key value of the data. And a storage means for storing as a data record.