JPS6244659B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a search method for data records having multiple keys, and more specifically, a method for searching data records having multiple keys of different types. Regarding the method of

For example, data related to parts, such as unit price, vendor, performance, standards, and other data, are stored in a storage device with the product name of the part added as a key, and the data is recorded using the key. Data on a desired part is obtained by searching for the desired part. In this case, the product name, name, specifications,
Alternatively, you can add multiple different types of keys corresponding to customer-specific product names, etc., and use any type of key to access the product name, name, specifications, or customer-specific product name. No matter which one is used, it is convenient to make it searchable.

If each key is assigned a different rank and the keys are arranged in ascending order, for example, the search can be performed quickly. However, as mentioned above, when assigning multiple different types of keys to data, it is assumed that one type of key is focused on and the data records are arranged in ascending order of keys by assigning different ranks to these keys. is not ascending for other types of keys,
This will be an array in random order. Searching by key for data records arranged in a random order with respect to keys can be done, for example, by sequentially reading all the data records one by one and comparing the read keys with the specified search key one by one. In the worst case, this would require reading the data record containing the key and comparing the keys as many times as there are stored data records. Therefore, the number of times of reading and comparison processing to be executed during a search increases, resulting in a disadvantage that the search takes time.

The present invention enables quick key-based searches of data records having a plurality of different types of keys and arranged in a random order, i.e., reading and comparing less than log ₂ N+1 (where N is the total number of data records) times. The purpose of the process is to provide a method for retrieving data records using any type of key.

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

FIG. 4 is a diagram explaining the principle of the two-branch search procedure used in the present invention. Here A, B, C, D,
E, F, and G are keys, each of which is ranked, and G is ranked higher than A. Let us now assume that the key to be searched is X. First, key D, which is in the middle of the keys A to G, is read out and compared with key D. If X is D, they match; if they do not match, if X is lower in rank, A, which is lower in rank than D,
The center B of B and C is designated and read out, and X and B are compared. If X is B, they match, but if they do not match, and if X is lower than B, A, which is lower in rank than B, is specified, A is read out, and X and A are compared. In this case, since A is the final key to be compared, X and A match. If X is higher than B, C, which is higher in rank than B, is specified and read out and compared with X. In this case as well, X and C match as described above.

Note that when comparing the ranks of X and D, unlike the above, if the rank of X is higher, then E, which is higher in rank than D,
Specify and read the middle F of F and G, compare X and F, if X is F, they match, and if they do not match, if X is higher than F, specify G and read X
Compare with. In this case, since G is at the last stage of comparison, X and G match. Also, X is F
If it is lower, specify E and read it and compare it with X. In this case as well, X and F match as described above.

In this way, the specified key is retrieved by at most three reads and comparisons among the seven keys,
The data record of that key can be read. That is, the specified key can be searched for at most log ₂ (N+1) times (in this case, since N=7, log ₂ (7+1)=3).

In the above, the information that specifies the next key to be read by comparing the ranking of the read key and the specified search key is specified as the lower search pointer (LP) when specifying a key with a lower ranking, and the key with a higher ranking. In this case, it is called an upward search pointer (UP).

FIG. 1 is a block diagram showing the configuration of one embodiment of the present invention. In the figure, M is the storage unit, MCTL
is the storage control unit, K-COM is the key comparison unit, KIN
is the search condition specification part and the key type specification information
KS and key specification information KV are input from input terminals KSin and KVin, respectively. The storage section M has an entry pointer storage area EA for storing entry pointers EP ₁ to EPm corresponding to the type of key, and a data record.
Data record storage area for storing DR ₁ to DRn
Equipped with DRA.

FIG. 2 is a diagram showing the structure of the above data records DR ₁ to DRn. In the figure, DR indicates the structure of a data record, data (in the case of the above parts, unit price, vendor, performance, and other information) is shown in part D, and types are shown in parts K ₁ to Km, respectively. Another key and its corresponding search pointer
Has LP and UP. K in the figure shows details of part _K1 , which is composed of a key KV, a downward search pointer LP, and an upward search pointer UP. Although not shown, the other portions K ₂ to Km also have the same configuration. The type of key KV can be made to correspond to the suffixes of the part K ₁ to Km.

FIG. 3 shows details of each data stored in the storage section M. In the data record storage area DRA of the storage section M, data records DR ₁ to DR ₇ are stored as shown. stored data records
The keys KV stored in the portion _K1 corresponding to each of the first type keys of DR ₁ to DR ₇ are A,
B, C, D, E, F, and G are ranked in this order. However, they are stored here in random order, not in ascending order.

The entry pointer storage area EPA of the storage unit M contains entry pointers EP ₁ to EPA corresponding to the type of key.
EPm is stored, but the first one of them is shown in the figure.
Only the entry pointer EP ₁ corresponding to the type of key is shown. Entry pointers EP ₁ to EPm contain data records of the corresponding type (one of DR ₁ to _{DR 7} , which are read for the first time, as explained in FIG. 4) corresponding to the type of key. address of the key in the middle position among all keys
Give the data.

In the embodiment shown in FIG. 1, in order to specify the first type of key and search for a data record using key X (one of A to G) in the corresponding type, first, the search condition is In the specification section KIN, information 1 specifying the type of key (1 to m) is inputted from the input end KSin, and key information X specifying one of the keys of the type is inputted from the input end KVin. Then, the specified key is searched for from all keys of the specified type using a two-branch search procedure.

Key type specification information 1 is the storage control unit MCTL
With this information 1, the content of the entry pointer EP ₁ corresponding to the type 1 is read out, in this case "6", and using this as an address, the data record storage area DRA is moved from address (AD) 6 to the central key D. The data record having the following data is read out and transferred to the key comparison section K-COM (see Fig. 3).

The key comparison section K-COM is first search condition specification section.
Information 1 specifying the type of key and key information X are input from KIN and are held.

The key comparison unit K-COM compares the key D of the portion K1 designated by the key type designation information ₁ of the transferred data record with the designated key X. If X is D, a match is detected, and as a result, it is determined that the search has ended, and the key comparison unit K-
The data record DR ₆ held in COM is output from the output terminal Out.

If X is not D, the ranks of X and D are compared, and if X is lower than D, the data record is
The downward search pointer LP, that is, "5" in part _K1 in _DR6 is extracted, and this information is stored in the storage controller.
Transferred to MCTL. This downward search pointer LP
The information "5" is the address information of the key B in the middle order among the keys lower than the key D.

The storage unit control unit MCTL uses the above information “5” as an address to read data record DR ₆ with key B from the data record storage area DRA of the storage unit M, transfers it to the key comparison unit K-COM, and compares it with the above. Compare X and B using the same procedure. If X is B, there is a match, so the search ends and the transferred data record DR ₆ is output. If there is no match, the search continues in the same manner as above, following the two-branch search procedure described with reference to FIG.

During the above search, when comparing the ranks of X and D, if X is in a higher rank than D, the upward search pointer in part K ₁ of data record DR ₆ is UP.
information "2" is extracted, and as described above, using this "2" as an address, data record DR ₂ with key F in the middle order of the three keys higher than key D is read out, and the above A search is performed using a similar procedure.

If you want to search using different types of keys,
Specify a new key type and perform the search in the same way as above.

In the above, for keys A, G, E, and C at the final stage of the search, which can no longer be branched into two, "0" is set as the upper and lower search pointers UP and LP. Therefore, in the final stage of the search, when a mismatch is detected, in other words, when the search is impossible due to specifying an unused key, "0" is set as the search pointer in the storage controller MCTL. Sent. Based on this, the storage controller MCTL sends unsearchable information to the output terminal ER.

Although the case where seven data records are searched has been described above, the present invention is not limited to seven data records; it is also possible to search a larger number of data records using exactly the same procedure. It goes without saying that it is possible.

Since the present invention is configured as described above,
This has the effect of quickly searching for data records that have multiple types of keys and are in random order. For example, when searching from 1023 records, if the records are sequentially read and searched, it will require 1023 read operations in the worst case, but according to the present invention, even in the worst case (log ₂ 1023 + 1 =)
The search can be completed after reading 10 times.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention, FIG. 2 is a diagram showing the structure of a data record in the present invention, and FIG. 3 is a diagram showing the structure of a data record stored in the storage unit of the embodiment of FIG. FIG. 4, a diagram showing the details of the data, is a diagram explaining the principle of the two-branch search procedure used in the present invention. M...Storage section, KIN...Search condition specification section,
MCTL...Storage control unit, K-COM...Key comparison unit, EA...Entry pointer storage area, DRA
...Data record storage area, EP ₁ - EPm ... Initial pointer, DR ₁ - DRn ... Data record, K ₁ - Km ... Part that stores keys and key-corresponding search pointers, D ... Data, KV ……Key,
LP...Downward search pointer, UP...Upward search pointer.

Claims (1)

[Claims] 1 A storage unit that stores data records having a plurality of keys and an upward search pointer and a downward search pointer for each key in a random order, and stores entry pointers corresponding to the types of keys, and a key comparison unit that holds specified information and key information to be searched, and compares the specified type of key of the data record read from the storage unit with the held search key; When searching for a data record, a two-branch search procedure is followed to read out the key in the middle order specified by the entry pointer corresponding to the specified key type, and to store the key as the read key. Based on the comparison result in the key comparison unit with the search key, the key specified by the upper search pointer or the lower search pointer of the read key is further read out, and this procedure is combined with the key read from the storage unit and the retained search key. A search method for data records having multiple keys, characterized in that the search is repeated until a key matches.