JPH052607A - High-speed search method using tree-structured data structure - Google Patents

Abstract

(57) [Abstract] [Purpose] By constructing a data structure that does not require redundant and redundant comparisons at the time of information search, and that can effectively utilize the comparison results at the time of information search to perform high-speed information search. ,
Improves performance when searching for information. [Structure] When a plurality of identifiers (keys) for identifying data are registered in a data structure for searching, each key is divided into blocks of a size that facilitates comparison. Then, the key comparison is performed for each block from the first block, and when the first block of the key is the same and the second block of the key is different, only one block of the same part is held and different. The partial blocks are connected by a pointer and held so as to form a tree-structured data structure.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data structure, and more particularly to a data structure capable of registering and searching information at high speed.

[0002]

2. Description of the Related Art Conventionally, hashing or a tree structure has been used as a data structure for efficiently implementing information registration and search. In the data structure using hashing, when the estimated value of the amount of generated data is known in advance, it is possible to create a data structure that obtains good performance. However, it is known that the tree structure is preferable when the amount of data is difficult to predict and varies considerably. The conventional tree data structure includes a binary tree, an AVL tree, an optimal tree,
There are various trees such as B tree, 2-3 tree, SBB tree,
In each case, the key must be completely held at the branch of the tree branch or the tip of the tree branch (hereinafter referred to as a node). In many cases, the information search key is not something that can be compared to determine the size by a single comparison like an integer, but a character that cannot be determined if it is divided into multiple times and compared like a character string. Is. However, in the conventional tree structure, each time the pointer is traced and a new node is reached, the keys must be compared again, and it is completely conceivable to reduce the number of key comparisons that cannot be compared in one comparison. Not not. Also, in the conventional tree structure, which of the two pointers is to be traced is determined by two pieces of information, which are larger or smaller, among the information obtained by comparing the keys at the nodes. Of the information obtained by comparing the keys,
There is no idea of how to select and trace one pointer from two or more pointers by using more detailed information on how much is equal and where is different.

[0003] Related to this kind of technology, for example, is ANSI (American National Standard for Information Systems: A).
merican National Standard for information s
ystems) database language: database langua
ge-SQL (standard number X3.135-1986).

[0004]

In a data structure having a key in each node in a tree structure in a complete form, a pointer is used when searching for a target key or a key insertion position from the root of the tree structure. At each node until the desired key is reached, the key at that node is compared with the key you are looking for. Some keys are usually long and some are short. Therefore, it is not possible to compare the key at the node with the key you are looking for in a single operation. The key is divided and compared multiple times, and which pointer is traced is determined by the comparison result (size of key). In most cases.
Therefore, when multiple keys are registered with the same beginning and different endings (when registering a lot of keys, this situation will always occur), the comparison at these nodes The problem arises that the same part at the beginning of the key has to be recompared each time.

When the key is divided into a plurality of blocks by comparing the keys at the nodes and the comparison is made from the first block, the obtained information is where the blocks are equal but where the subsequent blocks are large. Or information that it is small is obtained. However, in the conventional tree structure, only the information about whether the key is large or small is used when the pointer is traced based on the comparison result of the keys at the nodes, and the information obtained by the comparison at the nodes is fully used. There is a problem that there is no.

An object of the present invention is to solve such a problem, to minimize unnecessary comparison even when there is a key having the same key at the beginning and a different key at the rear, and comparing keys at nodes. It is to provide a data structure capable of improving the performance of information search by fully utilizing the information obtained in.

[0007]

In order to achieve the above object, in the data structure (tree structure) of the present invention, when a plurality of keys are registered, each key is divided into blocks of a size easy to compare. , The key comparison is performed for each block from the first block, and when the first block is the same and the second block is different, only one block of the same part is retained and blocks after the different part are retained. It is characterized by holding it by connecting it with a pointer so that it becomes a tree-structured data structure.

[0008]

In the data structure of the present invention, the node pointed to from the node is compared with the key set in the node that is the point of origin from the beginning, and only the blocks after the point where they differ are compared. Is set. For this reason,
If the beginning part of the target key and the key set in the node are the same, but the back part is different, in the key comparison at the next node pointed from that node, the key comparison at the previous node is Only the comparison after the point where the different parts appear should be performed. Therefore, when a plurality of keys having the same head portion but different tail portions are registered, it is not necessary to perform unnecessary comparison at each node when searching for a key.

Further, in the data structure of the present invention, each node has a plurality of blocks, and each block has a pointer. Then, when searching for a key, it is possible to determine which pointer is to be traced from two or more pointers by comparing the keys at the nodes and determining which block is the same and which block is different. As a result, the information search performance is improved.

[0010]

Embodiments of the present invention will now be described in detail with reference to the drawings. FIG. 1 is a diagram of a data structure when seven keys are registered in the data structure according to an embodiment of the present invention. FIG. 2 is a diagram showing details of the configuration of nodes in the data structure of FIG. In FIG. 2, 1 is an area in which one or more continuous blocks are set, 2 is an area of a pointer held for each block, blocks before the block are equal, but blocks after the block are different, and It is an area of a pointer (hereinafter, referred to as a left pointer) to a node indicating a key having a block having a value smaller than the value of the block. Reference numeral 3 denotes an area of a pointer held for each block. A pointer to a node indicating a key having a block which is equal to the block before the block but different from the block after the block and has a value larger than the value of the block. This area (hereinafter referred to as the right pointer) is the area.

FIG. 1 shows A, B, C, D, E, F, and G.
7 shows the data structure when the seven keys are registered. Root 4 is a pointer indicating the node of the root of the tree structure. A [n] indicates the nth block of the key A,
Similarly, B [n], C [n], ... G [n] indicate the nth block of each key. NIL is a block indicating the end of the key. The NIL is provided to enable variable-length key registration, and NIL is not necessary when only fixed-length key registration is performed. Table 1 shows the lengths (number of blocks) of the keys registered in the data structure of FIG. Table 2
Shows the magnitude relationship of each key.

[0012]

[Table 1]

[0013]

[Table 2]

First, this data structure will be described by showing the procedure for registering a key in this data structure. In the state where no key is registered, 0 is set in the root4 indicating the root of the tree. When registering key A in this state, set the address of node 5 to root4 and
Set all blocks of key A to. After the block of A [5], NIL indicating the end of the key A is set.

Next, when registering the key B in this state,
First, the key A set at the node 5 pointed to by root4
Then, the key B to be registered is compared from the beginning. Key A and key B are different from the first block,
B [1] is smaller than [1]. Therefore, the pointer on the left of A [1] is checked. Since nothing is set in the pointer, a new node 6 is created, the address of node 6 is set in the pointer on the left of A [1], and key B is set in node 6.
Set.

Next, when registering the key C in this state,
First, the key A set at the node 5 pointed to by root4
And the key C to be registered is compared from the beginning. Key A and key C are different from the first block,
C [1] is larger than [1]. Therefore, the pointer to the right of A [1] is checked. Since nothing has been set in the pointer, a new node 7 is created, the address of node 7 is set in the pointer to the right of A [1], and key C is set in node 7.
Set.

That is, the keys A, B, and C are 1
The second block is different, but the data structure of the binary tree is composed of comrades.

Next, when registering the key D in this state,
First, the key A set at the node 5 pointed to by root4
And the key D to be registered is compared from the beginning. The key A and the key D are the same in the first, second, and third blocks, but are different in the fourth block from A [4] to D.
[4] is larger. Therefore, the pointer to the right of A [4] is checked. Since nothing is set in the pointer, a new node 8 is created and the address of the node 8 is set in the pointer to the right of A [4]. The key D is set at the node 8, and at that time D [1], which is equal to the block of the key A,
D [2] and D [3] are not set, and only blocks after D [4] different from the key A are set.

Next, when registering the key E in this state,
First, the key A set at the node 5 pointed to by root4
Then, the key E to be registered is compared from the beginning. The key A and the key E are the same in the first, second, and third blocks, but are different in the fourth block from E [4] to E.
[4] is larger. Therefore, the pointer to the right of A [4] is checked. Since the address is set in the pointer on the right of A [4], the key D set in the node 8 pointed to by the pointer is compared with the key E to be registered. Here, since the pointers on the right side of A [4] are set only to the keys in which the first to third blocks are equal to the key A, the comparison of the keys at the node 8 indicates that the first to third blocks are the same. No block comparison is necessary. Comparing E [4] and D [4], E [4] is smaller than D [4]. Therefore, the pointer on the left of D [4] is checked.
Since nothing is set in the pointer, a new node 9 is created, and the address of the node 9 is set in the pointer to the left of D [4]. The key E is set at the node 9, and at that time, E [1], E equal to the blocks of the key A and the key D are set.
[2] and E [3] are not set, and only blocks after E [4] different from keys A and D are set.

That is, in this data structure, a binary tree is constructed by keys having the same up to the n-th block and different n + 1-th and subsequent blocks. At this time, only one block up to the nth block is held and shared. There is a feature in that.

Next, a special case that occurs only when a variable-length key is registered will be described. When registering the key F while the keys A, B, C, D, and E are registered, first, r
The key A set at the node 5 pointed by the boot 4 and the key F to be registered now are compared from the beginning. The key A and the key F are different from the first block, and F [1] is larger than A [1]. Therefore, the pointer to the right of A [1] is checked. Since the address is set in the pointer on the right of A [1], the key C set at the node 7 pointed to by the pointer and the key F to be registered from now on.
To compare. The keys C and F are the same in the first and second blocks, but the key C has only two blocks.
Key F consists of four blocks. Therefore, the block NIL indicating the end of the key C is compared with F [3], and (NIL
Is F [3] is larger than NIL (assuming that each block has a value smaller than the value of any block), the pointer to the right of NIL indicating the end of key C is checked.
Nothing is set in the pointer to the right of this NIL, so a new node 10 is created, and the address of node 10 is set to the pointer to the right of NIL indicating the end of key C. The key F is set at the node 10, but F [1] and F [2], which are equal to the block of the key C, are not set at that time, and only the blocks of F [3] and subsequent blocks different from the key C are set. ..

Next, when the key G is set in the above state, first, the key A set at the node 5 pointed by the root 4 and the key G to be registered are compared from the beginning.
Key A and Key G are different from the first block,
G [1] is smaller than A [1]. So A
Check the pointer to the left of [1]. Since the address is set to the pointer on the left of A [1], the key B set at the node 6 pointed to by the pointer is compared with the key G to be registered. Key B and key G have the same first block, but key B has four blocks and key G has only one block. So key G
The block NIL indicating the end of B is compared with B [2], and B
Since NIL is smaller than [2], the pointer to the left of B [2] is checked. Since nothing has been set in the left pointer of B [2], a new node 11 is created, and the address of the node 11 is set in the left pointer of B [2]. The key G is set at the node 11, but G [1] equal to the block of the key B is not set at that time,
Only NIL indicating the end of the key G is set.

As described above, in this data structure, a variable length key can also be registered by using the block NIL indicating the end of the key. In addition, since the n-th block is the same and the n + 1-th block and thereafter are different keys, a binary tree is formed, so that no unnecessary comparison of overlapping parts is required when searching for a target key. .. Furthermore, these keys that make up the binary tree share up to the nth block and hold only one, so there is no need to set multiple duplicate data and the time to create the data structure is shortened. It

In this data structure, the procedure for searching for a target key from the already registered keys is as follows when searching for a new node to be added when registering the key shown above. The target key can be searched by following the pointer in the same procedure. Also in this case, there is no wasteful comparison of overlapping portions, and the key search time is shortened.

Next, a procedure for deleting a target key from this data structure will be described. When deleting a key, first find the node in which the key to be deleted is set by the key search procedure shown above. The key deletion procedure differs depending on the state of the pointer set at the node.
First, the deletion procedure when no pointer is set at the node where the key to be deleted is set will be described. In this case, the pointer pointing to the node where the key to be deleted is set may be cleared. For example, when deleting the key E from the data structure of FIG. 1, a key search is performed,
It can be seen that the key E is set at the node 9. Since the node 9 is pointed to by the left pointer of D [4] of the node 8, if the left pointer of D [4] of the node 8 is cleared, the node 9 is deleted from the data structure and the key E is deleted. it can.

Next, the pointer is set at the node where the key to be deleted is set, and the last block (hereinafter, referred to as
This block is referred to as a replacement top block), and the deletion procedure is shown when only one of the left pointer and the right pointer is set. in this case,
All the contents of the node block and the pointer pointed by the left pointer or the right pointer of the replacement head block may be transferred to the blocks and pointers after the replacement head block of the node in which the key to be deleted is set. For example,
When the key A is deleted from the data structure of FIG. 1, it is found that the key is searched and the key A is set at the node 5. The blocks in which the pointer is set in the node 5 are A [1] and A [4], but since A [4] is a later block, A [4] becomes the replacement first block.
The block of A [4] has only the right pointer, and the node 8
The contents of the block and the pointer at the node 8 are copied to the block and the pointer after A [4] of the node 5. Then, the state shown in FIG. 3 is obtained. A [1], A
[2] and A [3] are D [1], D [2], and D
Since it is equal to [3], the key set at the node 5 is D instead of A, and it can be seen that the key A is deleted. The other registration statuses have not changed.

Next, the pointer is set at the node where the key to be deleted is set, and the leftmost pointer and the rightmost pointer of the last block (replacement head block) of the blocks where the pointer is set. The deletion procedure when both pointers are set is shown. In this case, first, consider a subtree structure in which the node pointed by the right pointer (following the method of tracing the left pointer) of the replacement head block of the node in which the key to be deleted is set is the root. In this subtree structure, only the pointer on the left of the block at the beginning of each node is traced to find a node for which the pointer on the left of the block at the beginning of the node is not set (hereinafter referred to as replacement source node). When the replacement source node is found, set the pointer pointing to the replacement source node to
Replace with the contents of the pointer on the right of the block at the beginning of the replacement source node. Next, the contents of the blocks after the replacement first block of the node in which the key to be deleted is set are replaced with the contents of the block set in the replacement source node. Further, it is sufficient to replace the pointers of the blocks after the first block after the replacement of the node in which the key to be deleted is set with the pointers of the second and subsequent blocks of the replacement original node. For example, when the key H is deleted from the data structure of FIG. 4, it is found that the key H is searched and the key H is set at the node 12. Since the block in which the pointer is set in the node 12 is only H [4], H [4] becomes the replacement top block. H
Both the right pointer and the left pointer are set in the block [4]. Therefore, in the subtree structure in which the node 14 pointed by the right pointer of H [4] is a root, only the left pointer of the head block of each node is traced, and the left pointer of the head block of the node is Search for unset nodes (replacement original nodes). First, node 14
Since the address has been set in the pointer on the left of the first block of, the pointer is traced, and then the node 15 is checked. Since the pointer to the left of the head block of the node 15 is not set, the node 15 becomes the replacement source node. Since the replacement source node is found, the left pointer of J [4] of the node 14 pointing to the replacement source node is replaced with the content of the right pointer of the leading block K [4] of the replacement source node 15. Next, the block after the replacement head block H [4] of the node 12 in which the key to be deleted is set is replaced with the contents of the block set in the replacement source node 15, and the key to be deleted is set. Replacement of the node 12 The pointer after the block one block after the leading block H [4] is replaced with the node 1
Replace with the pointers of the second and subsequent blocks of block 5. Then, the state shown in FIG. 5 is obtained. H [1], H [2], and H
[3] should be equal to K [1], K [2], and K [3], so the key set at node 12 is H
Instead of the key K, it can be seen that the key H has been deleted. Also, the registration status of other keys has not changed.

As described above, the procedure for deleting a key from this data structure is similar to the procedure for deleting a key from the binary tree data structure. However, since the procedure shown above can be used when searching for the node in which the key to be deleted is set, in this case as well, there is no wasteful comparison of overlapping parts and the time can be shortened by this amount.

Since this data structure uses the idea of a binary tree and each node is connected by a pointer to a larger one or a pointer to a smaller one, it is registered in this data structure. Clearly the keys are naturally sorted.

As described above, in the data structure shown in this embodiment, it is possible to register, search, delete, and sort a variable-length key. In the present embodiment, a normal binary tree is formed by keys having the same n-th block and different n + 1-th and subsequent blocks, but in addition to this, the n-th block is equal and the n + 1-th and subsequent blocks are the same. Since various methods such as a method of forming an AVL tree with different keys, a method of forming an optimal tree, and a method of forming a 2-3 tree can be considered, it is necessary to shorten the time in the worst case of key search. If desired, these methods can also be used.

[0031]

As described above, according to the present invention,
Data structures can be created that allow for variable length key registration, search, deletion, and sorting. At this time,
In this data structure, key comparison is performed for each block from the first block, and when the first block is the same and the second block is different, only one block of the same part is retained and after the different part The blocks are stored by connecting them with pointers so that they become a tree-structured data structure. Therefore, when searching for a node in which the target key is registered or a place where the target key is added, there is no wasteful comparison of the portions where the key contents overlap. In addition, in the case of adding a key, the data set in the overlapping portion of the key needs to be set only once. Furthermore, in the case of a normal binary tree, the comparison at one node yields only three pieces of information: equal, large, and small. Therefore, only one pointer can be selected from the two pointers and traced according to the comparison result at one node. However, in the method of the present invention, by comparison at one node, it is more detailed such as: equal, to which block is equal, where to be large block, to which block is equal, and after which block is small. You can get information. Therefore, one pointer can be selected and traced from two or more pointers according to the comparison result at one node. Therefore, the number of pointers required to search for the target key and reach the node where the target key is set is reduced. Therefore, these functions can be realized in a shorter time than when performing key registration, search, deletion, and sorting with a conventional tree-structured data structure.
In addition, when many keys are registered and there are many overlapping keys, the search can be executed in a shorter time than the binary search.

[Brief description of drawings]

FIG. 1 is a block diagram showing a data structure of A, B,
It is a figure which shows the data structure at the time of registering seven keys of C, D, E, F, and G.

FIG. 2 is a diagram showing a configuration of nodes.

FIG. 3 is a diagram showing a data structure after key A is deleted from the data structure shown in FIG.

FIG. 4 shows H, I, and
It is a figure which shows the data structure at the time of registering six keys of J, K, L, and M.

5 is a diagram showing a data structure after deleting a key H from the data structure shown in FIG. 4;

[Explanation of symbols]

 1 ... area for setting block, 2 ... left pointer area, 3 ... right pointer area, 4 ... root pointer, 5-17 ... node.

Claims (1)

What is claimed is: 1. When a plurality of identifiers (hereinafter referred to as keys) for identifying data are registered in a data structure for the purpose of searching, each key is divided into one or more. (Divided keys are referred to as blocks below), the keys are compared from the first block to the last block, and if the first block of the key is the same and the second block of the key is different, the same. A high-speed search method using a tree-structured data structure, in which only one block is retained, and blocks following different portions are connected by a pointer so that the block has a tree-structured data structure.