JPH03260867A - Data processing system - Google Patents

Abstract

PURPOSE:To improve the data retrieving efficiency by applying the reformation check to the nodes covering the one higher than a node newly registered into a register list by a rank through the one of the highest rank and then reforming a 2-split tree after confirming the satisfaction of the due conditions. CONSTITUTION:Each node 1 consists of a pointer 1e which points a node higher than one rank, the higher rank node direction 1f which shows whether the higher rank node is set at the right or left side of the node, the depth 1g of the node set in the lower left direction and the depth 1h of the node set in the lower right direction in addition to KEY 1a, DP 1b, LP 1c and RP 1d respectively. When a new node is registered into a register list, the reformation check is applied to the nodes covering the one higher than the registered node by one rank through the one of the highest rank. Thus a 2-split tree having high efficiency is obtained. Thus it is possible to shorten the data retrieving time to the register list and to process the data with high efficiency.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a data processing system that manages data on a main memory using a register having a binary tree structure.

[Conventional technology]

Figure 5 is a conceptual diagram showing the data structure of a register in a conventional data processing system. They are linked together to form a register. This node also has a key value 1a (hereinafter referred to as KEY) that indicates the name of the data loaded in the main memory.
, pointer 1b to the data loaded into main memory
(hereinafter referred to as DP), a pointer IC (hereinafter referred to as LP) to the lower node 1 in the left direction, and a pointer 1d (hereinafter referred to as RP) to the lower node 1 in the right direction. 2 is data on the main memory corresponding to KEYla indicated by the DP1b.

Next, the operation will be explained using the flowchart shown in FIG.

Normally, in data processing, as shown in FIG. 6(a), necessary data is loaded from a storage device such as a disk to the main memory (step 5T2), and this loaded data is used for calculations etc. (step 5T3). The data processing is repeated according to the number statement (step 5TI), but in such data processing, as the number of data increases, the number of accesses to the storage device also increases, and the processing performance decreases, so as shown in FIG. 6(b) As shown in FIG. 1, it is common to process data while managing it in a register as node 1, which is data already loaded on the main memory. In other words, the KEYl of node 1 that constitutes the register determines whether the necessary data has been loaded or not.
Search for and confirm step ST5). If node 1 that matches KEYla of node 1 corresponding to the data is confirmed, the necessary data already exists in the main memory, so do not load it and confirm. Only if possible, the necessary data is loaded from the storage device into the main memory (step ST6), and the node 1 corresponding to the loaded data is registered in the register (step 5T7).

Then, the operation of using the loaded data for calculation etc. (step 5T8) is repeated according to the data processing count statement (step ST4).

Here, the registration operation of node 1 in the registry is shown in Figure 6 (C).
It is done like this. That is, it is determined whether or not the data name to be searched from the highest node to the lowest node of node 1 constituting the registry matches the KEYla of node 1 (step ST9.5T10), and if they match during the search. If this is confirmed, this data already exists in the main memory, so the registration operation is not performed and all nodes 1
The addition of a new node 1 is instructed only when the KEYia does not match (step STI 1 ).

In this way, "Basic lesson "C language" ■Basic acquisition edition"
(Published by Gijutsu Hyoronsha Co., Ltd., p. 170, first edition February 25, 1986), when a registry is generated using a binary tree structure, for example, D.

When data named B, A, F, H, C, and Y are registered in this order, the data is managed as shown in Figure 7 (a) (only the KEYla part is extracted for clarity). ). At this time, when searching for the registered Y, if it is simply registered instead of using a binary tree as shown in Figure 7(b), Y will be registered last, so seven comparisons will be required. However, if the information is registered in consideration of the registration order as shown in FIG. 7(a), only three comparisons are required, which is efficient.

[Problem to be solved by the invention]

Since the conventional data processing system is configured as described above, for example, A, B, C, D, F, H.

If the data is registered in the order of Y, a unidirectional binary tree will be generated as shown in Figure 7 (C), so if the order of data registration is not taken into account, the original merits of the binary tree will not be utilized. . Also, when registering data all at once, it is possible to generate an optimal binary tree, but when registering online and using it immediately (you do not know in what order the data will be registered) Similarly, in cases where there is no tx, there were issues where the benefits of two-minute books were not taken advantage of.

Is this invention as described above? zl! This was done to solve the problem. It prevents the generation of unidirectional binary trees depending on the order of data registration, and even in such cases, it generates efficient binary trees and improves search efficiency. The purpose is to obtain a data processing system.

[Means to solve the problem]

In the data processing system according to the present invention, when generating a binary tree, so that the binary tree is not simply generated in the order of registration,
When a new node is registered in the registry (when a binary tree is generated), a reorganization check is performed for each node from the node one level above this node to the top node, and the decision is made using the skeleton reorganization check. The binary tree is reorganized after confirming that the conditions are satisfied.

[For production]

The data processing system according to the present invention, when a new node is registered in the register, performs a reorganization check on each node from the node one level higher than the node to the top node, thereby creating an efficient binary tree. By generating , data search time in the registry is shortened and data processing can be performed efficiently.

[Embodiments of the invention]

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

FIG. 1 is a conceptual diagram showing the data structure of a register in a data processing system according to an embodiment of the present invention, and is the same as the register (FIG. 5) in a conventional data processing system.
Or equivalent parts are given the same reference numerals and their explanations are omitted.

In the figure, each node 1 is KEYla, DPlb, LP
In addition to lc and RPld, a pointer 1e to the next higher node (hereinafter referred to as HP), and a direction 1f to the higher node indicating whether the higher node is to the left or right of this node (hereinafter referred to as HP). , HD), a node depth 1g in the lower left direction (hereinafter referred to as LD), and a node depth 1h in the lower right direction (hereinafter referred to as RD).

Next, the operation will be explained using the flowchart shown in FIG.

As shown in FIG. 2(a), check whether the necessary data has been loaded by searching the KEYla of the node 1 that constitutes the register (step 5T13), and if the KEYla of the node 1 corresponding to the data is If the node 1 that matches can be confirmed, the necessary data is already present in the main memory, so it will not be loaded, and only if it cannot be confirmed, the necessary data will be loaded from the storage device to the main memory in step 5T14.
), and further registers node 1 corresponding to the data loaded into the registry to generate a new registry (step 5T1
5). Then, the operation of using this loaded data for calculations etc. (step 5T16) is repeated according to the number of data processing statements (step 5T12), but the process from searching this register to creating a new register (
For steps 5TI3 to 5T15), see Figure 2(b)
This will be explained using the flowchart shown in .

In other words, the data name to be searched from the highest node to the lowest node of node 1 that constitutes the registry and the K of node 1.
Step 5T17 to determine whether EYla matches or not.
, 5T18), if a match is confirmed during the search, this data already exists in the main memory, so the registration operation is not performed, and only if it does not match the KEYla of all nodes 1, a new node 1 is registered. Proceed to action. First, make sure to reserve space for the new node in the registry in step 5.
T19), the pointer to this secured area is transferred to the LP of the current node (the next higher node connected by the pointer).
Store in IC or RPld (step 5T20,
If KEYla of terminal node 1 is smaller than the search data, it is stored in RPld; if it is tx, it is stored in LPlc).

Then, set LD1g and RDlh of this new node to 0 (step 8T21), set a pointer to the current node in HPle (step 5T22), and set the direction (right or left) to the current node in HDlf (step 8T23). , LPle and RPId are initialized to 0 (indicating that there are many lower nodes) (step 5T)
24).

Next, when the registration of the new node is completed, first the node becomes 1
LD1g or RDlh of the current node is added by 1 (step 5T26,
If the current node's HDlf points to the left, RDlh
If not, add LD1g). the result,
The difference between LD1g and RDlh of the current node is determined (step 5T27), and if the difference is 2 or more, the following reorganization conditions are checked (step 5T28).

■ The node is the top node.

■ LPlc or RPld of the next higher node is 0
not (t if HDlf of this node indicates left,
plc, otherwise RPld).

■ The difference between RDlg and LDlh of the next higher node is less than 1.

If any of these three conditions is satisfied, the nodes are reorganized (step 5T29), and if they are not satisfied, a reorganization check is performed for the next higher-level node. moreover,
When reorganization is performed, the current node changes, so the Mukuro current node must be reset (step 5T30), and the above operations are repeated from the current node to the top node (
Step 5T25).

Figure 3 is a diagram showing an example of this reorganization, and Figure 3 (a
), the reorganization check is repeated and L is reached at node B.
Since the difference between D1g and RDlh (11 and 9) has become 2 or more, reorganization is performed. In this reorganization, the following seven processes are performed.

■ Store the pointer to node A in HDlf of node C.

■ Store node B's pointer in node C's LPlc.

(2) Store LD1g of node B (added by 1) to LD1g of node C;

■ Store a pointer to node C in node B's LPlc.

■ Node B's HDl indicates that the upper node is in the right direction.
Set to f.

■ Store 0 in RPld of node B.

■ Store 0 in RDlh of node B.

As a result of this process, the data is reorganized as shown in FIG. 3(b).

In the above embodiment, the present invention is applied to the search process of a register for managing data on the main memory, but the present invention may also be applied to the management of transaction scene data.

[Effects of the Invention] As described above, according to the present invention, when a new node is registered in the register, a reorganization check is performed for each node from the node one level above this node to the highest node. Since an efficient binary tree is generated, the time taken to search for data in the registry can be shortened and data can be processed efficiently.

For example, A, B, C-, Y, Z, ZA, ZB.

If 52 pieces of data are registered in the order of ZC..., zy, zz, simply registering them in the binary tree will result in the data shown in Figure 3 (a
) are arranged in a unidirectional manner. Therefore, when searching for 22 items, 52 comparisons and determinations are required. However, in the data processing system according to the present invention, an efficient binary tree is constructed as shown in FIG. 3(b), and even when searching for 22 items, only 19 comparisons are required.

[Brief explanation of drawings]

FIG. 1 is a conceptual diagram showing the data structure of a register in a data processing system according to an embodiment of the present invention, FIG. 2 is a flowchart explaining the operation of the data processing system according to the present invention, and FIG. A conceptual diagram illustrating the reorganization of binary trees constituting a book, FIG. 4 shows a binary tree generated in a conventional data processing system and an example of a binary tree generated in the data processing system of the present invention. 5 is a conceptual diagram showing the data structure of a register in a conventional data processing system, and FIG. 6 is a flowchart explaining the operation of the conventional data processing system.
FIG. 7 is a diagram showing an example of binary tree generation generated in a conventional data processing system. In the figure, 1 is a node and 2 is data. In addition, in the figures, the same reference numerals indicate the same or corresponding parts. (De/') 1 ) No. o1 \ \ Figure \ W Y No. 5 Fig. 0 ('t no 3 ) No. (b) (Z no 2) No. 1 cl

Claims (1)

[Claims] A binary tree structure register consisting of nodes corresponding to each data on the main memory that has already been loaded is searched, only data that has not been registered is loaded, and the newly loaded data is loaded into the register. In a data processing system that registers and manages nodes, when a node of loaded data is registered in the register, a reorganization check is performed for each node from the node one level higher than the node to the highest node. A data processing system characterized in that the binary tree is reorganized after confirming that conditions determined by the reorganization check are satisfied.