JPH0789335B2 - Inserting and referencing records in indexed sequential files - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Object of the Invention (Industrial field of use) The present invention inserts a new record in the middle of a record arranged in order by random access by a key value to an indexed sequential file. In addition, the present invention relates to a record insertion and reference method in an indexed sequential file suitable for referring to a record moved by record insertion.

(Prior Art) Generally, an indexed sequential file stored on a disk is
As shown in FIG. 4A, an index part 11, a transposing part (transposing index part of the sub-key) 12, and a data part 13
Consists of. The data part 13 is composed of several data blocks 14, each data block 14 is composed of several data records 15 arranged in a primary key value order (here, in ascending order), and a record control block prepared for each record 15. (Not shown). The data record 15 has a primary key value (numerical value in the figure) and a secondary key value (lowercase letters in the figure). The record control block indicates the block position of the corresponding record 15 and its record length.

Next, the transposition unit 12 consists of several transposition blocks 16. This transposed block 16 is for accessing several data records in the order of the subkey values. It has the subkey value as a record and also has the index value to the data record (only the subkey value is shown in the figure. Exist).

In addition, the index unit 11 includes some (here, one) index blocks 17 forming a primary key index tree and some (here, 1) forming subkey index trees.
3) index block 18. First, the index block 17 has as a record the maximum primary key value in the block one step below (here, the data block 14), and also has the index value to that block (only the primary key value is shown in the figure. ing). The primary key values in the index block 17 are arranged in the order of their values (here, ascending order). Next, the index block 18 is 1
It has the record of the maximum subkey position in the lower block (transposition block 16 in this case) and also has the index value to that block (only the subkey value is shown in the figure). The arrangement of the sub-key values in the index block 18 is the value order (here, ascending order).

Here, in the indexed sequential file shown in FIG. 4 (a), a new data record 25 having a primary key value of 2 and a secondary key value of b is shown in FIG. 4 (b) according to the key value. A conventional method in the case of random access insertion will be described. In this case, since the records must be arranged in ascending order of the primary key values, the insertion position of the record 25 has two primary key values of 0 and 4 as apparent from FIG. 4 (a). It's between record 15. However, if the free space 19 in the data block 14 in which the two records 15 with primary key values 0 and 4 are stored is smaller than the size of the insert record 25, the record 25 is inserted into the data block 14. You cannot do it. In this case, a new data block 24 is created on the disk as shown in FIG. 4 (b),
Almost half of the records (here, record 15 whose primary key value is 4) is moved to the same block 24 from the original block 14 to expand the empty space of the block 14 (that is, after performing block division), and then the same block The target record 25 is inserted into 14 (block storing the record 15 having a primary key value of 0). At this time, the index tree of each subkey is traced from the root block (here, the index block 18) based on the subkey value b of the record 25 inserted in the block 14, and the index (record) of that subkey value b The transposition block 16 in the transposition unit 12 to be the addition destination is searched for. In the example of FIG. 4 (a), since this sub-key position b is smaller than the minimum sub-key value e in the index block 18, the transposed block 16 having the index of this sub-key value e It is obtained as the addition destination of the index of b. In this transposed block 16, in addition to the index of the subkey value e, the indexes of the subkey values a and c exist. Here, the magnitude relationship between the sub-key value b and the sub-key values a, c, e is a <b <c
Since <e, the indexes of the subkey values c and e are moved as shown in FIG. 4 (b), and the index of the subkey value b is added between the subkey value a and the subkey value c. It

As a result of the above block division, the position of the record 15 having the primary key value of 4 and the secondary key value of g changes. Therefore, the point point of the index for the record 15 in the transposed block 16 is changed from the position indicated by the arrow P1 in FIG. 4 (a) to the position indicated by the arrow P2 in FIG. 4 (b).
That is, the destination of the record 15 (actually, the record control block in the data block 24 corresponding to the record 15 after the movement) must be changed. For this change,
Similar to the case of adding the index of the sub key value b of the record (inserted record) 25 described above, the index tree of each sub key is traced from the root block (here, the index block 18) to find the record of the index to be changed. That operation is required. However, this operation requires a disk access in units of a large number of blocks (generally, a block becomes a unit of disk access), and thus requires a great deal of processing time. Moreover,
Even if the above change processing is performed, if the corresponding record (moving record) 15 is not referred to, the time required for the change processing is wasted.

(Problems to be Solved by the Invention) As described above, conventionally, when a block division occurs in a data recorder insertion operation for an indexed sequential file and a record previously stored in a data block is moved, Since the index tree of the alternate key needs to be traced from the root block in order to change the index value for that record (moved data record) in the transposed index part of the key, disk access for a large number of blocks is required. There was a problem that it decreased.

Therefore, the problem of the present invention is that the block division occurs in the data record insertion operation for the indexed sequential file, the position of the data record previously stored in the data block changes, and it exists in the transposed index part of the alternate key. It is to prevent a decrease in processing speed when the sub-key value of the record (moving record) does not match the point destination of the index. Another object of the present invention is to make it possible to efficiently refer to a record moved along with the record insertion.

[Structure of the Invention] (Means for Solving the Problems) The present invention relates to a record control block prepared for each data record stored in a data block which is a constituent element of an indexed sequential file, in which the same record is stored. The data record corresponding to the control block is provided with a move destination information field for setting the move destination information indicating the move destination when the data record is moved to a new data block by block division accompanying the insertion of the new data record. When moving and inserting a new data record, move destination information indicating the move destination of the record is set in the move destination information field in the record control block corresponding to the record before movement, and the block accompanying the record insertion is set. It is set in the transposed index part of the alternate key along with the alternate key value of the data record that was moved by splitting. It is characterized in that so as to omit the change process of change looking for the index to the same record. This changing process is performed based on the setting content of the move destination information field in the record control block used for the reference when the move record is referred to by the irregular access by the sub-key value.

(Operation) According to the configuration described above, when a data record is moved due to block division accompanying record insertion, information indicating the destination is set in the destination information field of the corresponding record control block of the original data block. Therefore, even if you omit the modification process of searching for and changing the index to the same record that is set with the subkey value of the moved data record in the transposed index part of the subkey, It becomes possible to refer.
That is, it is possible to omit the processing of changing the transposed index portion when moving a record due to block division, and thus it is possible to prevent the processing speed from being lowered due to this kind of changing processing. In addition, the above-mentioned change processing is performed when the moved record is actually referred to by the irregular access by the alternate key value, so it is useless as compared with the conventional method in which the change processing is unconditionally performed when the record is moved due to block division. There is no need to change.

Embodiment An embodiment of the present invention will be described below with reference to the drawings.
The same parts as those in FIG. 4 are designated by the same reference numerals and detailed description thereof will be omitted.

First, it is assumed that a disc (not shown) stores an indexed sequential file having the same record structure as the indexed sequential file shown in FIG. 4 (a). However, the structure of the data block, which is the element of the indexed sequential file used in this embodiment (more specifically, the structure of the record control block in the data block) is shown in FIG. 4 (a). It differs from that of the conventional indexed sequential file. The structure of the data block (further, the structure of the record control block) will be described with reference to FIG.

In FIG. 1 (a), 14 'is a data block having two data records 15 having a primary key value of 0 (subkey value is i) and a primary key value of 4 (subkey value is g), and 31 is a block. It is a control block. Block control block 31 is the same block
The data block in which 31 is placed (here, the data block
14 ') information indicating the position and size of the empty space 19 and information indicating the chain of data blocks when the data records are accessed in the order of the primary key value by referring to only the data block (that is, the next data). Blocks and pointers to previous data blocks) etc. are set. The block control block 31 is provided with a block identifier field for identifying a corresponding data block, for example, a block number field 32 in which a sequential block number is set. In the figure, field 32 has the value 10
Block number is set.

33 is a record control block for the record 15 having the primary key value of 0 (the first record in the data block 14 '), and 34 is the record 15 having the primary key value of 4 (2 in the data block 14').
Record control block for the second record). The record control block 34, as shown in FIG. 1A, has a record length field 41 for setting information indicating the size (record length) of the corresponding record, the data block of the corresponding record (here, the data block 14 '). An in-block position information field 42 for setting information indicating an inner position, and move destination information indicating a move destination when a corresponding record is moved to a new data block by block division accompanying insertion of a new data record A destination information field 43 for Record control block
The format of 33 is the same as that of the record control block 34 described above, and is therefore omitted in FIG. 1 (a).

The information set in the block position information field 42 is
The block number of the corresponding data block (10 in the figure) and the block number of the corresponding record control block (record control block 34). The block number of the record control block 34 is determined by the number of the corresponding record in the data block 14 ', and is 2 in this example. This number 2 also indicates that the corresponding record control block 34 is the second last block in the data block 14 '. If the corresponding record is moved to another data block, the block internal position information field 42
Is NULL indicating that the contents of field 42 is invalid.
A value (null value) is set. On the other hand, the information set in the destination information field 43 is the block number of the destination data block of the corresponding record and the block number of the corresponding record control block. When the corresponding record is not moved to another data block, the destination information field 43 has a null value (null value) indicating that the content of the same field 43 is invalid as shown in FIG. ) Is set.

In this embodiment, the data block 14 'shown in FIG. 1 (a) has the primary key value 0 (sub key value i) and the primary key value 4 (sub key) shown in FIG. 4 (a). It is used instead of the data block 14 having the two data records 15 with the key value g). Therefore, if necessary, two records with primary key values 0 and 4 in FIG.
Refer to by replacing the data block 14 with the data block 14 'shown in FIG. 1 (a).

Here, in FIG. 1A, the primary key values 0 and 4 are 2
It is assumed that it is necessary to insert a new data record 25 having a primary key value of 2 and a sub key value of b between two records 15 as shown in FIG. At this time, assuming that the size of the inserted record 25 is larger than the empty space 19 of the data block 14 'having the above two records 15,
Block division occurs as in the conventional case. That is, first
As shown in FIG. 9B, a new data block 24 'having a block number 11 is generated on the disk, and the record 15 having the primary key value of 4 is moved from the original block 14' to the block 24 '. At this time, the record control block 35 for the move record 15 is set in the data block 24 '. The contents of the record control block 35 are the same as those of the record control block 34 before record movement (before block division) shown in FIG. 1A except the contents of the in-block position information field 42. That is, in the field 42 of the record control block 35, the block number 11 of the new data block 24 'and the block number 1 of the record control block 35 are set.

On the other hand, the record control block 34 in the original data block 14 'for the moving record 15 having the primary key value of 4 is left as it is in the data block 14'. And
In the block position information field 42 of the remaining record control block 34, as shown in FIG.
The value is set and the destination information field 43 of the same block 34 is set.
The destination information indicating the destination of the record 15 having the primary key value of 4 (here, the information including the block number 11 of the destination data block 24 'and the block number 1 of the record control block 35) is set. Now, when the empty space of the data block 14 'is expanded by the record movement accompanying the above block division, the target record 25 is inserted using the empty space as shown in FIG. 1 (b). And the record control block 36 for the same record 25 is set.

FIG. 2 shows the data structure of the indexed sequential organization file after the series of processes following the insertion of the data record 25 described above. However, the index tree of the primary key (index block 17 in FIG. 4) is omitted because it is not directly related to the present invention. In FIG. 2, a data block 14 'having a data record 15 with a primary key value of 8 (width key value of a) is
It corresponds to a data block 15 having a data record 15 with a primary key value of 8 (subkey value a) shown in FIGS. 4 (a) and 4 (b), and in FIG. Data block 1 with two data records 15 with key values c and e)
4'has primary key values 12 and 16 shown in FIGS. 4 (a) and 4 (b).
It corresponds to a data block 14 having two data records 15 (with subkey values c and e). In addition, in FIG.
37, 38, 39 are record control blocks for the record 15 having primary key values of 8, 12, 16 respectively, and their formats are the same as those of the record control block 34 described above.

Now, in this embodiment, in the series of processing accompanying the insertion of the data record 25, even if the block division occurs and the record is moved as described above, unlike the conventional case,
It should be noted that the contents of the transposition block 16 are not changed, more specifically, the index point in the transposition block 16 for the move record 15 having the primary key value of 4 and the sub key value of g is not changed. Therefore, the point of the corresponding index in the transposition block 16 in FIG. 2 points to the record 15 (with respect to the record control block 34) whose primary key value before movement is 4 as indicated by arrow P3. It is possible to refer to the move record 15 according to the contents of the move destination information field 43 of the record control block (here, the record control block 34) as described below without changing the point destination. In this embodiment, the point destination is changed when the moving record is referred to.

Here, the operation of referring to the data record by the irregular access by the alternate key for the indexed sequential file shown in FIG. 2 will be described with reference to a record reference with the alternate key value g as an example.
This will be described with reference to the flowchart in the figure. First, the root block (index block 18 in FIG. 2) of the subkey index tree is searched for the corresponding index in the transposition block 16 of the transposition unit 12 according to the key value (subkey value) (step S1). The index of the transposing unit 12 has a position where a data record (record control block for) having the key value (subkey value) exists as an index value. Corresponding record control block) (step S2). Therefore, in this example in which the sub key value is g, the data block 14 '(the record control block 34 therein) indicated by the arrow P3 is referred to, as is apparent from FIG.

Next, it is determined whether the target record (the record whose sub-key value g is to be referenced) exists in the referenced data block 14 ', or whether the target record does not move due to block division. It is checked by the in-block position information field 42 (see FIG. 1 (b)) of the record control block 34 in the data block 14 '(step
S3). If the null value is not set in the field 42, the target record exists in the area starting from the position of the same data block 14 ′ indicated by the field 42 (the area of the record length indicated by the field 41). The record is referred to (step S4), and the record referencing process ends.

On the other hand, if the NULL value is set in the field 42 of the record control block 34 as in the present embodiment, the target record does not exist in the data block 14 'referred to above, so that the record control in the data block 14' is controlled. The position of the destination (record control block 35) of the target record indicated by arrow P4 in FIG. 2 is checked from the destination information field 43 of the block 34, and the data block 24 '(corresponding record control block 35 therein) Reference (step
S5). Next, the data block 24 'referred to in step S5
Whether or not the target record exists in the data block or the target record does not exist due to the record movement due to the block division, the in-block position information field 42 of the record control block 35 in the data block 24 '(Fig. 1 (b )reference)
(Step S5). The reason for executing this step S5 is that the record moved to the data block 24 'due to the block division is further divided into blocks due to the insertion of a new record in the block 24', and is moved to another block again. Because there is a possibility. Therefore, if the target record does not exist in the data block 24 ', the process returns to step S5 to further refer to the destination data block (the record control block therein).
Then, this step S5 and the determination process of the next step S6 are repeated until the data block in which the target record exists is found.

Now, in this embodiment, in the processing of step S6 for the first time,
It is detected that a target record (record 15 having a subkey value g) is present in the data block 24 '. in this case,
The index having the sub-key value g of the transposed index 16 of the transposing unit 12 points directly to the position (of the corresponding record control block 35 in the data block 14 ') where the target record 15 actually exists, as shown by the arrow P5. , Change the index value (step S7). After this change,
The process proceeds to S4, the target record 15 is referred to, and the record reference process ends. After that, the record reference (record reference due to random access of the sub key value g) to this record 15 (the sub key value of which is g) is the position where the record 15 actually exists due to the corresponding index in the transposing unit 12. The target record in the data block pointed to (as indicated by arrow R5 in FIG. 2) and thus referenced by the value of the index.
Since 15 exists, the steps of the flowchart of FIG.
The process branches from S3 to step S4, and the target record 15 is immediately referenced.

The case where block division occurs due to record insertion and record movement occurs has been described above, but the present invention is not limited to this. That is, according to the present invention, for example, when the data of an indexed sequential file is updated (modify), the record length becomes longer than the original length, so that the record does not fit in the data block, and as a result, block division occurs and record movement occurs. It is also applicable to the above case, and the process of changing the transposed part of the index tree of the subkey when a record move occurs can be eliminated.

[Effects of the Invention] As described in detail above, according to the present invention, when a data record is moved due to block division accompanying the insertion of a record, the information indicating the destination is the corresponding record control block of the original data block. Since it is set in the destination information field of, the omission of the change process of searching for and changing the index to the same record that is set with the subkey value of the moved data record in the transposed index part of the subkey Can also refer to the moved data record. That is, according to the present invention, the process of changing the index of the sub-key value of the moving record in the transposed index portion at the time of moving the record due to the block division can be omitted, so that it is possible to prevent a decrease in the processing speed due to this kind of changing process. . However, if an attempt is made to refer to a moving record by random access using a sub-key value without performing the above-mentioned change processing, it will be an indirect access via the original data block. Therefore, if that record is accessed only once, This is not a problem, but if it is referenced multiple times, the processing speed will be reduced. According to the present invention, however, the above-mentioned change processing is performed when the moving record is actually referred to by the irregular access by the sub-key value. Therefore, the second and subsequent references to the moving record can be performed at high speed, and the moving record that is not referred to can be used. Since the above-mentioned change processing is not performed, useless change processing is eliminated as compared with the conventional method in which the change processing is unconditionally performed at the time of moving records accompanying block division.

[Brief description of drawings]

1 to 3 show an embodiment of the present invention.
FIG. 1 is a data block state transition diagram for explaining a record insertion process when a data record is moved, and FIG. 2 is a diagram showing an extracted data structure of an indexed sequential file after the record insertion process, FIG. 3 is a flowchart showing a processing procedure at the time of referring to a data record due to an irregular access of a subkey value, and FIG. It is a data structure state transition diagram. 11 ... Index part, 12 ... Transposed part (transposed index part), 13 ... Data part, 14,14 ', 24,24' ... Data block, 15,25 ... Record, 16 ... Transposed block, 1
9 ... Empty space, 31,33 to 39 ... Record control block, 42 ... Position information field in block, 43 ... Destination information field.

Claims (2)

[Claims] 1. A record control block prepared for each data record stored in a data block which is a constituent element of an indexed sequential file, wherein the data record corresponding to the record control block is a new data record. Is a record insertion method in an indexed sequential file having a move destination information field for setting move destination information indicating a move destination when moving to a new data block by block division accompanying insertion of the data block When the above-mentioned data record stored in is moved and the above-mentioned new data record is inserted, the move of the record is moved to the move destination information field in the record control block corresponding to the data record before the move. The destination information indicating the destination is set, and the data moved by the block division is set. The data record is referred to according to the setting content of the destination information field in the record control block corresponding to the same record and placed in the data block before the movement of the same record. Record insertion method for indexed sequential files. 2. A record control block prepared for each data record stored in a data block which is a constituent element of an indexed sequential file, wherein the data record corresponding to the record control block is a new data record. A record insertion and reference method in an indexed sequential file having a movement destination information field for setting movement destination information indicating a movement destination when moving to a new data block by block division accompanying insertion of When the above-mentioned data record stored in the data block is moved and the above-mentioned new data record is inserted, the same record is set in the above-mentioned move destination information field in the above-mentioned record control block corresponding to the above-mentioned data record before the move. Set the destination information that indicates the destination of the The data record is referred to according to the setting contents of the move destination information field in the record control block corresponding to the record and placed in the data block before the move of the record by the irregular access by the sub-key value. At the time of referring to this move record, the corresponding index in the inverted index part of the subkey is searched, and the index value is changed based on the setting contents so as to indicate the position of the referred record. Inserting and referencing records in indexed sequential files.