JPH0524549B2 - - Google Patents

Description

Detailed Description of the Invention [Field of Application of the Invention] The present invention relates to an information retrieval mechanism using a balanced tree in a computer system consisting of an arithmetic processing unit, a main storage device, an auxiliary storage device, and an input/output device. An information retrieval method that can quickly add and delete information.

[Prior art]

BACKGROUND ART Balanced trees have conventionally been used in digital computer systems to search for information corresponding to a key. The representative one is B
-Tree (B-Tree), and various modifications of B-Tree are also being considered.
For B-Tree, see Do Comer: “The
Ubiqitous B-Tree”ACM Computing
See Surveys, Vol. 11, No. 2, pp 121-138. A typical variation of B-Tree is B ⁺ −Tree.
and is widely used.

Now, let's consider adding a key to a Node whose B ⁺ −Tree is full of entries. In this case, keys can be added by securing a new Node and moving half of the keys from the full Node to the new Node. This normal process is called Split processing. When performing split processing, it is necessary to also update the parent node of the target node.

On the other hand, in B ⁺ -Tree, the number of entries in a Node is controlled to be between half of the order, that is, the maximum number of entries that can fit into the Node and the maximum number of entries. Therefore, if the number of entries becomes less than the order by deleting an entry, the neighboring
Processing is required to accommodate entries from a node or merge neighboring nodes, and at this time, it is performed to update the parent node in the same way as Split processing.

Traditionally, when updating the parent Node,
Retracing from RootNede (root node),
I was looking for a Node that contains a pointer pointing to the relevant Node. Usually trees are stored on a supplementary storage device such as a magnetic disk device (abbreviated as disk), so
Auxiliary storage to trace back from the Root Node,
access was required, which caused performance problems.

[Purpose of the invention]

The purpose of the present invention is to use a balanced tree such as B ⁺ -Tree, which may require update processing up to the parent node when adding or deleting a key.
The purpose is to speed up the process of searching for nodes and speeding up the process of adding and deleting keys.

[Summary of the invention]

In a balanced tree such as B ⁺ −Tree, before adding or deleting a key, the Leaf Node that should contain or contains the key is checked.
It is necessary to trace from the root until
At this time, enter the Node number (number to identify the Node) from the Root Node to the applicable Left Node.
Stored in a table on the main storage in order from Root,
When the Node number of the parent Node is needed, this table is searched to find the corresponding Node number. The Node number stored before one of the cases containing the corresponding Node number in this table is the parent
This is the node number of the node. In this way, the parent node can be known quickly.

[Embodiments of the invention]

An embodiment of the present invention will be described below with reference to FIGS. 1 to 11. FIG. 1 shows the overall configuration of the present invention. 1 is a magnetic disk device (hereinafter abbreviated as disk), 2 is an index file consisting of B ⁺ -Tree, 21 is a bit map that manages the used and unused nodes in the index file by turning on and off bits, and 22 is B ⁺ −This is the part that contains the body of the Tree. 201 to 208 constitute B ⁺ -Tree
Node, 201 is Root Node, 208 to 208
is a Leaf Node. 3 is a file label area, and 31 to 32 are file labels. The file label contains the file sector address in 311, bitmap management information in 312, and bitmap management information in 313.
Node number of Root Node (i.e., B ⁺ −Tree
(numbers assigned to Nodes in order from the beginning of the area of the main body 22), the key length in 314, and the record size in 315.

4 is a main memory, 5 is a group of programs for the system that controls B ⁺ -Tree, 51 is a program for adding entries, 52 is a program for deleting entries, and 53 is a program for searching for entries. 54, 55 are
This is a subroutine used by programs 51 and 52, and 55 is a program that registers the Node number of the node that reached the NNLT, which will be described later.
This is a program to get the Node number of a Node's parent.

Hereinafter, 54 is the Node number registration program, 55
Calls the parent Node number checking program.

Up to now, we have expressed this as adding or deleting a key to a tree, but more accurately, it is more correct to express this as adding or deleting an entry consisting of a key and a record, and henceforth we will use the latter. 8 is a buffer for reading nodes and bitmaps on the disk. 6 is the area containing the user program, 61 is the user program body, B ⁺ -
The programs 51 to 53 that control Tree are called.
62 is the key for checking/adding or deleting; 63 is the key to check/add or delete.
is an area where each record to be added is set, and desired processing can be performed by passing these addresses to the B ⁺ -Tree control program. 7 is a table called NNLT (Node Number List), which stores node numbers in order from the beginning when tracing B ⁺ -Tree from the Root Node to the Leaf Node containing the target key.

Intermediate information of processing of the B ⁺ -Tree control program is stored in 64 to 68. 64 stores the key of the entry to be added. 64 is the record body of the entry to be added or the Node of the child Node.
Remember the number. 66 is eligible for entry addition
Memorize Node's Node cipher.

67 is the relative entry number within the node of the entry to be deleted, and 68 is the entry to be deleted.
Memorize each node's Node number.

Figure 2 shows the detailed structure of Node. 9 is Node
Root Leaf or other
The length is fixed to 1 sector regardless of whether it is a node or not. 91 is an area containing node control information and has a fixed length. 92-93 are entries. The entry contains the keys indicated by 921 and 9.
Contains the record indicated by 22 (when it is a Leaf Node) or the node number of the lower node (when it is not a Leaf Node).

911 is the node number of the node on the right, 91
2 is the number of entries included in Node, 913
914 stores a flag indicating whether the node is a Root Node, and a flag 914 indicating whether the node is a Leaf Node.

The number of entries in a Node is controlled to be between the maximum number of entries that can fit in the Node and an order that is 1/2 of this value.

Based on the above description of the configuration, entry addition and deletion processing will be described below, and this method will be explained in detail, as well as the effectiveness of this method.

FIG. 3 shows a flowchart of a program for adding entries. This flowchart will be explained based on the example of B ⁺ -Tree shown in FIGS. 4 and 5.

First, consider adding an entry with a key value of 25 to B ⁺ -Tree shown in A of FIG. 4. Here, A in Fig. 4 is B ⁺ -Tree before addition, B is B ⁺ -Tree after addition, 211 is Root Node, Node number i is, 212 to 215 are Leaf Nodes, and Node
The numbers are j, k, l, and m, respectively. At step 101 in FIG. 3, all cases of NNLT shown at 7 in FIG. 1 are cleared to zero. At 102 in FIG. 3, the Node number of the Root Node, i in the example of FIG. 4, is obtained from the first 313. At 103 in Figure 3, the sector address on the disk of Node number i is determined based on the information on the file label shown at 31 in Figure 1, as is normally done in file management. Read Node in the system buffer number 8 in Figure 1. Read at 104 in Figure 3.
Register Node number i of Node to NNLT.

This process is performed by the Node number registration program shown at 54 in FIG. Details of NNLT and Node number registration program are shown in Figures 9 and 10.

In FIG. 9, 7 is the NNLT as a whole, and each case 71 to 77 consists of 4 bytes, and case numbers are assigned sequentially starting from 71. 71 stores the number of nodes registered in NNLT. 72-7
In 7, the Node numbers when tracing the B ⁺ -Tree from the Root Node to the Leaf Node containing the target key are entered in order from the beginning. The maximum number of nodes that can be registered is
Depending on the number of cases in the NNLT, this value only needs to be equal to the maximum number of stages of B ⁺ −Tree that can be assumed,
Here, 15 cases are fixed due to the maximum file size.

Figure 10 shows a flowchart of the NNLT registration program. At 701, 1 is added to the number of registered nodes of the NNLT (stored at 71 in FIG. 9). In this case, since it was initially 0, the number of registered nodes becomes 1 after the processing in 701 is completed.

In step 702, the NNLT start address is multiplied by the number of registered nodes and the number of bytes per case, 4, to obtain the address of the NNLT case to be registered. In this case, the address for the case shown at 72 in FIG. 9 is calculated.

At 703, a designated Node number is set for the case whose address was calculated at 702. In this case, Root
Node number i is set in case 72 in FIG.

Leaf of the node read at 105 in Figure 3
Referring to the Node display (indicated by 914 in FIG. 2), it is determined whether it is a Leaf Node. in this case,
Since it is not a Leaf Node, it jumps to 106 in Figure 3. In step 106, the entry keys in the read Node are compared in order from the first entry to find an entry whose key value exceeds the key value of the first entry to be added. In this case, the first entry with a key value of 30 corresponds. From the pointer value of this entry (generally indicated by 922 in Figure 2) to
Get the Node number of the Node, in this case j. After this, return to 103 in Fig. 3 and select the lower Node, that is, the Node.
Read in the system buffer, and at 104, Node
Register the Node number j of the Node that called the number registration program in the NNLT. In this case, j is set in case 73 in Figure 9, and registration in case 71 is
The number of nodes is 2. In 105, Leaf
Since it is a Node, proceed to 107, and here, the first
For the works shown in 64 to 66 in the figure, set the key of the entry to be added (i.e. 25), the record and the node number of the node to which the entry is added (i.e. j). In this way, in 131 to 137, Leaf where the entry should go
Trace from Root to Leaf to Node.
Register the Node number traced to this point, and set information regarding the entry to be added to the work.
NNLT looks like C in Figure 4.

At 108 in Figure 3, the number of entries currently in the Node (stored at 912 in Figure 2) and
Compare the number of entries that can fit into Node. Node
The number of entries that can be entered is the entry length, which is the sum of the key length and record length for Leaf Nodes, and the sum of the key length and the fixed 4-byte length of the area for storing pointer values for non-Leaf nodes. ,
It is calculated by dividing the value excluding the length (fixed value) of the part containing the control information of the node. In the case of A in FIG. 4, the current number of entries is 4 and the number of entries that can enter the node is 4, so in the determination at 108 in FIG. 5, the process proceeds to 109. In 109,
Root display in Node control information (91 in Figure 2)
Indicated by 3. ) and make sure the node to be added is Root.
Determine whether it is a Node. In this case, since there is no Root, proceed to 110. ) Here, an empty node is obtained by referring to the bitmap shown at 21 in FIG.
In this case, the node indicated by 216 in B of FIG. 4 is the newly secured node, and the node number is n.

For 111 in Figure 3, entries are to be added.
The second half of the Node entry is the newly secured Node.
Move to. After that, compare the key of the entry to be added and the maximum key of the Node containing the entry in the first half, and if the entry to be added is larger, the entry is added to the newly secured Node. if,
If the entry to be added is smaller, it is added to the Node that contains the first half of the entry. In this case, an entry is added to the Node indicated by 216 in B of FIG. This process is called Split process.

At 113 in Figure 3, the parent node number search program is called and the parent node of the node that caused the split is called.
Obtain the Node number from NNLT7. parent
A flowchart of the Node number search program is shown in FIG. This flowchart will be explained by taking as an example the case where the NNLT is shown in C of FIG. Here, the node number of the entry addition target node is j.

At 801 in Figure 11, the counter (which can be an area on main memory or a register) is set to NNLT.
Set the number of registered nodes, in this case 2. At 802, the address of the +1st case (in this case, 73 of C in FIG. 4) is calculated, and at 803, the address of 802
is stored in the case where the address was calculated in
Compare the Node number (j in this case) with the specified Node number (j in this case). In this case, it matches, so jump 805, and the NNLT-th case (in this case, the case shown by 72 in C in Figure 4)
The Node number (i in this case) of the parent node can be obtained from . If there is no match at 803 in FIG. 11, the process advances to 804, the counter is decremented by 1, the process jumps to 802, and the search processing for the case in which the specified Node number is stored is continued. In this way, you can obtain the node number of the parent node of the specified node.

At 114 in Figure 3, the value obtained at 113 is
Read the parent node by Node number and caused a Split
The pointer of the entry in the parent Node that was pointing to the Node is changed to the pointer of the entry in the parent Node that was pointing to the Node.
Change to Node number. In other words, parent Node 21 that was pointing to Node 212 at A in Figure 4
The value j of the pointer of entry No. 1 is changed to n as shown in B of FIG.

At 115 in FIG. 3, additional entry information for adding a parent node to an entry pointing to the addition target node is created. In this case, the key value is 15, the pointer value j, and the node number to be added is i. After this process, return to 108 and again
Starts the process of adding an entry to Node.
In this case, the number of nodes to be added is full, so 109
Proceed to. Since the node to be added at this time is the Root Node, the process jumps to 117. At 117,
Two nodes are secured, one for the Split processing node shown at 217 in B of FIG. 4, and one for the new root node shown at 218. 118 and 119 are the split processing described above. At step 120, the current Root Node is no longer the same, so the root display of the node shown at 211 in B of FIG. 4 is cleared. At 121 in Figure 5, there is a new Root containing two entries pointing to the two Split Nodes.
Create a node. 122, in the file label
The pointer to the Root Node (indicated by 313 in FIG. 1) is updated to the new Root Node. As a result, the shape of B ⁺ -Tree becomes as shown in B in FIG.

In this way, it is necessary to change the parent node in the Split process, but it is necessary to change the parent node from Root to Leaf in NNLT.
By memorizing these Node numbers when tracing to a node, the parent node number can be obtained without tracing back from the Root Node, and entry addition processing can be performed at high speed.

A case where split processing is not necessary will be explained using FIG. 5. Consider the case where an entry with a key value of 15 is added to B ⁺ -Tree in A in FIG. 10 in Figure 3
1 to 107, trace from the Root to the Leaf Node to which an entry is to be added, register these node numbers in the NNLT, and set additional entry information on the work. At 108 in Figure 3, the number of entries in the Node is 3 and it is not full, so 116
Go to , add an entry, and finish the process. As a result, B ⁺ +Tree becomes as shown in B in Fig. 5.
In this case, there is no need to update the parent node.

Entry deletion processing will be explained using FIGS. 6 to 8. First, consider deleting an entry with a key value of 10 from B ⁺ -Tree in A of FIG. A is B ⁺ −Tree before deleting the entry, B is after deleting the entry
It is B ⁺ Tree. In Figure 7, 501 is Root
Nodes, 502, 503, 504 and 505 are
Leaf Node, and the node numbers are i,
j, k, l and m.

In Figure 6, in steps 401 to 403, the process is traced from the Root Node to the Leaf Node containing the deleted entry in the same way as in the process of adding entries, and the traced nodes are
Register the Node number to NNLT. As a result
NNLT looks like C in Figure 7. At 403,
67 in Figure 1 shows the deletion entry information, that is, the relative entry number within the node of the entry to be deleted, and 6
8, set the Node number of the node to be deleted.

At step 404 in FIG. 6, the number of entries in the deletion exercise node is compared with the order, that is, 1/2 of the maximum number of entries that can fit in the node. The maximum number of entries is determined by the method described in the section on adding entries. In this case, the number of entries in the Node is 2, which is the same as the order, so the process advances to 405.

Entry to be deleted at 405 in Figure 6
Determine whether the Node is the Root Node. This is done in the same way as adding an entry. In this example in Figure 7, it is not the Root Node, so it is 406
Proceed to.

In step 406 in Figure 9, the parent node number search program is called to search for cases where the NNLT node number is stored and to delete the entry.
Find the case where Node's Node number is stored, and find the case that is in the case immediately before this case.
Get the Node number. This is the node number of the parent node. In this case, the NNLT of C in FIG. 7 is searched by j, and the node number i containing the case immediately before the case containing j is the parent node number.

Read the parent Node at 407.

At 408 in FIG. 6, the deletion target node is selected from the entry next to the entry pointing to the deletion target node in the parent node. Here, at 503 in FIG.
Get the Node number R of the Node next to Node and use this
Load Node into the system buffer. In step 409, the number of entries in the node just read, 3 in this case, is compared with the order, 2 in this case. Since the number of entries is greater than the order, the process advances to 410.

At 410 in Figure 6, 50 at A in Figure 7
Nodes 1,502 and 503 are set like Nodes 501, 502 and 503 in B of FIG. In other words, deletion entry information (67 in Figure 1,
It is stored in 68. ) After deleting the entry specified by
Ensure that the number of entries in is not less than the order. This process is called balancing process. This completes the entry deletion process. As a result, B ⁺ −Tree
becomes like B in Figure 7.

Consider deleting an entry with a key value of 70 from the B ⁺ -Tree in FIG. 8.

In FIG. 6, the same processing as in the example of FIG. 7 is performed in steps 401 to 407. However, NNLT becomes as shown in Figure 8C, 601 and 603
Node is loaded into the system buffer. 40
In step 8, get the Node number of the next Node from the entry next to the entry of the target Node in the parent Node, and
Load into the Node system buffer.

At 409 in Figure 6, the number of entries of the adjacent Node and
Compare with order. In this case, the number of entries is 2.
Since the order is 2, it jumps to 411. In 411, after deleting the specified entry,
Move the remaining entries to the Node on the left, and
is returned as an empty Node. This process is called merging process.

The maximum key of the Node to which the entry was transferred changes due to the merging process at 411 in FIG. 6. In other words, the maximum key of Node 602 in ^FIG . (Keys added to B ⁺ −Tree in advance)
, update the key of the entry pointing to this Node in the parent Node to the new maximum key in the Node, and delete the entry pointing to the deleted Node. Set the information to 67 and 68 in FIG. In this case, the intra-node relative entry number 2 of the deletion entry is set in 67, and the node number i of the deletion target node is set in 68.

The process returns to step 404 to delete the entry pointing to the node deleted from the parent node in FIG.
At 404, the number of entries in the Node is 2, which is equal to the order, so the process proceeds to 405. Targeted at 405
Since the Node is the Root Node, it jumps 413. At 413, the target node is not a Leaf Node, so the process proceeds to 414. Target Node in 414
Since the number of entries within is 2, the process advances to 415. NoNode merged into one in 415
as the new Root Node, and set the old Root Node as the new Root Node.
to be returned. As a result, B ⁺ -Tree becomes as shown in B in FIG.

On the other hand, if the number of nodes is one B ⁺ -Tree and the number of entries is less than the order, 40 in Figure 6.
Processing progresses from 1 to 405, 413, and 4 at 413.
The process jumps to 16, deletes the specified entry, and ends.

Also, the Leaf Node containing the entry to be deleted
If there are more entries than orders, then
In FIG. 6, the process progresses from 401 to 404, and 404
The process jumps to step 416, deletes the specified entry, and ends the process.

Additionally, deletion of entries from subordinate Nodes
If the ripple effect extends to the Root Node and the number of entries in the Root Node is 3 or more but less than the order, the process jumps to 416 at the determination of 414 in FIG. 6, the entry is deleted, and the process ends. This is the Root Node
This is because the number of entries in is also allowed to be less than the order.

In this way, even in entry deletion processing, when merging and balancing, it is necessary to update the parent node. At this time, just search for NNLT,
You can get the node number of the parent node.

〔Effect of the invention〕

In split processing by adding entries to B ⁺ −Tree and balancing or merging processing by deleting entries, processing target
A Node's parent Node must be referenced and updated. According to the present invention, the parent node can be known without retracing from the Root Node, and the parent node can be determined at high speed.
It is now possible to refer to or update B ⁺
- Enables high-speed processing of adding and deleting entries to the Tree.

[Brief explanation of the drawing]

Fig. 1 shows the overall configuration of the present invention, and Fig. 2 shows the overall structure of the present invention.
The internal structure of Node is shown, and Figure 3 shows the flow of a program that adds an entry to B ⁺ -Tree.
Figures 4 and 5 show an example of adding an entry to B ⁺ -Tree, Figure 6 shows the flow of a program to delete an entry from B ⁺ -Tree, and Figures 7 and 8 show an example of adding an entry to B ⁺ -Tree. An example of deleting an entry from Tree is shown. Figure 9 is NNLT, Figure 10 is
A flowchart of a program for registering a Node number in the NNLT, and FIG. 11 shows a flowchart for a program for searching a parent Node number from the NNLT. 1...Magnetic disk device, 2...File composed of B ⁺ -Tree, 21...Bit map for managing area within the file, 22...B ⁺ -
Tree body, 3... File labels, 4... Main memory, 5... Programs that manage B ⁺ -Tree, 51... Program that adds entries to B ⁺ -Tree, 52... B ⁺ -Tree 53...Program to search for B ⁺ -Tree, 54...Node number registration program, 55...Parent Node number search program, 6...
...User program area, 61...User program, 7...NNLT, 8...System work area, 9...Node, 91...Node control section, 92, 93...Entry, 10...
B ⁺ -Tree entry addition program, 211~
215, 310-304, 501-505 and 601-603... Nodes of B ⁺ -Tree.

Claims (1)

[Scope of Claims] 1. In an electronic computer system comprising an arithmetic processing unit, a main memory, an auxiliary storage device, and an input/output device, the auxiliary storage device stores a balanced tree for retrieving information using keys; A table storing identification information for identifying nodes traced from the root node to the leaf nodes for the balanced tree is stored in the memory, and the table includes the number of registered nodes and the balanced tree as the identification information. , the node numbers traced from the root node to the leaf node containing the target key are stored sequentially in order of case number, and when the identification information of the parent node of the node being processed is needed, it is used as a counter. a process for setting the number of registered nodes; a determination process for determining whether the node number stored in the +1st case matches the specified node number; and +1 if the determination results match. An information retrieval system characterized in that the node number stored in the second case is set as the node number of the parent node, and if the determination results do not match, a counter is decremented by 1 and the determination process is performed.