CN103281175B - A Dynamic Balancing Method of LKH Key Management Tree - Google Patents

Abstract

The invention discloses a dynamic balance method of an LKH key management tree. By judging the numbers N _J and _ND of users who join and leave the key management group, different methods are used to dynamically balance the original key management tree to obtain a new key management tree. The key management tree of LKH is the balanced key management tree, which ensures the efficiency of LKH in group key management.

Description

A Dynamic Balancing Method of LKH Key Management Tree

technical field

The invention belongs to the technical field of network information security, and more specifically relates to a method for dynamically balancing an LKH key management tree.

Background technique

The rapid development of multicast networks has brought about the wide application of multicast services, such as IPTV, vehicular communications, and video conferencing. How to ensure the security of communication within a multicast group is the basis for developing multicast services. The most common and effective method is to encrypt messages within a group and then share an encryption key among legal members of the group to ensure multicast The security of communication within the group can effectively prevent illegal users from stealing the content of communication within the group. Considering that users in the group may leave or join at any time, in order to ensure the forward and backward security of communication in the group, the group key management center needs to update the encryption key in time. How to efficiently manage and update encryption keys within a group is an extremely important issue. At present, a variety of group key management methods have been proposed, such as OFT, ELK, SDR, SHKD, and LKH. For large dynamic multicast networks, LKH (Logical Key Hierarchy) is one of the efficient key management methods.

LKH uses a key management tree as shown in Figure 1 to manage group keys. There are three types of keys in the key management tree, the encryption key K ₀ located at the root node of the tree, which is used to directly encrypt the communication content within the group; the user private keys PK ₁ ~ PK ₆ located at the leaf nodes, each When a user joins a group, the group key management center will assign him a user private key PK ₁ ~ PK ₆ ; other nodes in the tree are distribution keys K ₁ ~ K ₄ , which are mainly used to distribute encryption keys. Each member in the group saves all keys on the path from its corresponding leaf node to the root node of the tree, and the group key management center saves all keys in the key management tree. When the members in the group change, the key management center will update the corresponding key. As shown in Figure 1, if member M ₁ leaves the communication group, in order to ensure that member M ₁ can no longer decrypt the communication content in the group, the key management center needs to update the keys K ₀ , K ₁ and K ₃ , and generate the following key update message {K ₃ '}PK ₂ ,{K' ₁ }K' ₃ ,{K' ₁ }K ₄ ,{K' ₀ }K' ₁ and {K' ₀ }K ₂ , where K _i ' represents K _i The new key of {K _i '}K _j means to encrypt the key K _i ' with K _j . For member M ₂ , when it receives these key update messages, it first uses its private key PK ₂ to decrypt the message {K ₃ '}PK ₂ to get a new key K ₃ ', and then uses the key K ₃ ' Decrypt the message {K' ₁ }K' ₃ to get the new key K ₁ ', and finally use the riddle K ₁ 'to decrypt the message {K' ₀ }K' ₁ to get the new encryption key K' ₀ . In this way, the remaining members in the group can successfully obtain the new encryption key, but member M1 cannot obtain the new encryption key, which ensures the security _of communication. If member M ₁ is added to the group, also to ensure that member M ₁ cannot use the key to decrypt the previous communication content in the group, so when member M ₁ is added to the group, the group key management center needs to update the encryption key. As shown in Figure 1, keys K ₀ , K ₁ and K ₃ need to be updated, and the key update message is {K ₃ '}PK ₁ ,{K ₃ '}PK ₂ ,{K ₁ '}K ₃ ',{ K' ₁ }K ₄ , {K' ₀ }K' ₁ and {K' ₀ }K ₂ , so member M ₁ according to the message {K ₃ '}PK ₁ , {K ₁ '}K ₃ 'and {K' ₀ }K' ₁ can get a new encryption key, similarly, other members in the group can also get a new encryption key according to the key update message. The LKH key management overhead is related to the logarithm of the number of members in the group, so it is a low-overhead group key management scheme.

However, the premise of efficient LKH key management is a balanced key management tree. If the relationship between users in the group changes and the key management tree is unbalanced, it will be a serious challenge to the efficiency of LKH key management.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies in the prior art, provide a kind of LKH key management tree dynamic balance method, make LKH key management tree can keep balance under any circumstances, thereby guaranteed LKH on group key management Efficiency.

In order to realize the above-mentioned purpose of the invention, the LKH key management tree dynamic balance method of the present invention is characterized in that comprising the following steps:

(1) Define variables N _J and N _D to represent the number of users joining and leaving the key management group respectively;

(2) Judging the number N _J and N _D of users joining and leaving the key management group;

2.1), when the number of joining users N _J > the number of leaving users N _D , then execute:

a1. Select a number of N _D joining users to replace the leaving users in the original key management tree;

a2. Merge the remaining joining users and the original key management tree into a new key management tree: regard the joining user as a key management tree of a single node, and combine the single-node key management tree and the original key management tree Form a set of key management trees to be merged, select two key management trees with the smallest height from the set of key management trees to be merged, merge them into a key management tree and place them in the set of key management trees to be merged, At the same time, delete these two key management trees with the smallest height from the set of key management trees to be merged; select two key management trees with the smallest height in the set of key management trees to be merged to merge, and repeat this until only Until one key management tree is left, the key management tree is a new key management tree;

2.2) When the number of joining users N _J = the number of users leaving the user N _D , just replace the leaving users in the original key management tree with joining users to get a new key management tree;

2.3), when the number of joining users N _J < the number of leaving users N _D , execute:

b1, replace the number of N _J leaving users in the original key management tree with all joining users;

b2. Delete the left user who has not been replaced in the original key management tree, and delete the node:

If the node in the original key management tree lacks the right node subtree or the left node subtree, this node will be replaced by its remaining node subtree;

b3. From bottom to top and from right to left, check whether each node in the original key management tree is a balanced node. If the node is unbalanced, merge the left and right subtrees of the unbalanced node, and use the newly merged subtree Replace unbalanced nodes to get a new key management tree;

(3) The key management center generates a key update message and a location update message according to the change of nodes in the new key management tree, that is, the balanced key management tree, and manages the group key;

Among them, the merger described in step 2.1) and step 2.3) is:

The two key management trees to be merged are Tree1 and Tree2, and the maximum height of the key management trees Tree1 and Tree2 is H _{Max_Tree1 ≥} H _{Max_Tree2} ;

c1. When the maximum height H _{Max_Tree1} of the key management tree Tree1 - the minimum height H _{Min_Tree2} of the key management tree Tree2 ≤ 1, use the merge method 1 to merge: create a new node, and combine the key management tree Tree1 and Tree2 is used as the left and right subtrees of the newly created node, and the newly created node is the root node of the merged balanced key management tree;

c2. When the maximum height H _{Max_Tree1} of the key management tree Tree1 - the minimum height H _{Min_Tree2} of the key management tree Tree2 > 1, and the maximum height and minimum height of the key management tree Tree1 are equal, that is, H _{Max_Tree1} = H _{Min_Tree1} , the merge method is adopted Two to merge, namely:

The first step is to calculate the difference h between the maximum heights H _{Max_Tree1} and H _{Max_Tree2} of the key management tree Tree1 and Tree2, i.e. h=H _{Max_Tree1-} H _{Max_Tree2} ;

The second step is to search for a node to be updated from left to right on the h layer of the key management tree Tree1, if there is such a node, mark it; if there is no such node, mark the h layer of the key management tree Tree1 on the last node;

The third step is to create a new node to replace the node marked in the second step, and use the key management tree Tree2 and the subtree with the marked node as the root node as the left and right subtrees of the newly created node;

c3. When the maximum height H _{Max_Tree1} of the key management tree Tree1 - the minimum height H _{Min_Tree2} of the key management tree Tree2 > 1, and the maximum height and minimum height of the key management tree Tree1 are not equal, that is, H _{Max_Tree1} ≠ H _{Min_Tree1} , sampling is merged Method 3 for merging:

The first step, define parameters:

Set_M represents a container used to store the minimum height subtree of the key management tree Tree1;

Set_T represents a container for storing the key management tree to be merged. Initially, the container only contains the key management tree Tree2;

Num_M represents the number of minimum height subtrees in the container Set_M;

H _i represents the maximum height of the i-th minimum height subtree in the container Set_M;

MinTree_H _i represents the minimum height subtree whose height is H _i ;

H_MergeTree represents the tree with the largest height in the container Set_T;

Step 2: Find all the minimum height subtrees of the key management tree Tree1, and record these minimum height subtrees in the container Set_M according to the maximum height from large to small, that is, H ₁ ≥... _{≥H Num_M} ;

Step 3: Find the key management tree H_MergeTree with the largest height in the container Set_T;

Step 4: Comparing the maximum height of the minimum height subtree in the key management tree H_MergeTree and the container Set_M, there are the following three situations:

Situation 1: When the maximum height H _{Max_H_MergeTree} of the key management tree H_MergeTree is equal to the maximum height H _i (1≤i≤Num_M) of the minimum height subtree MinTree_H _i (1≤i≤Num_M), that is, H _{Max_H_MergeTree} =H _i , the method of merging the key is adopted The management tree H_MergeTree and the minimum height subtree MinTree_H _i are merged; secondly, the key management tree obtained by merging is used to replace the MinTree_H _i in the key management tree Tree1, and finally H_MergeTree is deleted from the container Set_T;

Situation 2: When the maximum height H _{Max_H_MergeTree} of the key management tree H_MergeTree is less than the maximum height H _{i of the minimum height subtree MinTree_H i and} greater than the maximum height H _{i+ 1 of the minimum height subtree MinTree_H i+1} , that is, H _{Max_H_MergeTree} <H _i and When H _{Max_H_MergeTree} >H _i+1 (i≠Num_M), if H _i -H _{Min_H_MergeTree} >1, merge the key management tree H_MergeTree and the minimum height subtree MinTree_H _i using the method of merging method 2; otherwise use the method of merging method 1 Merge H_MergeTree and MinTree_H _i , and replace MinTree_H _i in the key management tree Tree1 with the newly merged key management tree, and finally delete H_MergeTree from the container Set_T;

Case 3: When the maximum height H _{Max_H_MergeTree} of the key management tree H_MergeTree is less _than the maximum height H1 of the minimum height subtree _{MinTree_H1} , the key management tree H_MergeTree cannot be merged into the key management tree Tree1 at one time, and the key Measures for the decomposition of the management tree H_MergeTree, and merge it into the key management tree Tree1 step by step:

c31, search for _a subtree with a height of H1 in the key management tree H_MergeTree, denoted as subtree _{H_MergeTree_H1} ;

c32. Mark all nodes on the path from the parent node of the subtree _{H_MergeTree_H1} to the root node of the key management tree H_MergeTree. After removing the marked node, add records to the container Set_T for the remaining subtrees except the subtree _{H_MergeTree_H1} ;

c33. Merge the subtree _{H_MergeTree_H1} and the minimum height subtree MinTree_H1 using the method of merging method _one , and replace the minimum height subtree MinTree_H1 in the key management tree _Tree1 with the merged subtree;

c34. Delete the key management tree H_MergeTree from the container Set_T;

Step 5: Check whether the container Set_T is empty, if it is empty, the merge is completed, otherwise empty the container Set_M, and return to the first step;

Wherein, in the merging step, the maximum height of the key management tree is numerically equal to the maximum height of the root node of the key management tree, that is, the maximum length path from the root node to its child nodes, and the minimum length of the key management tree is Height is numerically equal to the minimum height of the root node of the key management tree, that is, the minimum path length from the root node to its child nodes;

The balance node is that if the difference between the maximum height and the minimum height of the node does not exceed 1, then this node is called a balance node;

The described balanced key management tree is if all nodes in the key management tree are balanced nodes, then this key management tree is called a balanced key management tree;

The layer of the tree is that the root node of the key management tree is set at the first layer, and the number of layers increases by 1 successively from the root node level;

The minimum height subtree is in an incomplete balanced key management tree, if the minimum height and maximum height of a node are equal but the minimum height and maximum height of its parent node are not equal, the definition of this node and all its The subtree composed of child nodes is the minimum height subtree.

The purpose of the invention of the present invention is achieved like this:

The LKH key management tree dynamic balance method of the present invention judges the number of users N _J and _ND who join and leave the key management group, samples different methods to dynamically balance the original key management tree, and obtains a new key management The tree is a balanced key management tree, which ensures the efficiency of LKH in group key management.

Description of drawings

Fig. 1 is a schematic diagram of LKH sampling key management tree managing group keys;

Fig. 2 is a schematic diagram of key management tree merging method-merging in the present invention;

Fig. 3 is the key management tree merging method two merging schematic diagrams in the present invention;

Fig. 4 is a schematic diagram of a concrete example of the key management tree Tree1 and the minimum height subtree in the merging method three;

Fig. 5 is a schematic diagram of situation 1 in the merger method three;

Fig. 6 is a schematic diagram of situation 2 in merging method three;

Fig. 7 is a schematic diagram of situation 3 in the merger method three;

Fig. 8 is a schematic diagram of the key management tree after the first merging is performed in the third merging method;

Fig. 9 is a schematic diagram of the key management tree after performing three merges in the merge method three;

Fig. 10 is a schematic diagram of the original key management tree in the present invention;

Fig. 11 is a schematic diagram of the balance in which the number of joining users is greater than the number of leaving users in the present invention;

Fig. 12 is a schematic diagram of the balance in which the number of joining users is equal to the number of leaving users in the present invention;

Fig. 13 is a schematic diagram of a key management tree in which the number of joining users is greater than the number of leaving users in the present invention;

FIG. 14 is a schematic diagram of the balanced key management tree shown in FIG. 13 .

Detailed ways

Specific embodiments of the present invention will be described below in conjunction with the accompanying drawings, so that those skilled in the art can better understand the present invention. It should be noted that in the following description, when detailed descriptions of known functions and designs may dilute the main content of the present invention, these descriptions will be omitted here.

Merge method one

In this embodiment, FIG. 2( a ) and ( b ) respectively represent the key management trees tree1 and tree2 to be merged that satisfy the first merge method. When using merge method 1 to merge two key management trees, you only need to create a new node new node and use the key management trees tree1 and tree2 to be merged as the left child subtree and right child subtree of the new node new node respectively. After merging The key management tree of is shown in Fig. 2(c).

Merge method two

In this embodiment, Fig. 3(a) shows the key management tree Tree1, and Fig. 3(b) shows the key management tree Tree1 after member M2 is deleted. Since member M2 leaves, the keys of node 0, node 1 and node 3 The key needs to be updated. It is now required to merge the key management tree Tree1 after deleting member M2 with the key management tree Tree2 shown in Figure 3(c). According to the merging method two, first find a node to be updated in the second layer of the key management tree Tree1 shown in Figure 3(b), and obviously node 1 meets the requirements, so mark node 1. Then create a new node new node to replace the marked node 1, and use the subtree with node 1 as the root node and Tree2 as the left and right subtrees of the new node new node. The merged key management tree is shown in Figure 3(d) .

Merge method three

Figure 4(a) shows the key management tree Tree1 to be merged that satisfies the three conditions of the merge method. The initial key management tree Tree1 has three minimum height subtrees, as shown in Figure 4(b), and their heights are respectively 3, 1, 1, the minimum height subtree of the key management tree Tree1 is recorded in the container Set_M and sorted in descending order of height, that is, H ₁ =3, H ₂ =1, H ₃ =1. At the same time, before performing the merging step, the key management tree Tree2 to be merged needs to be added to the container Set_T. According to the height of the key management tree Tree2 to be merged, the merge method 3 is discussed in detail in three situations. What needs to be explained here is that the tree H_MergeTree with the largest height to be merged is selected from the container Set_T for the first time, which is the merged key management tree Tree2.

Case 1: The maximum height of the key management tree Tree2 to be merged is equal to the height of a minimum height subtree of the key management tree Tree1.

The key management tree Tree2 shown in Figure 5(a) satisfies case 1, and H _{Max_Tree2} =H ₁ . Merge the key management tree Tree2 and the minimum height subtree MinTree_H ₁ using the method of merging method 1, and replace the minimum height subtree MinTree_H ₁ with the height H ₁ in the key management tree Tree1 with the merged tree. In this case, the final merged tree formed by merging the key management trees Tree1 and Tree2 is shown in Figure 5(b).

Case 2: The maximum height of the key management tree Tree2 to be merged is between the heights of the two minimum height subtrees of the key management tree Tree1.

The key management tree Tree2 shown in Fig. 6(a) satisfies case 2, H ₁ >H _{max_Tree2} >H ₂ . Merge the key management tree Tree2 and the minimum height subtree MinTree_H ₁ using the method of merging method 2, and replace the minimum height subtree MinTree_H ₁ with height H ₁ in the key management tree Tree1 with the merged tree. In this case, the final merged tree formed by merging the key management tree Tree1 and the key management tree Tree2 is shown in Figure 6(b).

Situation 3: The maximum height of the key management tree Tree2 to be merged is greater than the minimum height subtree with the largest height in the key management tree Tree1.

The key management tree Tree2 shown in Fig. 7(a) satisfies case 3, H _{max_Tree2} >H ₁ . At this time, the key management tree Tree2 needs to be split. First, find a subtree whose height is equal to H ₁ in the key management tree Tree2, and record it as H_MergeTree_H ₁ , as shown in Figure 7(b). The key management tree Tree2 The remaining subtree of is shown in Fig. 7(c), and the remaining subtree is added to the container Set_T. Merge the subtree H_MergeTree_H ₁ and the minimum height subtree MinTree_H ₁ using the method of merging method 1, and use the merged tree to replace the minimum height subtree MinTree_H ₁ in the key management tree tree1. After the first merge, Tree1 is as follows Figure 8 shows. Delete the key management tree Tree2 from the container Set_T, and the first merging is completed, but at this time, there are still remaining subtrees of the key management tree Tree2 in the container Set_T, and the merging operation needs to be continued, and the container Set_M is emptied and returned. After performing three merge operations, the final key management tree is shown in Figure 9.

Dynamic Balance Method of Key Management Tree

Suppose the key management center establishes a key management tree as shown in Figure 10 for the users in the group, that is, the original key management tree. Now implement the dynamic change process of the key management tree when the users in the group change dynamically.

Scenario 1: The number of joining users is greater than the number of leaving users

As shown in Figure 10, if members M ₄ and M ₇ leave, members M ₁₂ , M ₁₃ , M ₁₄ , M ₁₅ and M ₁₆ will join. Firstly select the joining members M ₁₂ and M ₁₃ to replace the leaving members M ₄ and M ₇ , and then consider merging the remaining joining members M ₁₄ , M ₁₅ and M ₁₆ and the original key management tree into a new balanced key management tree. Specific operation: regard M ₁₄ , M ₁₅ and M ₁₆ as a single-node key management tree, plus the original key management tree, there are four key management trees in total. Key management and use the merge method to merge them into a key management tree until finally only one key management tree remains. After the first two mergers, members M ₁₄ , M ₁₅ and M ₁₆ merge into a key management tree as shown in Figure 11(a). After the third merge, the final key management tree is shown in Figure 11(b).

Case 2: The number of joining users is equal to the number of leaving users

If members M ₄ and M ₇ leave, and members M ₁₂ and M ₁₃ join, directly replace the leaving users with joining users, and the obtained key management tree is shown in Figure 12.

Case 3: The number of joining users is less than the number of leaving users

If members M ₄ and M ₇ leave, no members join. Delete the outgoing users M4 and _M7 to get the key management tree shown in Figure ₁₃ . Since the deletion of a user may cause an imbalance in the key management tree, check whether all nodes in the key management tree are balanced from left to right and from bottom to top. When node 1 is checked, it is found that node 1 is unbalanced. Merge algorithm 3 is used here to merge the left and right subtrees of node 1 into a new balanced key management tree, and then replace node 1 with it. The balanced key management tree is shown in Figure 14.

Although the illustrative specific embodiments of the present invention have been described above, so that those skilled in the art can understand the present invention, it should be clear that the present invention is not limited to the scope of the specific embodiments. For those of ordinary skill in the art, As long as various changes are within the spirit and scope of the present invention defined and determined by the appended claims, these changes are obvious, and all inventions and creations using the concept of the present invention are included in the protection list.

Claims (2)

1. a logical key hierarchical LKH key management tree dynamic balance method, is characterized in that, comprises the following steps: (1), define variable N _J and N _D to represent the number of users who join and leave the key management group respectively; (2), judge the user number N _J and N _D of joining and leaving the key management group; 2.1), when the number of joining users N _J > the number of leaving users N _D , then execute: a1. Select a number of N _D joining users to replace the leaving users in the original key management tree; a2. Merge the remaining joining users and the original key management tree into a new key management tree: regard the joining user as a key management tree of a single node, and combine the single-node key management tree and the original key management tree Form a set of key management trees to be merged, select two key management trees with the smallest height from the set of key management trees to be merged, merge them into a key management tree and place them in the set of key management trees to be merged, At the same time, delete these two key management trees with the smallest height from the set of key management trees to be merged; select two key management trees with the smallest height in the set of key management trees to be merged to merge, and repeat this until only Until one key management tree is left, the key management tree is a new key management tree; 2.2), when the number of joining users N _J = the number of users leaving the user N _D , it is only necessary to replace the leaving users in the original key management tree with joining users to obtain a new key management tree; 2.3), when the number of joining users N _J < the number of leaving users N _D , execute: b1, replace the number of N _J leaving users in the original key management tree with all joining users; b2. Delete the left user who has not been replaced in the original key management tree, and delete the node: If the node in the original key management tree lacks the right node subtree or the left node subtree, this node will be replaced by its remaining node subtree; b3. From bottom to top and from right to left, check whether each node in the original key management tree is a balanced node. If the node is unbalanced, merge the left and right subtrees of the unbalanced node, and use the newly merged subtree Replace unbalanced nodes to get a new key management tree; (3) The key management center generates a key update message and a position update message according to the change of nodes in the new key management tree, ie, the balanced key management tree, to manage the group key. 2. logical key hierarchical LKH key management tree dynamic balance method according to claim 1, is characterized in that, step 2.1), step 2.3) described in merging as: The two key management trees to be merged are Tree1 and Tree2, and the maximum height of the key management trees Tree1 and Tree2 is H _{Max_Tree1 ≥} H _{Max_Tree2} ; c1. When the maximum height H _{Max_Tree1} of the key management tree Tree1 - the minimum height H _{Min_Tree2} of the key management tree Tree2 ≤ 1, use the merge method 1 to merge, that is: create a new node, and merge the key management tree Tree1 and Tree2 as the left and right subtrees of the newly created node, and the newly created node is the root node of the merged balanced key management tree; c2. When the maximum height H _{Max_Tree1} of the key management tree Tree1 - the minimum height H _{Min_Tree2} of the key management tree Tree2 > 1, and the maximum height and minimum height of the key management tree Tree1 are equal, that is, H _{Max_Tree1} = H _{Min_Tree1} , the merge method is adopted Two to merge, namely: The first step, calculate the difference h of key management tree Tree1 and Tree2 maximum height H _{Max_Tree1} , H _{Max_Tree2} namely h=H _{Max_Tree1-} H _{Max_Tree2} ; The second step is to search for a node to be updated from left to right on the h layer of the key management tree Tree1, if there is such a node, mark it; if there is no such node, mark the h layer of the key management tree Tree1 on the last node; The third step is to create a new node to replace the node marked in the second step, and use the key management tree Tree2 and the subtree with the marked node as the root node as the left and right subtrees of the newly created node; c3. When the maximum height H _{Max_Tree1} of the key management tree Tree1 - the minimum height H _{Min_Tree2} of the key management tree Tree2 > 1, and the maximum and minimum heights of the key management tree Tree1 are not equal, that is, H _{Max_Tree1} ≠ H _{Min_Tree1} , merge Method 3 for merging: The first step, define parameters: Set_M represents a container used to store the minimum height subtree of the key management tree Tree1; Set_T represents a container for storing the key management tree to be merged. Initially, the container only contains the key management tree Tree2; Num_M represents the number of minimum height subtrees in the container Set_M; H _i represents the maximum height of the i-th minimum height subtree in the container Set_M; MinTree_H _i represents the minimum height subtree whose height is H _i ; H_MergeTree represents the tree with the largest height in the container Set_T; Step 2: Find all the minimum height subtrees of the key management tree Tree1, and record these minimum height subtrees in the container Set_M according to the maximum height from large to small, that is, H ₁ ≥... _{≥H Num_M} ; Step 3: Find the key management tree H_MergeTree with the largest height in the container Set_T; Step 4: Compare the maximum height of the minimum height subtree in the key management tree H_MergeTree and the container Set_M, there are the following three situations: Situation 1: When the maximum height H _{Max_H_MergeTree} of the key management tree H_MergeTree is equal to the maximum height H _i (1≤i≤Num_M) of the minimum height subtree MinTree_H _i (1≤i≤Num_M), that is, H _{Max_H_MergeTree} =H _i , then the method of merging method 1 is used to pair the key The management tree H_MergeTree and the minimum height subtree MinTree_H _i are merged; secondly, the key management tree obtained by merging is used to replace the MinTree_H _i in the key management tree Tree1, and finally H_MergeTree is deleted from the container Set_T; Situation 2: When the maximum height H _{Max_H_MergeTree} of the key management tree H_MergeTree is smaller than the maximum height H _{i of the minimum height subtree MinTree_H i and} greater than the maximum height H _{i+ 1 of the minimum height subtree MinTree_H i+1} , that is, H _{Max_H_MergeTree} <H _i and When H _{Max_H_MergeTree} >H _i+1 (i≠Num_M), if H _i -H _{Min_H_MergeTree} >1, merge the key management tree H_MergeTree and the minimum height subtree MinTree_H _i using the method of merging method 2; otherwise use the method of merging method 1 Merge H_MergeTree and MinTree_H _i , and replace MinTree_H _i in the key management tree Tree1 with the newly merged key management tree, and finally delete H_MergeTree from the container Set_T; Case 3: When the maximum height H _{Max_H_MergeTree} of the key management tree H_MergeTree is less _than the maximum height H1 of the minimum height subtree _{MinTree_H1} , the key management tree H_MergeTree cannot be merged into the key management tree Tree1 at one time, and the key Measures for the decomposition of the management tree H_MergeTree, and merge it into the key management tree Tree1 step by step: c31, search for _a subtree with a height of H1 in the key management tree H_MergeTree, denoted as subtree _{H_MergeTree_H1} ; c32. Mark all nodes on the path from the parent node of the subtree _{H_MergeTree_H1} to the root node of the key management tree H_MergeTree. After removing the marked node, add records to the container Set_T for the remaining subtrees except the subtree _{H_MergeTree_H1} ; c33. Merge the subtree _{H_MergeTree_H1} and the minimum height subtree MinTree_H1 using the method of merging method _one , and replace the minimum height subtree MinTree_H1 in the key management tree _Tree1 with the merged subtree; c34. Delete the key management tree H_MergeTree from the container Set_T; Step 5: Check whether the container Set_T is empty, if it is empty, the merge is completed, otherwise empty the container Set_M, and return to the first step; Wherein, in the merging step, the maximum height of the key management tree is numerically equal to the maximum height of the root node of the key management tree, that is, the maximum length path from the root node to its child nodes, and the minimum length of the key management tree is Height is numerically equal to the minimum height of the root node of the key management tree, that is, the minimum path length from the root node to its child nodes; The balance node is that if the difference between the maximum height and the minimum height of the node does not exceed 1, then this node is called a balance node; The described balanced key management tree is if all nodes in the key management tree are balanced nodes, then this key management tree is called a balanced key management tree; The layer of the tree is that the root node of the key management tree is set at the first layer, and the number of layers increases by 1 successively from the root node level; The minimum height subtree is in an incomplete balanced key management tree, if the minimum height and maximum height of a node are equal but the minimum height and maximum height of its parent node are not equal, the definition of this node and all its The subtree composed of child nodes is the minimum height subtree.