JPH04195588A - Back coincidence retrieving processing system for data base - Google Patents

Abstract

PURPOSE:To rapidly execute back coincidence retrieval by providing the back coincidence retrieving processing system with a descending indexes. CONSTITUTION:A condition conversion means 5 converts conditions specified by a retrieval request in the descending order and a descending index key record retrieving means 6 retrieves a descending index key record 14 in the descending indexes 10 stored in a data base 8 by using the converted conditions as descending index key values. A record retrieving means 7 retrieves an objective record 9 from the pointer value of the retrieved record 14. Thus back coincidence retrieval can rapidly be executed.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a database suffix match search processing method % expression % [Prior Art] In the field of databases, a method is used to identify a specific record from a large number of records stored in a database file. The process of searching for records that satisfy conditions is called an "inquiry."

Incidentally, this inquiry is generally made by specifying a character string contained in a particular field of a record and determining whether or not the string matches.

Note that there are three search methods as follows depending on the form of matching.

・Starting match search ・Suffix matching search ・Middle matching search Here, a starting match search is a condition where the specified character string matches at the beginning of the field, and a suffix match search is a condition where the specified character string is a match at the beginning of the field. The condition is that a match occurs after the field, and the middle match search is a condition that the specified character string matches at any position in the field.

On the other hand, as a method for performing inquiries at high speed, an index in which values of predetermined fields in a record are used as index key values and arranged in the order of key values has been used.

[Problem to be solved by the invention]

As mentioned above, there are three search methods for inquiries, and an index is provided as a method to speed up the search, but if an index does not exist for the field to be matched, all the records will be searched using any of the search methods. Of course, even if an index is provided, suffix search and middle match search cannot be expected to have the same dramatic effect as prefix search. There was a drawback that there was no In other words, since indexes that target character strings generally determine the order based on the key value of the first character, a prefix search allows you to immediately search for a corresponding record from the index, but a suffix search or middle match This is because the order of the index has no meaning in a search, so all index key records must be read to determine a match.

The present invention has been proposed in view of the above points, and it is an object of the present invention to provide a processing method that allows a suffix match search to be performed at high speed. Note that intermediate match searches are not covered.

[Means to solve the problem]

In order to achieve the above object, the present invention is directed to a lowest block in which descending index key records having descending index key values in which the values of predetermined fields of records are arranged in descending order and a pointer value to the corresponding record are stored in order of key values. and an upper block in which upper descending index key records having the largest descending index key value in the lowest block and a pointer value to the lowest block are stored in order of key values; a condition conversion means for converting a condition specified in a search request into descending order; a descending index key record search means for searching a descending index key record of a descending index using the converted condition as a descending index key value; and record search means for searching for a target record from the pointer value of the key record.

[Effect]

In the data head suffix search processing method of the present invention, the condition conversion means converts the conditions specified in the search request into descending order, and the descending index key record search means converts the converted conditions into descending order as descending index key values. A descending index key record of the index is searched, and a record search means searches for a target record from the pointer value of the searched descending index key record.

〔Example〕

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

FIG. 1 is a block diagram showing an embodiment of the data base suffix match search processing method of the present invention.

In FIG. 1, the functional units of this embodiment include a descending index definition means 1, a record registration means 2, a descending index key value generation means 3, a descending index key record registration means 4, a condition conversion means 5, and a descending index key record. It includes a search means 6 and a record search means 7. In addition, as a storage area or storage information, a data header 8, a record 9, and a descending index 10 are stored.
, an upper block 11 , a lower order block 12 , an upper descending index key record 13 , and a descending index key record 14 . Note that the functions of each part will be explained through the following operations to avoid duplication.

Hereinafter, the operation of the above embodiment will be explained for each case.

(1) Record Registration Prior to registering a record, the descending index definition means 1 defines an arbitrary field within the record 9 to be registered as a target for generating a descending index.

FIG. 2 shows an example of the fields of a book record as record 9, which includes fields such as book title, author, and publisher. The descending index definition means 1 defines, for example, a book title field as a target for generating a descending index.

In FIG. 1, when a record 9 to be registered is subsequently given, the record registration means 2 determines the address on the database 8 in which the record 9 is to be stored, and registers it in the database 8.

Before and after the record 9 is registered in the data database 8 by the record registration means 2, the descending index key value generation means 3 generates the value of the field of the registered record 9 based on the field defined by the descending index definition means 1. Sort in descending order and generate descending index key values.

FIG. 3 shows a specific example of a descending index key value generated when the title field of a book record is defined as a target for descending index generation. Generates a character string that is the reverse of the book title character string as a descending index key value.

Next, in FIG. 1, the descending index key record registration means 4 stores the descending index key value generated by the descending index key value generation means 3 and the address on the database 8 of the record 9 registered by the record registration means 2. A descending index key record 14 consisting of a pointer value,
It is registered on the lowest block 12 of the descending index 10. Note that for the descending index key record 14, it is the lowest level record.

12 in descending order of index key values.

Also, the descending index key record 14 is the lowest block 12.
If the above is the same, the descending index key record registration means 4 creates an upper descending index key record whose descending index key value is the maximum descending index key value of the descending index key records 14 included on the lowest block 12. 13 is created on the upper block 11, and the pointer value of the upper descending index key record 13 is given the address of the lowest block 12 to point to the lowest block 12.

When newly registering a descending index key record 14 after that, it is stored in another lowest block 12, and the maximum descending index key value of the descending index key records 14 included on the lowest block 12 is set as the descending index key value. At the same time, an upper descending index key record 13 with the address of the lowest block 12 as a pointer value is created on the upper block 11.

Similarly, when all the upper descending index key records 13 of the upper block 11 are used up, an even higher upper block is created, and the descending index io is formed hierarchically.

The above processing is performed every time record 9 is registered.

Figure 4 shows the state of the data hese 8 after all the book records in Figure 3 have been registered, and the upper block 1
It consists of upper descending index key records 131 to 133 of 1, descending index key records 1401 to 1412 of lowest level 121 and 122, and records 901 to 912, and are hierarchically related by pointers. There is.

(2) Search for records A search request for record 9 specifies a certain character string as a condition for a field that has already been defined by descending index definition means 1, and specifies that records 9 whose suffix matches that character string are to be searched. shall be provided.

For example, a search request is made to the data header 8 in FIG. 4 such as ``Search for books whose title ends with ``Murder Case''.

In FIG. 1, in response to a search request for record 9, condition converting means 5 converts the character string of the specified condition in descending order,
Generate descending index key values.

For example, search for books with the title ``murder case'' mentioned above. ”, the condition conversion means 5 converts the condition character string “murder case” into vllll[
, and generate “Incident Massacre” as a descending index key value.

The descending index key record search means 6 searches the database 8 based on the descending index key value generated by the condition converting means 5.
The descending index key record 14 of the descending index 10 is searched. That is, the search first reads the upper block 11,
The upper descending index key record 13 having the descending index key value that is closest and larger than or equal to the descending index key value for which the search request was made within the upper block 11 is obtained, and the lowermost block 12 is searched from the pointer value. Follow the
The corresponding descending index key record 14 is obtained.

Taking the aforementioned descending index key value "Case Massacre" as an example, the descending index key record search means 6 first refers to the upper block 11 in FIG. 4 to obtain the upper descending index key record 131. Then, the top l order index key record 13
Tracing the lowest block 121 from the pointer value of 1, the descending index key record 1404 has a prefix match of “Incident Massacre”
Then, the descending index key records 1405 to 1409 of the following lowest blocks 1, 22, and 123 are obtained.

In FIG. 1, the record search means 7 acquires a record 9 from the database 8 based on the pointer value of the descending index key record 14 searched by the descending index key record search means 6.

In the above example, the record search means 7 searches the acquired descending index key records 1404 to 1409 in FIG.
Based on the pointer value of record 903.911.90
Get 9.901.905,907.

As explained above, the backward-losing search can be performed extremely quickly.

For example, if the total number of records is 1 million, the record blocking factor (the number of records in one block) is 10, and the index block blocking factor is 200, then the total number of records to be obtained is If a traditional index is not defined, 100,000 l10s (input/output operations) are required to search all blocks of a record, and if an index is defined, the index It takes 5,000 times of Ilo to search all the programs in , but in the present invention, it takes 2 times of Ilo to sequentially trace from the highest block to the upper block and the lowest block in the descending index 10. This means that Ilo only needs to be executed three times in total, one for each record stored, and a dramatic increase in speed can be achieved.

〔Effect of the invention〕

As explained above, in the database suffix search processing method of the present invention, by having a descending index,
This has the effect of allowing suffix matching searches to be performed at high speed and improving service for inquiries.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an example of the suffix match search processing method of the database of the present invention, FIG. 2 is a diagram showing an example of the logical structure of records, and FIG. 3 is a specific example of a descending index key value. FIG. 4 is a diagram showing a specific example of the database. In the figure, 1... Descending index definition means 2... Record registration means 3... Descending index key value generation means 4...
Descending index key record registration means 5...Condition conversion means 6...Descending index key record search means 7...
...Record search means 8...Database 9...Record 10...Descending index 11...Upper block 12...Lowest block 13...Upper descending index key record 14... Descending index key record

Claims (2)

[Claims] (1) A lowest block that stores descending index key records in order of key value, each having a descending index key value in which the values of a predetermined field of a record are arranged in descending order and a pointer value to the corresponding record, and a maximum block within the lowest block. A descending index hierarchically formed by upper blocks storing upper descending index key records in the order of key values, each having a descending index key value and a pointer value to the lowest block, and a condition specified in a search request. a condition conversion means for converting to descending order; a descending index key record search means for searching a descending index key record of a descending index using the converted condition as a descending index key value; A suffix match search processing method for a database, comprising: a record search means for searching records. (2) A descending index definition means that defines any field in a record as a target for generating a descending index, a record registration means that registers the record in the database, and a field value defined by the descending index definition means at the time of record registration. descending order index key value generation means for generating a descending order index key value in descending order, and descending order index key record registration means for registering a descending order index key record including the generated descending order index key value in the descending order index. 2. The database suffix match search processing method according to claim 1.