JP2596397B2 - Tree structure data storage method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an information processing apparatus in which a part of data in an external storage device is arranged in a main storage in order to increase an access speed, and particularly to a tree structure data. The present invention relates to a tree structure data storage method in which a part of the data is arranged in a main memory.

[0002]

2. Description of the Related Art Tree data is one type of data structure handled by an information processing apparatus. The tree structure data is obtained by connecting a plurality of nodes in a reverse tree shape with pointers starting from the root node, and is suitable for describing data having a parent-child relationship and a hierarchical relationship. Used in the field.

[0003] In general, when accessing data other than tree-structured data, the data can be accessed at a higher speed when the data is stored in the main storage than when it is stored in an external storage device such as a disk device. For this reason, in an information processing device having an external storage device and a main storage, if all of the tree structure data stored in the external storage device cannot be stored in the main storage due to the limitation of the main storage capacity, The access speed is increased by placing only frequently accessed data of the tree structure data stored in the main memory on the main memory. As a conventional method of deciding data to be arranged on the main memory, there is a method of preferentially arranging data that has been accessed recently, a method of preferentially arranging data that has been accessed so far, and the like. Has been adopted.

[0004]

SUMMARY OF THE INVENTION These prior arts are:
In each case, the future access status is estimated based on the access status up to the present, so that it is necessary to keep a record of the access status every time individual data is accessed, and to replace the main memory data. Sometimes it is necessary to determine the data to be evicted from the main memory by referring to the record of the access status of each data, and there is a problem that the overhead at the time of data access increases.

The present invention has been made to solve such a problem in an information processing apparatus that handles tree structure data. It is an object of the present invention to determine a tree structure data portion to be arranged on a main memory without an overhead at the time of data access. It is an object of the present invention to provide a tree-structured data storage method capable of performing the above operation.

[0006]

According to the present invention, there is provided an information processing apparatus in which a part of data on an external storage device is arranged on a main storage in order to increase an access speed. Targeting the stored tree structure data,
A node arrangement unit that preferentially arranges the nodes having a large number of descendant nodes in the main storage among the nodes is provided.

[0007]

Since the tree structure data is a data structure suitable for describing data having a parent-child relationship and a hierarchical relationship, at the time of access, generally, data closer to the root node tends to be better accessed. That is, in the inheritance in the object orientation, the attribute of the parent node is inherited by its child node. Therefore, in the access for knowing the attribute of a certain node, the parent node also accesses to the root. In a search or the like, a search is started from a root node, so that data closer to the root node tends to be accessed more frequently. The present invention focuses on such a point, and the node arranging unit preferentially arranges, in the main memory, a node having a large number of descendant nodes among the nodes of the tree structure data stored in the external storage device. Thus, the probability that the access destination node exists in the main memory is increased to improve the access speed.

Here, instead of preferentially arranging a node closer to the root node in the main memory, preferentially arranging a node having a larger number of descendant nodes is, for example, two nodes in the root node. Nodes are connected, and one of them has many descendant nodes connected to it, while the other node is a leaf node that has no descendant nodes. This is because if a close node is prioritized, this leaf node is also stored in the main memory.

[0009]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

Referring to FIG. 1, an example of an information processing apparatus to which a tree structure data storage method according to an embodiment of the present invention is applied is as follows.
It comprises a processing device 1 including a CPU, a disk device 2 and a main memory 3 connected thereto, and a node arrangement unit 4 for arranging a part of the tree structure data on the disk device 2 in the main memory 3. ing. The node arrangement unit 4 includes a descendant node number calculating unit 41, a node selecting unit 42, and a node reading unit 43.

FIG. 2 shows an example of tree structure data stored in the disk device 2. In the figure, the portion described on the left side is the tree structure management information of the tree structure data, and in this example, is composed of ten nodes N1 to N10.
The portion described on the right side is the data portion of the tree structure data, and is composed of areas D1 to D10 corresponding to the nodes N1 to N10 on a one-to-one basis. The nodes in the tree structure management information are linked according to the parent-child relationship, and actual data to be held in the individual nodes N1 to N10 are stored in areas D1 to D10 indicated by pointers as indicated by arrows in the drawing. .

Prior to the processing device 1 starting the processing on the tree structure data stored in the disk device 2, the node arranging unit 4 transfers a part of the tree structure data on the disk device 2 to the main storage 3. The tree structure management information arranged in the data section 31 and matching the arrangement state is set in the management section 32. Such an operation is performed as follows.

First, the descendant node number calculating means 41 of the node arrangement unit 4 calculates the number of descendant nodes of each node of the tree structure data stored in the disk device 2. Next, based on the calculation result, the node selecting means 42 selects L nodes in descending order of descendant nodes. Where L
The number is determined by the size of the data part 31, and as many nodes as possible are selected within the range that can fit in the data part 31. Then, the node reading means 43 reads the data of the node selected by the node selecting means 42 from the disk device 2 and stores it in the data section 31 of the main memory 3, and stores the tree structure management information so as to indicate the data of the storage destination. Is stored in the management unit 32.

Thereafter, the processing device 1 starts to manage the management unit 3 of the main memory 3.
2 and performs processing by accessing the tree structure data while referring to the tree structure management information existing in Step 2.

FIG. 3 is a flowchart showing a processing example of the descendant node number calculating means 41 of the node arrangement unit 4. In the figure, in steps S1 to S4, as the nodes are closer to the root node, the node names a _i having the smaller subscripts i are used.
Steps S5 to S8 are processes for calculating the number of descendant nodes of each node. Hereinafter, taking the tree structure data shown in FIG.
Will be described.

The descendent node number calculating unit 41, first, adds the node name a ₁ having a subscript 1 to the node N1 as a route to the node as a target node a _s (S1). Next, name a to all of the node that does not have yet unnamed node adjacent to the node N1, which was granted this node name a _1
k (k is a number sequentially assigned from the number following the number used immediately before) (S2). For Figure 2, since there is no node unnamed node adjacent to the node N1 only N2, to name a ₂ to node N2. Then, one of the nodes not named to the node and adjacent the node with the name and aimed node a _s (S4), the flow returns to step S2. In FIG. 2, step S2 is a node that is not named in the node adjacent and the node with the name, so N2, the node N2 as the target node a _s
Return to

In step S2, all the unnamed nodes adjacent to the node N2 are given names. In FIG. 2, no node unnamed node adjacent to the node N2 N3, N4 so, naming the a _3, a _4, respectively. In step S4, one of the nodes not named to the node and adjacent the node with the name and aimed node a _s (S4), the flow returns to step S2. In the case of FIG. 2, the nodes which are named and whose adjacent nodes have no names are N3, N
4, for example, the node N3 of the node
_{The process} returns to step S2 as _s .

The above operation is repeated, and if it is determined in step S3 that all nodes have been given names, the process proceeds to step S5. FIG. 4 shows names given to the respective nodes in FIG.

Processing S for calculating the number of descendant nodes of each node
In 5 to S8, first, the maximum subscript n (10 in FIG. 2) of the assigned node name is set in the variable t (S8).
5), the name select all nodes with names of larger subscripts than adjacent to and t in a _t, by the following equation to calculate the number of progeny node b _t of the node whose name a _t (S6). Here, the first term of the right side represents the number of child nodes of the node whose name a _t, the second term shows the number of descendant nodes thereof child nodes.

[0020] The name of the number of descendant nodes of the node with a _t b _t
Is calculated, the variable t is decremented by one (S7), and step S
6 is repeated, and the process ends when the variable t becomes 0 (S8).

[0021] In the case of Figure 2, firstly, the above formula (1) is calculated by selecting the node with the name of the larger subscripts than adjacent to and 10 to the node N10 with a node name a _10. In this case, since the node N10 has no child nodes, the node N1
The number of descendant nodes b _t of 0 is 0. Next, the node name a ₉
It is calculated the formula (1) for the node N9 with, the first term on the right hand side 1, the second term 0, the descendant node number b ₉ of the node N9 is one. Hereinafter, nodes N8, N7,
.., N1 in that order. The result is shown in FIG.

The node selecting means 4 in the node arrangement section 4
2 refers to the number of descendant nodes of each node calculated by the descendant node number calculation means 41 as described above, and selects L nodes in descending order of the number of descendant nodes. For example, when five nodes are selected, nodes N1, N2, N3, N4, and N5 are selected in descending order of the number of descendant nodes.

The node reading means 43 in the node arrangement unit 4 reads data of the node selected by the node selecting means 42 from the disk device 2 and
Is stored in the data section 31 and the tree structure management information in which the pointer is changed to point to the data in the main memory 3 is stored in the management section 32 of the main memory 3 for the node from which the data is read out to the main memory 3. I do.

FIG. 5 shows the data of the nodes N1, N2, N3, N4 and N5 in the tree structure data shown in FIG.
2 shows a state when the data section 31 is arranged in the data section 31.

FIG. 6 is a flowchart showing an example of the node processing performed by the processing device 1. Processing apparatus 1, when, for example, want to know the attributes of the nodes N _i, first, examine the data storage destination of the node N _i with reference to the tree structure management information managing unit 32 of the main memory 3, in the main storage 3 If there is (YE in S11
S), reads and processes from the main memory 3 the data of the node N _i (S13). For example, attribute information is obtained from the data. If it is not in the main memory 3 (N in S11)
O), read from the disk device 2 and perform the same processing (S12). Then, this processing node is determined whether the root node (S14), if the root node obtains the adjacent node closer to the current processing node N _i from the root node from the tree structure management information managing unit 32 ,
This was a new node N _i (S15), step S1
Returning to step 1, the above-described processing is repeated. When the processing up to the root node is completed (S14), the current node processing ends.

The embodiments of the present invention have been described above.
The present invention is not limited to the above embodiments, and various other additions and changes are possible. For example, although the node arrangement unit 4 is provided separately from the processing device 1 that accesses and processes the tree structure data, the function of the node arrangement unit 4 may be incorporated in the processing device 1 itself. Also, tree structure data having a maximum of 10 nodes has been described as an example, but this is for convenience of description, and usually is tree structure data composed of more nodes.

[0027]

As described above, the present invention relates to an information processing apparatus in which a part of data on an external storage device is arranged on a main storage in order to increase an access speed. Among the nodes of the tree structure data stored in the device, those having a large number of descendant nodes are preferentially arranged in the main memory. In order to improve the access speed, the tree structure data portion to be arranged in the main memory is designated. This has the advantage that it can be determined without the overhead at the time of data access.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of an information processing apparatus to which a tree structure data storage method according to the present invention is applied.

FIG. 2 is a diagram showing an example of tree structure data stored in a disk device.

FIG. 3 is a flowchart illustrating a processing example of a descendant node number calculation unit.

FIG. 4 is a diagram showing a name given to each node of the tree structure data shown in FIG. 2 by a descendant node number calculating means, and a calculated number of descendant nodes of each node.

FIG. 5 is a diagram showing an example in which a part of tree structure data is arranged in a main storage.

FIG. 6 is a flowchart illustrating an example of a node process of the processing device.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Processing apparatus 2 ... Disk apparatus 3 ... Main memory 31 ... Data part 32 ... Management part 4 ... Node arrangement part 41 ... Descendant node number calculation means 42 ... Node selection means 43 ... Node reading means

Claims (3)

(57) [Claims] 1. An information processing apparatus in which a part of data on an external storage device is arranged on a main storage in order to increase an access speed, wherein the tree structure data stored in the external storage device is A tree-structured data storage method, comprising: a node arrangement unit that preferentially arranges a node having a large number of descendant nodes among the nodes in the main storage. 2. The method according to claim 2, wherein the node arranging unit calculates a descendant node number of each node of the tree structure data stored in the external storage device. 2. The tree structure data storage method according to claim 1, further comprising: a node selecting unit that selects a predetermined number of nodes; and a node reading unit that reads the selected nodes from the external storage device to a main storage. 3. The node reading unit stores tree structure management information including storage destination information of data of each node of the tree structure data on a main memory.
Described tree structure data storage method.