JPH05257610A - Device and method for reading file - Google Patents

Abstract

(57) [Summary] [Object] An object of the present invention is to realize high-speed reading of a file. [Structure] When a page address list of necessary pages is created by interpreting an input search command, pages are segmented in units of continuous addresses on pages that do not exist in the main memory. Further, address interval information of the unnecessary pages is linked to the necessary page segment, and the necessary pages before and after the unnecessary page having the number of pages equal to or less than the seek factor are integrated into one segment to reorganize the segments. Then, the data is read in this segment unit, and the necessary page is stored in the used fixed buffer and the unnecessary page is stored in the reusable buffer.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a file reading device and a reading method for reading data from a magnetic disk device or the like.

[0002]

2. Description of the Related Art To access data stored in a magnetic storage device, etc., follow the steps of (1) moving the head to the address position of the data to be read (seek), and (2) reading the desired data. Be seen. When data is read from a magnetic disk device or the like, the seek operation of moving the head to a predetermined position is time-consuming because it involves a mechanical operation.

Therefore, when reading data, it is necessary to read at consecutive addresses as much as possible to reduce the number of seeks.

[0004]

When reading data in a file, there may be unnecessary data within the necessary data range. In such a case, for example, by skipping unnecessary data It is conceivable to realize such reading.

However, when the area to be skipped is large, it may not take much time to interrupt the reading and seek, which is not always the best method. An object of the present invention is to realize high-speed reading of files.

[0006]

FIG. 1 is a block diagram showing the principle of the first invention. In the file reading device that retrieves the necessary data discretely existing in the file (1) and reads the data into the buffer, the segment constructing means 2 makes the necessary data to be read in the file 1 in units of consecutive addresses. Segment.

The data reading means 3 estimates the access time for continuous reading between the segments and the access time for seeking when moving the reading position on the file between the segments, and the continuous reading between the segments. When the access time is shorter to read, a plurality of segments including unnecessary data are sequentially read into the buffer.

For example, the data reading means 3 stores the necessary data in the used fixed buffer and the unnecessary data in the reusable buffer which is reused when the buffer area becomes insufficient, out of the continuously read data.

According to the second aspect of the invention, when necessary data discretely existing in the file (1) is searched and the data is read into the buffer, the necessary data to be read has consecutive addresses in the file 1. It is better to estimate the access time for continuous reading between segments and for seeking when moving the reading position in the file between each segment by segmenting by segment, and then reading between segments continuously. When the access time is short, a plurality of segments including unnecessary data are sequentially read into the buffer.

[0010]

In the first and second aspects of the invention, when the data of a plurality of segments whose addresses are not consecutive are read, the access time when reading continuously between segments and when seeking is estimated, and the access time is calculated. Since the data is read in a short way, the data reading can be speeded up.

Further, when a plurality of segments containing unnecessary data are continuously read, the necessary data is stored in the use fixed buffer and the unnecessary data is stored in the reusable buffer. The main memory resident rate of the search target data can be increased while effectively utilizing it. As a result, the overhead for reading data that does not exist in the main memory from the file can be reduced.

Further, information serving as a criterion for deciding whether to continuously read or seek between the segments,
Since the information is given as information that can be defined externally, even if the performance of the reading device is different, it is possible to set the optimum condition for the performance of the device by changing the reference information.

[0013]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 2 is a system configuration diagram of the embodiment of the present invention.

This system reads data satisfying the search condition from the secondary storage device 13 according to a search command input from the keyboard 12 and displays the result on the display device 14.

The circuit block diagram of the file reading device 11 of FIG. 2 shows various processes such as main control executed by the CPU, acceptance of search commands, interpretation of search conditions, setup, page reading, display of search results, and the like. , Page address list, page address hash, page
The relationship with addresses, segments, etc. is shown.

First, the overall operation of the file reading device 11 will be described with reference to the flowchart of FIG. The setup process (FIG. 3, S1) is executed by the main control process when the operation of the system is started. In this setup processing, the seek factor, free page management information, index, etc. are read from the secondary storage device 13 into the main storage (S
2, S3, S4).

Now, the states of the empty page management information, index and data page will be described with reference to FIGS. The free page management information stores information indicating whether the page is used or is empty for each page address as shown in FIG. 4 (in this example, when the page is used, “1”, When it is free, "0" is written), and an unused page can be searched from this free page management information.

Further, as shown in FIG. 5, the key values A to H are stored in the index in ascending order of the keys, and the page address of the data corresponding to each key value on the data page file is stored. Is stored in association with the key value.

The diagram showing the state of the data page of FIG.
A key value of data stored in each page in the order of page addresses or information indicating that the page is empty is stored.

Returning to FIG. 3, when the setup process is completed, the data search process of step S5 is executed. In this data search process, input of a search command is accepted from the keyboard 12 (S6), search conditions are extracted from the input search command, and the search conditions are interpreted (S7).
Then, the page address where the data satisfying the search condition is stored is checked from the index, and a page address list of necessary pages is created (S8).

In the next page reading process (S9), the page designated by the page address list is read as data.
Read from the page file into a buffer on main memory.
At this time, it is checked whether or not the content of the desired page address exists in the buffer, and only the page that does not exist in the buffer is read.

When the required page satisfying the search condition is read into the buffer in this way, the search result is displayed on the display device 14 (S10). Here, the contents of the page reading process of step S9 will be described with reference to the flowchart of FIG.

Now, from the keyboard 12, select "SELECT * FROM
DATAPAGE WHERE KEY> = 'A' AND KEY <= 'D';"
It is assumed that the search command is entered. this is,
It is a request to search for a key in the range of values'A '≤ KEY ≤'D'.

First, the fixed use buffer created by the previous retrieval request is transferred to the reusable buffer (FIG. 7,
S11). At this time, the buffer transitioning from the link of the fixed use buffer is linked to the end of the reusable buffer.

Next, the buffer on the main memory corresponding to the required page address is searched from the page address list created by analyzing the search conditions (S12). In this process, first, a page address hash is used to search for a buffer corresponding to a required page address (S13).

Here, the page address hash is a correspondence between a page address and a buffer by a hash function. For example, x is a page address and S is a page address.
Is the number of arrays in the hash table ("10" in this case),% is x
When used as an operator for calculating the remainder when divided by, the page address and the array number of the hash table are associated with each other by the hash function: H (x) = x% S.

FIG. 8 is an explanatory diagram of the page address list and the page address hash. For example, since page addresses “10” and “20” are H (x) = 0 from the above hash function, they correspond to the 0th array in the hash table and the buffer corresponding to the page address (see FIG. 8).
The buffer that stores the data of key B and key D)
If exists, it is registered in the 0th link of the array.

Therefore, the buffer corresponding to the page address can be easily found by referring to this page address hash. As shown in FIG. 8, each buffer has a key value of data stored in the buffer, a page address, and buffer classification information indicating whether the buffer is a fixed-use buffer or a reusable buffer. have.

Returning to FIG. 7, the required page address and the buffer are associated with each other by referring to the page address hash (S14). Further, the buffer classification information of the buffer corresponding to the required page address is rewritten to "1", and the buffer is linked to the end of the fixed fixed buffer (S15).

Then, it is determined whether or not all the buffers corresponding to the required page address are present in the main memory (S16), and if they are present, the page reading process is terminated.

On the other hand, when the buffers corresponding to the required page addresses are not available in the main memory, the page address / address is determined in step S17 in order to decide whether to read the data continuously or by seeking. Create a segment.

FIG. 9 is a flowchart of the page address segment creation processing. First, a page address for which no buffer exists is picked up in the page address list (S31).

At this time, whether or not the buffer corresponding to the page address exists is determined by the pointer to the buffer in the page address list shown in FIG. 10 (1) pointing to a specific buffer or "NULL". It can be judged by whether or not.

The pointers of the page address list in FIG. 10 (1) are all "NULL", which indicates the case where all the buffers corresponding to the search target keys A to D do not exist.

Next, the picked-up page addresses are sorted and rearranged in the order of page addresses (S32),
Segment continuous page addresses (S
33).

FIGS. 10 (2) and 10 (3) show an example of segmenting a page address sequence. In this case, page 1 and page 2 are continuous, and the other pages, 7, 10, 15, 18, 20 are not continuous, so page 1 and page 2 are one segment, and the other pages are Each will be an independent segment.

Next, the unnecessary page between each segment and the address interval information are inserted into the link of the segment of the necessary page (S34). FIG. 10 (4) shows an example of the state at this time.

Then, the address interval information of the unnecessary pages whose page intervals are equal to or less than a predetermined seek factor is removed from the interval information of the segments and the unnecessary pages, and the segments of the necessary pages on both sides of the unnecessary pages are combined into one segment. The segments are reorganized (S35).

By the way, when reading discrete data on a file, if the head moves to the address position of the data that does not need to be read, it may be shorter to access the data by seeking to the next address position. There are two possible methods when the unnecessary data is read continuously and the access time is shorter.

FIG. 11 is an explanatory view of a trade-off of access time in the case of seeking and in the case of sequential reading. When the page interval is equal to or less than a constant value P _r , the seek is performed by sequentially reading unnecessary pages. Access time is shorter than.

The seek factor that serves as a criterion for determining when associating a plurality of segments into one segment in step S35 is a value determined by the page interval P _r at this time, and in this embodiment, the seek factor is "2". When the page interval of unnecessary pages is 2 pages or less, necessary pages before and after the unnecessary page are combined into one segment.

For example, if the page address segment shown in (4) of FIG. 10 is reorganized based on the above seek factors, 8-9 pages of unnecessary pages, 19 pages of unnecessary pages and 16-17 of unnecessary pages. Since each page has a page interval of 2 pages or less, the page interval information can be removed and the necessary pages before and after can be combined into one segment.

As a result, as shown in (5) of FIG.
~ 2 pages, 7-10 pages, 15-20 pages each become one segment, and 3-6 pages of unnecessary pages and 11-pages of unnecessary pages having a page interval of 3 pages or more.
14 pages remain.

When the page address segment is created as described above, the page reading process from the file in step S18 of FIG. 7 is executed. In this read processing, the page address segments created as described above are sequentially taken out (S19), and first the file read position is sought to the top page address of the page address segment (S20). Next, data is continuously read for the number of pages indicated by each segment (S21), and the page-by-page buffer is read and the skip processing is executed (S23).

FIG. 12 is a flow chart of the reading and skipping processing of the page buffer. First, the first page address of the segment of the required page of the page address segment is read, and it is determined whether the page is a required page, an empty page, or an unnecessary page (S41). At this time, whether or not the page to be read is a necessary page is determined by referring to the page address list, and whether or not it is a blank page is determined by referring to the blank page management information (Fig. 4). Be seen.

If the page read in the determination in step S41 is a required page, the process proceeds to step S42 to secure a buffer for storing the page (S4).
2). Further, the page data corresponding to the secured buffer is read, the buffer classification of the buffer is rewritten to "1", and the pointer of the buffer is linked to the end of the fixed fixed buffer (S43).

In order to search this buffer efficiently, the buffer is registered in the page address hash based on the above-mentioned hash function H (x) (S4).
4). Further, a pointer pointing to the buffer is set to the corresponding page address in the page address list (S45).

On the other hand, if it is determined in step S41 that the read page is an empty page, the process proceeds to step S46 and the page is skipped without being stored in the buffer.
On the other hand, if it is determined in step S41 that the read page is neither a necessary page nor an empty page, it is an unnecessary page. In this case, the process proceeds to step S47 to check whether the same page exists in the reusable buffer. Whether or not the same page exists in the buffer is checked by checking whether or not the page is already registered in the page address hash.

When the corresponding page already exists in the main memory, it is not necessary to read the page, so that the page is skipped (step S48). If the same page does not exist in the main memory, a buffer for storing unnecessary pages is secured (S49).

Then, the unnecessary page is read into the newly secured buffer, the buffer classification of the buffer is set to "0", and at the same time, the pointer of the buffer is linked to the end of the reusable buffer (S50).

Further, similar to S44, this buffer is registered in the page address hash (S51). It should be noted that reading unnecessary pages into the main memory is effective in increasing the resident ratio of the main page of the search target page, because the unnecessary pages may be required for the next search.
On the other hand, it is conceivable that many main memory areas are used for that purpose and the main memory area becomes insufficient.

Therefore, in this embodiment, necessary pages are stored in a fixed-use buffer, unnecessary pages are stored in a reusable buffer, and when a new buffer area is insufficient, the reusable buffer is set to that area. As available.

Further, even the ones set in the used fixed buffer in this search are all moved to the reusable buffer in the next search, so that many search target pages are made resident in the main memory to improve the search efficiency. While increasing, the reusable buffer can be used as if it were a newly secured buffer area, and the main memory can be efficiently used.

FIG. 13 is an explanatory diagram of the above-mentioned buffer read operation. First, referring to the page address segment reorganized by the seek factor, it is checked whether the page to be searched is a required page.

For example, referring to the page address segment of FIG. 10, since the segments of page addresses 1 and 2 are necessary pages, a buffer for storing those pages is secured and the data page file (see FIG.
The contents of the corresponding page of 3) are sequentially read into those buffers. Further, the division of those buffers is set to "1" and the buffer is linked to the end of the fixed use buffer.

Since the segment of page addresses 3 to 6 is an unnecessary page segment, reading is not performed, and the segment of page addresses 7 to 10 is a required page. Therefore, the head is sought at the position of page address 7 to read those segments. Read pages continuously.

In this case, since pages 7 and 10 are necessary pages, each page is stored in a buffer and those buffers are linked to the end of the fixed fixed buffer.
On the other hand, pages 8 and 9, which are unnecessary pages, are likewise stored in buffers and linked to the end of the reusable buffer.

Since pages 11 to 14 are empty pages, data is not read. Since the segments of the next pages 15 to 20 are necessary page segments, the head is sought at the position of page address 15 to start reading data.

In this case, since page 15 is a necessary page, the contents of the page are stored in the buffer and the buffer is linked to the end of the fixed use buffer. Page 1
Although 6 is an unnecessary page, the contents of the page are stored in a buffer and the buffer is linked to the end of the reusable buffer. Since the next page 17 is a blank page, it is skipped as it is.

Since page 18 is a necessary page, the contents of that page are stored in a buffer and linked to the end of the fixed use buffer (in this case, the page 15 is next to the buffer in which it is stored). Since page 19 is an empty page, it is skipped without being stored in the buffer. Since the next page 20 is a required page, the contents of that page are stored in a buffer, and that buffer is linked to the end of the used fixed buffer.

As described above, when there is an unnecessary page or an empty page between the necessary pages which satisfy the search condition, the access time when the page is continuously read and when the seek page is read is calculated, When the access time when reading continuously is equal to or shorter than the seek time, those pages are assimilated into one segment. Then, the file is continuously read in units of the segments created as described above.

Therefore, even when reading the discrete data on the file, the necessary data can be read in the shortest time. Also, link the necessary data in the continuous read data to the used fixed buffer and the unnecessary data to the reusable buffer, and use the reusable buffer as a new buffer area when the buffer area becomes insufficient. Since it can be used, the main memory area can be efficiently used while increasing the main memory resident rate of the search target data.

Next, the operation for securing the buffer area will be described with reference to the flowchart of FIG. The main storage area is used not only for buffers but also for page address lists, page address hashes, etc., so the maximum size of the buffer area (the limit number of buffer areas) must be set to secure those areas. An estimate is made in advance, and if the number of buffer areas reaches the limit, a reusable buffer is used as a newly provided buffer area.

First, it is judged whether or not the limit number of the buffer area is reached (FIG. 14, S61). If the number has not reached the limit, a new buffer area is secured in the main memory (S6).
2).

On the other hand, when the limit number is reached, the oldest buffer among the reusable buffers is selected (S6).
3). In the present embodiment, both the fixed buffer used and the reusable buffer are connected to the latest read buffer or the latest regarded necessary page at the end of each link. It is an old buffer.

Therefore, in step S63, the oldest buffer is selected by extracting the head buffer of the reusable buffer. Then, the next step S6
At step 4, the selected buffer is unlinked from the reusable buffer. As a result, the content of the page address stored in the buffer does not exist in the main memory, so the buffer is excluded from the page address hash (S65).

Further, the pointer of the buffer removed from the link is set as the pointer of the newly secured buffer area (S66). For example, in the explanatory diagram of FIG. 13, if the buffer area runs short when trying to read the contents of the page address 18, the buffer of the page address 8 at the head of the reusable buffer is removed from the link and the page address 18 is deleted. It is reused as a buffer for storing the contents of.

As described above, for example, "SELECT * F
ROM DATAPAGE WHERE KEY> = 'A' AND KEY <= 'D';
"GET * FROM DATA
Suppose there is a search request of "PAGE WHERE KEY> = 'E' AND KEY <= 'H';".

In this case, since the data of the key values A to D are present as the required data and the data of the key values E and F are present in the main memory as unnecessary data in the previous search, the page address 6
Key value G data of page address 21 and key value G of page address 21
And the data of the key value H of the page address 24 need only be read from the data page file into the buffer in two seek operations.

In the above embodiment, the data is read from the file in page units. However, the present invention is not limited to this, and the data may be read in record units or predetermined document data as one unit.

Further, as a seek factor which is a criterion for determining whether data is continuously read including unnecessary portions or read by seeking, a page interval which is a trade-off between seek time and access time in sequential reading is used. However, the information is not limited to the page interval, and can be used to determine whether the continuous read or seek is the shorter access time, such as the number of records, the number of document data, or sequential read time and seek time. If it is good.

[0072]

According to the present invention, when reading discrete data on a file, the time required for continuous reading including unnecessary portions and the time required for seeking only necessary portions are read. By estimating in advance, the data can always be read by the method with the shortest access time. In addition, the required pages that have been read are stored in the fixed buffer for use and unnecessary pages are stored in the reusable buffer, and the reusable buffer is reused when the buffer area is insufficient. It is possible to increase the residence rate of data in the main memory and reduce the overhead due to file access.

Further, since the information serving as a criterion for determining whether to continuously read or seek and read is held as information independent of the file reading process, the data reading process depends on the performance of the file reading device. It is possible to read data under the optimum conditions of each device without having to change.

[Brief description of drawings]

FIG. 1 is a principle block diagram of the present invention.

FIG. 2 is a system configuration diagram of an embodiment.

FIG. 3 is a flowchart showing the overall operation of the embodiment.

FIG. 4 is a diagram showing a data structure of empty page management information.

FIG. 5 is a diagram showing a data structure of an index.

FIG. 6 is a diagram showing a state of a data page.

FIG. 7 is a flowchart of a page reading process.

FIG. 8 is an explanatory diagram of a page address list and a page address hash.

FIG. 9 is a flowchart of a page address segment creation process.

FIG. 10 is an explanatory diagram of creating a page address segment.

FIG. 11 is an explanatory diagram of a trade-off between access times in seek and sequential reading.

FIG. 12 is a flowchart of page-by-page buffer read / skip processing.

FIG. 13 is an explanatory diagram of an operation of reading a page into a buffer.

FIG. 14 is a flowchart of a buffer area securing process.

[Explanation of symbols]

 1 file 2 segment construction means 3 data reading means

Claims (7)

[Claims] 1. In a file reading device for searching for necessary data discretely existing on a file (1) and reading the data into a buffer, the necessary data to be read is a unit in which addresses are consecutive on the file (1). Segment segmentation means (2) for segmenting with, and when moving the read position on the file (1) between the respective segments, estimate the access time when reading continuously between segments and when seeking A file reading device comprising: a data reading means (3) for sequentially reading a plurality of segments including unnecessary data into a buffer when the access time is shorter when reading between the segments continuously. 2. The data reading means (3) stores necessary data of the read data in a fixed buffer for use and unnecessary data in a reusable buffer which is reused when the buffer area becomes insufficient. The file reading device according to claim 1. 3. The data reading means (3) assimilates the plurality of segments into one segment when the access time is shorter to read continuously between the segments, and the file (1 2.) The file reading device according to claim 1, wherein the data is read from 4. The information as a basis for estimating the access time by the data reading means (3) is information that can be externally defined independently of the access time estimation processing executed by the means. The file reading device according to claim 1, 2, or 3. 5. When retrieving necessary data discretely existing in a file (1) and reading the data into a buffer, the necessary data to be read is segmented in units of consecutive addresses on the file (1). When moving the read position on the file (1) between the respective segments, it is better to estimate the access time when continuously reading between the segments and when seeking, and to continuously read between the segments. When the access time is short, a file reading method is characterized in that a plurality of segments including unnecessary data are sequentially read into a buffer. 6. A reusable buffer in which, when a plurality of segments containing unnecessary data are sequentially read into a buffer, necessary data of the read data is used as a fixed buffer and unnecessary data is reused when the buffer area is insufficient. 6. The file reading method according to claim 5, wherein the file is stored in. 7. When the access time is shorter to read continuously between the segments, the plurality of segments are assimilated into one segment, and the data is read from the file (1) in the segment unit. 7. The file reading method according to claim 5, wherein: