JPS628226A - File key search method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of Industrial Application The present invention relates to a file key search method for searching for a record having a key by using the two-part method and an approximate expression using the key as a variable.

Conventional technology In recent years, file key search methods include reading the file sequentially from the beginning, generating random numbers from the key value, determining the position from the random number and reading, and repeatedly comparing the size of the keys to narrow down the data. Generally, the two-division method is used, and the approximation method is used in which a linear equation is derived from the key values and relative positions of the two records, and the relative positions are determined from this.

Hereinafter, two aspects of the conventional file key search method described above will be described with reference to the drawings.

Figure 3 is an example of a conventional file key search method2.
This shows the division method. In FIG. 3, each black circle indicates the relative number and key value of the record. The operation will be explained below.

Consider a case where the search key is 40. First, a comparison is made with the key value 70 of record 5 whose relative number is in the middle.

Since the search key is smaller, similar searches are subsequently performed for records with relative numbers 1 to 4, and search record relative number 3 is found in the third comparison.

FIG. 4 shows a linear equation approximation method, which is another example of the conventional file key search method. In FIG. 4, black circles indicate relative numbers and key values of records, as in FIG. 3. The operation will be explained below.

Consider a case where the search key is 50. In this method, the relative numbers l and 9 are connected with a straight line, and a perpendicular line is drawn from the key value 50. The intersection of the horizontal line and the vertical axis from the intersection point A of this perpendicular line and the straight line is closest to relative number 3. Then, when looking at the key value of relative number 3, the key value is 90, which does not match. Next, connect the points with relative numbers 1 and 3 with a straight line and perform the same operation. Then, the desired record with relative number 2 is searched.

Problems to be Solved by the Invention However, in the method described above, the worst case can be suppressed by the two-part method, but it is not necessarily possible to search for the minimum number of times, and the approximation method using the following formula There was a problem in that efficiency deteriorated when the equation was extremely different from the equation.

In view of the above problems, the present invention provides a file key search method with high search efficiency.

Means for Solving the Problems In order to solve the above problems, the file key search method of the present invention searches for the target record by using a combination of the above two-division method and the approximation method from linear equations. be.

As described above, when the key of a search record is specified, the present invention uses a two-part method to search for a record from a corresponding file by comparing the key value of the median relative number in the target record with the search key. This is a file key search method characterized by searching for records by combining this method with an approximation method that estimates from a linear equation that passes through both ends of the relative number in the target record.

Embodiment Hereinafter, a file key search method according to an embodiment of the present invention will be described with reference to the drawings. - FIG. 1 shows the function of a file key search method in an embodiment of the present invention. In FIG. 1, black circles indicate relative numbers and key values.

In this example, the two-part method is applied to the first search, and the linear equation approximation method is used for subsequent searches. Consider a case where the search key is 100. First, records with a median relative number of 8 are searched according to the 2-division method. Key (! 140 (>10
0), so connect relative numbers 1 and 8 with a straight line and draw a perpendicular line from the point of key value 100. The intersection of the horizontal line and the vertical axis from the intersection of the straight line and the perpendicular line is closest to relative number 6. So relative number 6
Looking at the key value, it is 120, which does not match. Next, connect relative numbers 1 and 6 with a straight line and repeat the same operation, and the key value of the record with relative number 4 will be l.
OO and was able to search for the desired record.

FIG. 2 is a diagram illustrating a system configuration for implementing the present invention. In FIG. 2, 1 is a file, 2 is a key search mechanism, and 3 is an application program. The application program relies on the key search mechanism to read records. The key search mechanism accesses the file using the method shown in FIG. 1 and passes the relative number of the record having the relevant key to the application program.

Effects of the Invention As described above, the present invention enables searching for a record with a specific key from a file in which records are arranged in the order of keys.
By using a combination of the two-division method and the linear equation approximation method, it is possible to improve record search efficiency.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing processing in an embodiment of the present invention, and FIG.
The figure shows a system configuration for implementing the present invention, and FIGS. 3 and 4 are diagrams showing examples of processing in a conventional embodiment. l...File, 2...Key search mechanism, 3...Application program. Name of agent Patent attorney Toshio Nakao Number 1 Figure 3-m-Applied 7° program Figure 3 Figure 4

Claims (1)

[Claims] In a method of searching for a record with a specified key from a file in which records are stored in the order of a specific key, there are two methods: 2) repeating a size comparison between the specified key and the key of the record located in the middle of the file; A file key search method characterized by searching for a target record by combining a method of estimating the relative position of the target record from a linear equation based on the key value and relative position of two records.