JPS62182849A - Data control system - Google Patents

Abstract

PURPOSE:To attain the uniform storage of data by increasing the number of pages in response to the increase of overflow and dividing only the data on the overflow page into plural pages. CONSTITUTION:In case data are stored, the data are first transferred to a data value memory part 11 from outside and only the key part in the data value is used by a hash calculation part 12 of production of the real number value that is printed to '1' from proper '0'. An optional hash function or the one that has high possibility to be printed to the uniform distribution in terms of the data distribution state is selected. That is, a function F(X)=X /(conceivable maximum value of X) is available. Then a store address calculating part 15 calculates the store addresses from the obtained hash function and the divided rows in a divided row memory part 13. Then the data in an overflow page if obtained is divided into plural pages by the key hash function value of each data.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a data management method in a computer system having files, and in particular, data access by a hash that calculates a data storage address using a part of the data as a key. Regarding the data management method used when carrying out.

1' Prior Art Conventionally, in a hash access method using files, keys and data other than keys are stored together with other data in units of data storage areas called pages. At this time, a special calculation formula called a hash function has been used to determine the storage address indicating the data storage area from the key value.

However, with conventional data management methods, when the storage space in a page decreases and data can no longer be stored in this page, when a so-called overflow occurs, the overflow page cannot store data in the overflow page. It was stored in a separate storage area via .

[Problems to be solved by the invention: 1. In the conventional data management method described above, data storage efficiency deteriorates due to biased data distribution, and the number of page accesses increases when accessing overflow data. There was a point.

1. Means for Solving the Problems] The method of the present invention is an information processing method that uses a part of data as a key and performs data access in which the storage address of the data in a file is determined based on the hash function value of the key. In the data management method of the device, divided column data consisting of an address sequence of a data storage area obtained by dividing overflowed data stored in advance during data storage into a plurality of data storage areas and the hash function value. Storage area address determination means for determining the storage area address of Togachi data; and when the storage area determined by the storage area address determination means overflows during data accumulation, the address of the storage area is added to the divided column data. The storage area address determination means determines the storage area address of the data stored in the overflowed storage area and the data to be stored, and controls the storage area address to be stored.

By having the above-mentioned means, the number of pages increases with overflow, and data can be stored uniformly by dividing only the data of overflow pages into a plurality of pages.

In addition, when accessing overflow data, there is no need to access the overflow-compatible storage area as in the past, and access to the file is not required to refer to the split column storage area, so it must be accessed only once. It becomes possible to retrieve the desired data by accessing the .

〔Example〕

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention.

When storing data, data is first transferred from the outside to the data value storage section 1.1. Only a portion of the data value is used by the hash calculator 12 to generate real values that map appropriately from 0 to 1. As the hash function, an arbitrary one or a function that is highly likely to be mapped to a uniform distribution in view of the data distribution situation is selected. For example, F (X) = X/ (maximum possible value of X) can be considered as a function. Using the obtained hash function value and the divided columns in the divided column storage section 13, which will be explained below, a storage address is calculated in the storage address calculation section 15 by the operation shown in FIG. The data access control unit 14 performs processing not shown below. The storage area having the storage address obtained by the storage address calculation unit 15 is retrieved from the data retrieval unit 16, and if there is no overflow, the data is stored in the storage area by the data storage unit 17, and then the data is stored in the storage area by the disk device 18. Write to disc. If the page has overflowed, the in-page data of this page is divided into a plurality of pages according to the hash function value of the key of each data.

In the division, first, the address of the storage area of the overflow page is added to the division column storage unit 13, and then each data is processed according to the flow shown in FIG. 2 to obtain the storage address. Hereafter, as a simple case, 2
Let us consider the time of division. The data set divided into two is stored in the above-mentioned overflow page and a new page acquired from the free space on the disk. The given data to be stored is also stored in one of the two pages according to its hash function value.

When data is retrieved, only a portion of the data is first set in the data value storage section 11 from the outside.

Using the above key value, the address of the storage area is determined by the storage calculation section 12 and the storage address calculation section 15 in the same manner as in the case of L storage. Thereafter, the data storage area having the key value given by the data acquisition section 16 is retrieved from the address obtained above, and the data is set in the data value storage section 11.

The details of the process described below are explained below using an example.

Assume now that the data shown in FIG. 3 is stored in the manner shown in FIG. 11. Assume that a new request is given to store data (15, f>) and that data is set in the data value storage unit 11.The content of the division column is (1,,2). - The hash function value is obtained by the Sosh calculation unit 12. Now, let us assume that 0.2 is found in the calculation. At this time, the next storage address calculation unit 15 performs the following processing.

(Step 1) Setting the initial value Nr)=1. m=1, P
=1. Ne=1.1=0 (Step 2>1=1 (Step 3) Since i>2 is not true, go to Step 4 (Step 4) L, l-1 (Step 5) N l! = 1.- +, so go to step 6.1 (step 6.1) A, =O, so go to step 7, I
a/\ (Status 7.1a) Nff=1, Np=2. m
= 2 (Step 2) i = 2 (Step 3) Since i > 2, go to Step 1 (, Step...) A'-1) L2 = 2 ( Ste Tubu 5) Nj? = Not Lz, so go to Ste-Tsub 6.2 (Step 6.2) Ne > L 2, but Ste-So77.2b'\ (7!, Te-y7”7.2t+) Ne=1.Np= 3(
Step 2 > i = 3 (Step 3) Since i > 2, it ends, P = 1 From this, it was determined that the data storage address is 14, but page 1 is already in an overflow state! No more data can be stored. Therefore, page 1
Divide the data set in page 1 and new page 4
Store in.

At this time, the data to be stored is also stored in an appropriate page (1 or 4) according to flowchart I in FIG. 2 using a new division sequence (1, 2, 1>) according to the hash function value of the key. The state of the file after splitting is
As shown in the figure.

Next, when extracting data in the state shown in Figure 4, suppose the data key value is 120 and its hash function value is 0.9.
Assuming that, the storage address is set as follows in the same manner as the above accumulation.

(Step 1> Setting initial values Np=1.m=1, P=
1. Ne=1.1=0 (Step 2) i=1 (Step 3) Since i>2 is not true, go to Step 4 (Step 4) L+=1 (Step 5) Nj? =L+, so step 6.1
(Step 6.1) Since A+ = O, go to Step 7, Ih (Step 7, Ib) P = 2, N e =
2, N p = 2, m = 2 (Step 2) i = 2 (Step 3) i) - Since it is not 2, go to Step 4 (Step 4) L2 = 2 (Step 5) Ne = L2, so Step 6. 1 (Step 6.1) Since A2 = 0, go to Step 7.1h (Step:tT)”7.1b>P=3.Ne=3.Np
=3, m=3 (Step 2) i-=3 (Step 3) Since i>2, end. P=3 From the obtained storage address 3, data (120, d) matching the key 120 is retrieved by the data retrieval section 6, set in the data value storage section 11, and passed to the outside.

[Effects of the Invention] As described above, the present invention has a method of dynamically dividing data stored in an overflow page and calculating storage addresses using a division column having division page addresses, thereby controlling the distribution of data within a file. This has the advantage that it can be made homogeneous, and the data can be retrieved with just one access, reducing the number of accesses. As a result of experiments and analysis, the average data page storage efficiency was 0.67, making it possible to store data efficiently.

Brief Description of the Drawings FIG. 1 is a block diagram showing an embodiment of the present invention, and FIG. 2 is an operational flowchart 1 of the storage address calculation section of FIG. 1.
Fig. 3 is a diagram showing an example of a data set that is heavily used in the explanation of Fig. 2, and Figs. 4 and 5 are explanatory diagrams showing the file status before and after division in the example using Fig. 3. .

1-5.6.1.6.2.7. la, 7. Ib,
7.2a.

7.2b...Step of flowchart, 11...
Data saturation storage unit, 12... Hash calculation unit, 13...
- Division column storage unit, 14...data access control unit, 1
5...Storage address calculation unit, 16...Data retrieval unit, 1
7... Data storage section, 18... Disk device.

2ffi Mature 3 concave Street address 4th place Science 4 diagram Cow 5 diagram

Claims (1)

[Scope of Claims] In a data management method for an information processing device that performs data access in which a part of data is used as a key and a storage area address of the data in a file is determined based on the hash function value of the key, data storage is determined in advance. The storage area address of the data is determined from the hash function value and divided column data consisting of the address sequence of the data storage area obtained by dividing the overflowed data stored at the time into a plurality of data storage areas. area address determination means, and when the storage area determined by the storage area address determination means overflows during data storage, the address of the storage area is added to the divided column data, and the overflowed storage area is determined by the storage area address determination means. 1. A data management system comprising: control means for determining storage area addresses of data stored in a storage area and data to be stored and controlling storage area addresses;