CN111881140A - Data structure tree checking method, device, equipment and storage medium - Google Patents

Abstract

The present application discloses a data structure tree verification method, device, device and storage medium. The steps of the method include: counting the data structure tree in the data volume; judging whether there is an unverified target data structure tree in the data structure tree; if there is an unverified target data structure tree, calling the thread A verification operation is performed; wherein, the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the thread; the step of judging whether there is an unverified target data structure tree in the data structure tree is performed. The method relatively ensures the overall efficiency of the verification process for the data structure tree in the data volume. In addition, the present application also provides a data structure tree verification device, equipment and storage medium, the beneficial effects are the same as described above.

Description

A data structure tree verification method, device, device and storage medium

technical field

The present application relates to the field of data storage, and in particular, to a data structure tree verification method, apparatus, device and storage medium.

Background technique

A data structure tree is a data structure that consists of n (n greater than or equal to 0) finite nodes to form a hierarchical data set, including root nodes, internal nodes and leaf nodes. The data structure tree is usually used in the file system of the database system and the operating system for data indexing, which can keep the data storage stable and orderly, and its insertion and modification have a relatively stable logarithmic time complexity.

In a database system or file system, the data structure tree is often stored in pre-divided data volumes. When verifying the data structure tree, a separate thread is often allocated to each data volume, and then the corresponding data volume is processed by using threads. However, in the current data structure tree verification method, when the number of available threads is greater than the number of data volumes, there are often idle threads, which makes it difficult to ensure that the data structure tree in the data volume is verified. The overall efficiency of the verification process.

It can be seen that it is a problem to be solved by those skilled in the art to provide a data structure tree verification method to relatively ensure the overall efficiency of the verification process of the data structure tree in the data volume.

SUMMARY OF THE INVENTION

The purpose of the present application is to provide a data structure tree verification method, apparatus, device and storage medium, so as to relatively ensure the overall efficiency of the verification process of the data structure tree in the data volume.

In order to solve the above-mentioned technical problems, the application provides a data structure tree verification method, including:

Data structure tree in the statistics volume;

Determine whether there is an unverified target data structure tree in the data structure tree;

If there is an unverified target data structure tree, the calling thread performs a verification operation on the target data structure tree; wherein, the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the thread;

The step of judging whether there is an unchecked target data structure tree in the data structure tree is performed.

Preferably, when the number of data volumes is greater than 1, after judging whether there is an unverified target data structure tree in the data structure tree, the method further includes:

If there is no unverified target data structure tree, determine whether there is a data volume that has not been verified;

If there is a data volume for which the verification operation is not performed, then based on the data volume for which the verification operation is not performed, the step of counting the data structure tree in the data volume is performed;

Otherwise, stop the verification operation.

Preferably, before performing the step of counting the data structure tree in the data volume based on the data volume for which the verification operation has not been performed, the method further includes:

Determine whether the data volume that has not performed the verification operation meets the preset verification standard;

If the preset verification standard is met, based on the data volume for which the verification operation has not been performed, the step of counting the data structure tree in the data volume is performed;

Otherwise, filter the data volumes that have not performed the verification operation.

Preferably, before the calling thread performs the verification operation on the target data structure tree, the method further includes:

Determine whether the root node data can be accessed through the root address of the target data structure tree;

If the root node data can be accessed, the calling thread performs the verification operation on the target data structure tree;

Otherwise, filter the target data structure tree.

Preferably, the data structure tree includes one or more of a B-tree, a B+ tree and a balanced binary tree.

In addition, the present application also provides a data structure tree verification device, comprising:

Statistics module, used to count the data structure tree in the data volume;

The structure tree judgment module is used to judge whether there is an unverified target data structure tree in the data structure tree, and if so, then call the thread verification module and the structure tree judgment module in turn;

The thread verification module is used to call the thread to perform verification operation on the target data structure tree; wherein, the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the thread.

Preferably, when the number of data volumes is greater than 1, the structure tree judgment module calls the data volume judgment module when there is no unverified target data structure tree;

The data volume judgment module is used to judge whether there is a data volume that has not performed the verification operation, if so, call the statistics module based on the data volume that has not performed the verification operation, otherwise, call the verification stop module;

The verification stop module is used to stop the verification operation.

Preferably, the device further includes:

The verification standard judgment module is used to judge whether the data volume that has not performed the verification operation meets the preset verification standard, and if so, calls the statistics module based on the data volume that has not performed the verification operation;

The data volume filtering module is used to filter the data volumes that have not been verified.

In addition, the application also provides a data structure tree verification device, including:

memory for storing computer programs;

The processor is configured to implement the steps of the above-mentioned data structure tree verification method when executing the computer program.

In addition, the present application also provides a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and when the computer program is executed by a processor, the steps of the above-mentioned data structure tree verification method are implemented.

The data structure tree verification method provided by this application firstly counts the data structure tree in the data volume, and then judges whether there is an unverified target data structure tree in the data structure tree, if there is an unverified target data structure tree, Then call the thread uniquely corresponding to the target data structure tree to perform the verification operation on the target data structure tree, and the total number of threads is greater than 1, and further perform the step of judging whether there is an unverified target data structure tree in the data structure tree , so as to complete the verification of all data structure trees in the data volume. This method allocates a separate thread to the unverified target data structure tree in the data volume. Since the overall number of data structure trees in the data volume is relatively large, the overall utilization rate of the thread can be relatively ensured, thereby relatively avoiding the occurrence of causes The number of available threads is greater than the number of data volumes, resulting in the existence of idle threads in the threads, which relatively ensures the overall efficiency of the process of verifying the data structure tree in the data volume. In addition, the present application also provides a data structure tree verification device, equipment and storage medium, the beneficial effects are the same as above.

Description of drawings

In order to describe the embodiments of the present application more clearly, the following will briefly introduce the drawings that are used in the embodiments. Obviously, the drawings in the following description are only some embodiments of the present application, which are not relevant to ordinary skills in the art. As far as personnel are concerned, other drawings can also be obtained from these drawings on the premise of no creative work.

1 is a flowchart of a method for verifying a data structure tree disclosed in an embodiment of the present application;

2 is a flowchart of a method for verifying a data structure tree disclosed in an embodiment of the present application;

FIG. 3 is a schematic structural diagram of a data synchronization apparatus disclosed in an embodiment of the present application.

Detailed ways

The technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application. Obviously, the described embodiments are only a part of the embodiments of the present application, but not all of the embodiments. All other embodiments obtained by those of ordinary skill in the art based on the embodiments in the present application without creative work fall within the protection scope of the present application.

In a database system or file system, the data structure tree is often stored in pre-divided data volumes. When verifying the data structure tree, a separate thread is often allocated to each data volume, and then the corresponding data volume is processed by using threads. However, in the current data structure tree verification method, when the number of available threads is greater than the number of data volumes, there are often idle threads, which makes it difficult to ensure that the data structure tree in the data volume is verified. The overall efficiency of the verification process.

Therefore, the core of the present application is to provide a data structure tree verification method, so as to relatively ensure the overall efficiency of the verification process for the data structure tree in the data volume.

In order to make those skilled in the art better understand the solution of the present application, the present application will be further described in detail below with reference to the accompanying drawings and specific embodiments.

Referring to FIG. 1 , an embodiment of the present application discloses a method for verifying a data structure tree, including:

Step S10: Statistics of the data structure tree in the data volume.

It should be noted that the data volume in this embodiment refers to a file directory that can be used by one or more containers. In addition, the data structure is stored in a pre-divided data volume for recording data stored in the data volume The storage address of the data volume is used to provide access and retrieval of the data stored in the data volume.

The purpose of counting the data structure tree in the data volume in this step is to verify the data structure tree in the subsequent steps. The purpose of the verification includes but is not limited to repairing the index content in the data structure tree, or using the data structure The tree accesses the stored data in the data volume, etc.

In addition, the number of data structure trees stored in the data volume should be determined according to the actual situation, and may be one or more.

Step S11: Determine whether there is an unverified target data structure tree in the data structure tree, and if so, perform step S12 and step S11 in sequence.

Step S12: The calling thread performs a check operation on the target data structure tree.

Among them, the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the threads.

After the data structure tree in the data volume is counted, the present embodiment further judges whether there is an unverified target data structure tree in the data structure tree, and further when the unverified target data structure tree is stored, the calling thread The structure tree performs verification operations. In addition, it should be emphasized that the key point of this embodiment is that the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the thread, that is, when the number of data structure trees is greater than 1, at least there is Two or more threads simultaneously perform checksum operations on different data structure trees in the same data volume.

The data structure tree verification method provided by this application firstly counts the data structure tree in the data volume, and then judges whether there is an unverified target data structure tree in the data structure tree, if there is an unverified target data structure tree, Then call the thread uniquely corresponding to the target data structure tree to perform the verification operation on the target data structure tree, and the total number of threads is greater than 1, and further perform the step of judging whether there is an unverified target data structure tree in the data structure tree , so as to complete the verification of all data structure trees in the data volume. This method allocates a separate thread to the unverified target data structure tree in the data volume. Since the overall number of data structure trees in the data volume is relatively large, the overall utilization rate of the thread can be relatively ensured, thereby relatively avoiding the occurrence of causes The number of available threads is greater than the number of data volumes, resulting in the existence of idle threads in the threads, which relatively ensures the overall efficiency of the process of verifying the data structure tree in the data volume.

On the basis of the above embodiment, as a preferred implementation, before the calling thread performs the verification operation on the target data structure tree, the method further includes:

Determine whether the root node data can be accessed through the root address of the target data structure tree;

If the root node data can be accessed, the calling thread performs the verification operation on the target data structure tree;

Otherwise, filter the target data structure tree.

It should be noted that the key point of this embodiment is that, before the calling thread performs the verification operation on the target data structure tree, it is first judged whether the root node data can be accessed through the root address of the target data structure tree, that is, to judge the target data structure. The tree can be accessed by normal traversal. If the root node data can be accessed, it means that the target data result tree can be accessed by normal traversal, and then the calling thread performs the verification operation on the target data structure tree. If the root address of the data structure tree cannot be accessed to obtain the root node data, the target data structure tree is further filtered. This embodiment further ensures the reliability of checking the data structure tree.

Referring to FIG. 2 , when the number of data volumes is greater than 1, an embodiment of the present application discloses a method for verifying a data structure tree, including:

Step S20: Statistical data structure tree in the data volume.

Step S21: Determine whether there is an unverified target data structure tree in the data structure tree, if so, execute step S22 and step S21 in sequence, otherwise, execute step S23.

Step S22: If there is an unverified target data structure tree, the calling thread performs a verification operation on the target data structure tree.

Among them, the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the threads.

Step S23: Determine whether there is a data volume for which the verification operation has not been performed, and if so, perform Step S20 based on the data volume for which the verification operation has not been performed; otherwise, perform Step S24.

Step S24: Stop the verification operation.

It should be noted that this embodiment is applicable to a scenario where the number of data volumes is greater than 1. When the number of data volumes is greater than 1, if it is determined whether there is an unverified target data structure tree in the data structure tree, the result is that there is no unverified target data structure tree. When verifying the target data structure tree, it means that all the data structure trees in the current data volume have been verified. Therefore, in this case, it is further judged whether there is a data volume for which the verification operation has not been performed. If the data volume for which the verification operation has not been performed, the data structure tree in the data volume without the verification operation will be further counted, and the data structure tree in the data volume without the verification operation will be further verified. If the data volume is displayed, it means that the verification of the data structure tree in all data volumes has been completed, so the verification operation is stopped. This embodiment further ensures the reliability and comprehensiveness of the data structure tree check when the number of data volumes is greater than 1.

On the basis of the foregoing embodiment, as a preferred implementation manner, before performing the step of counting the data structure tree in the data volume based on the data volume for which the verification operation has not been performed, the method further includes:

Determine whether the data volume that has not performed the verification operation meets the preset verification standard;

If the preset verification standard is met, based on the data volume for which the verification operation has not been performed, the step of counting the data structure tree in the data volume is performed;

Otherwise, filter the data volumes that have not performed the verification operation.

It should be noted that the key point of this embodiment is to further determine whether the data volume for which the verification operation is not performed satisfies the preset value before performing the step of counting the data structure tree in the data volume based on the data volume for which the verification operation has not been performed. The verification standard, and then when the data volume for which the verification operation is not performed meets the preset verification standard, the step of counting the data structure tree in the data volume is further performed based on the data volume for which the verification operation is not performed; on the contrary, when the data volume is not performed When the data volume of the verification operation does not meet the preset verification standard, the data volume for which the verification operation has not been performed is further filtered. In addition, the preset verification standard in this embodiment includes, but is not limited to, the data volume belongs to a specific type, the data volume can be accessed, or the read-write control authority of the data volume belongs to the local controller, and the like.

This embodiment further ensures the overall reliability of the data structure tree verification by performing the verification of the data structure tree only on the data volumes that meet the preset verification standard.

On the basis of the foregoing series of implementations, as a preferred implementation, the data structure tree includes one or more of a B-tree, a B+ tree and a balanced binary tree.

It should be noted that the balanced binary tree adopts the idea of dichotomy to assemble data into a tree-structured data according to the rules. Using this tree-structured data reduces the retrieval of irrelevant data and greatly improves the speed of data retrieval; B-tree also Compared with the balanced binary tree, there are more than two search paths; compared with the B tree, the B+ tree makes more full use of the node space, making the query speed more stable, and its speed is completely close to the dichotomy method Find.

This embodiment further ensures the diversity of the data structure tree, and further improves the overall flexibility of verifying the data structure tree.

Referring to FIG. 3, an embodiment of the present application provides a data structure tree verification device, including:

The statistics module 10 is used for statistics of the data structure tree in the data volume;

The structure tree judgment module 11 is used to judge whether there is an unverified target data structure tree in the data structure tree, and if so, then call the thread check module 12 and the structure tree judgment module 11 in turn;

The thread verification module 12 is used for calling a thread to perform a verification operation on the target data structure tree; wherein, the total number of threads is greater than 1, and there is a unique correspondence between the target data structure tree and the thread.

Preferably, when the number of data volumes is greater than 1, the structure tree judgment module calls the data volume judgment module when there is no unverified target data structure tree;

The data volume judgment module is used to judge whether there is a data volume that has not performed the verification operation, if so, call the statistics module based on the data volume that has not performed the verification operation, otherwise, call the verification stop module;

The verification stop module is used to stop the verification operation.

Preferably, the device further includes:

The verification standard judgment module is used to judge whether the data volume that has not performed the verification operation meets the preset verification standard, and if so, calls the statistics module based on the data volume that has not performed the verification operation;

The data volume filtering module is used to filter the data volumes that have not been verified.

The data structure tree verification device provided by the present application firstly counts the data structure tree in the data volume, and then judges whether there is an unverified target data structure tree in the data structure tree, if there is an unverified target data structure tree, Then call the thread uniquely corresponding to the target data structure tree to perform the verification operation on the target data structure tree, and the total number of threads is greater than 1, and further perform the step of judging whether there is an unverified target data structure tree in the data structure tree , so as to complete the verification of all data structure trees in the data volume. By assigning a separate thread to the unverified target data structure tree in the data volume, the device can relatively ensure the overall utilization rate of the thread because the overall number of the data structure tree in the data volume is relatively large, thereby relatively avoiding the occurrence of The number of available threads is greater than the number of data volumes, resulting in the existence of idle threads in the threads, which relatively ensures the overall efficiency of the process of verifying the data structure tree in the data volume.

In addition, the embodiment of the present application also provides a data structure tree verification device, including:

memory for storing computer programs;

The processor is configured to implement the steps of the above-mentioned data structure tree verification method when executing the computer program.

The data structure tree verification device provided by the present application firstly counts the data structure tree in the data volume, and then judges whether there is an unverified target data structure tree in the data structure tree, if there is an unverified target data structure tree, Then call the thread uniquely corresponding to the target data structure tree to perform the verification operation on the target data structure tree, and the total number of threads is greater than 1, and further perform the step of judging whether there is an unverified target data structure tree in the data structure tree , so as to complete the verification of all data structure trees in the data volume. The device allocates a separate thread to the unverified target data structure tree in the data volume. Since the overall number of data structure trees in the data volume is relatively large, it can relatively ensure the overall utilization rate of the thread, and thus relatively avoid the occurrence of The number of available threads is greater than the number of data volumes, resulting in the existence of idle threads in the threads, which relatively ensures the overall efficiency of the process of verifying the data structure tree in the data volume.

In addition, an embodiment of the present application further provides a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and when the computer program is executed by a processor, the steps of the above-mentioned data structure tree verification method are implemented.

The computer-readable storage medium provided by the present application firstly counts the data structure tree in the data volume, and then judges whether there is an unverified target data structure tree in the data structure tree, if there is an unverified target data structure tree, then Call the thread uniquely corresponding to the target data structure tree to perform a verification operation on the target data structure tree, and the total number of threads is greater than 1, and further perform the step of judging whether there is an unverified target data structure tree in the data structure tree, In this way, the verification of all data structure trees in the data volume is completed. The computer-readable storage medium allocates a separate thread to the unverified target data structure tree in the data volume. Since the overall number of data structure trees in the data volume is relatively large, the overall utilization rate of the thread can be relatively ensured, and further Relatively avoids the situation that the number of available threads is greater than the number of data volumes, which leads to the existence of idle threads in the threads, and relatively ensures the overall efficiency of the verification process of the data structure tree in the data volume.

A method, apparatus, device and storage medium for verifying a data structure tree provided by the present application have been described above in detail. The various embodiments in the specification are described in a progressive manner, and each embodiment focuses on the differences from other embodiments, and the same and similar parts between the various embodiments can be referred to each other. As for the device disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and the relevant part can be referred to the description of the method. It should be pointed out that for those of ordinary skill in the art, without departing from the principles of the present application, several improvements and modifications can also be made to the present application, and these improvements and modifications also fall within the protection scope of the claims of the present application.

It should also be noted that, in this specification, relational terms such as first and second, etc. are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply these entities or operations. There is no such actual relationship or sequence between operations. Moreover, the terms "comprising", "comprising" or any other variation thereof are intended to encompass a non-exclusive inclusion such that a process, method, article or device that includes a list of elements includes not only those elements, but also includes not explicitly listed or other elements inherent to such a process, method, article or apparatus. Without further limitation, an element qualified by the phrase "comprising a..." does not preclude the presence of additional identical elements in a process, method, article or apparatus that includes the element.

Claims (10)

1. a data structure tree verification method, is characterized in that, comprises: Data structure tree in the statistics volume; Judging whether there is an unverified target data structure tree in the data structure tree; If there is an unverified target data structure tree, the calling thread performs a verification operation on the target data structure tree; wherein, the total number of the threads is greater than 1, and the distance between the target data structure tree and the thread There is a unique correspondence; The step of judging whether there is an unverified target data structure tree in the data structure tree is performed. 2. The method for verifying a data structure tree according to claim 1, wherein when the number of the data volumes is greater than 1, it is determined whether there is an unverified target data structure in the data structure tree. After the tree, the method further includes: If there is no unverified target data structure tree, determine whether there is a data volume for which the verification operation has not been performed; If there is a data volume for which the verification operation is not performed, then based on the data volume for which the verification operation is not performed, the step of counting the data structure tree in the data volume is performed; Otherwise, the verification operation is stopped. 3. The method for verifying a data structure tree according to claim 2, wherein, before the step of performing the data structure tree in the statistical data volume based on the data volume that does not perform the verification operation, The method also includes: judging whether the data volume for which the verification operation has not been performed meets a preset verification standard; If the preset verification standard is met, based on the data volume for which the verification operation is not performed, the step of counting the data structure tree in the data volume is performed; Otherwise, filter the data volumes for which the verification operation is not performed. 4. The data structure tree verification method according to claim 1, wherein before the calling thread performs a verification operation on the target data structure tree, the method further comprises: Judging whether the root node data can be accessed through the root address of the target data structure tree; If the root node data can be accessed and obtained, the step of performing the verification operation on the target data structure tree by the calling thread is performed; Otherwise, filter the target data structure tree. 5 . The data structure tree verification method according to claim 1 , wherein the data structure tree comprises one or more of a B tree, a B+ tree and a balanced binary tree. 6 . 6. a data structure tree verification device, is characterized in that, comprises: Statistics module, used to count the data structure tree in the data volume; A structure tree judgment module, used for judging whether there is an unverified target data structure tree in the data structure tree, and if so, calling the thread verification module and the structure tree judgment module in turn; The thread verification module is used to call a thread to perform a verification operation on the target data structure tree; wherein, the total number of the threads is greater than 1, and there is a unique correspondence between the target data structure tree and the thread relation. 7. The data structure tree verification device according to claim 6, characterized in that, when the number of the data volumes is greater than 1, the structure tree judging module does not exist when the unverified target data structure does not exist When tree, call the data volume judgment module; The data volume judging module is used to judge whether there is a data volume that has not performed the verification operation, if so, call the statistics module based on the data volume that has not performed the verification operation, otherwise, call the verification operation stop module; The verification stop module is used to stop the verification operation. 8. The data structure tree verification device according to claim 7, wherein the device further comprises: A verification standard judging module, configured to determine whether the data volume for which the verification operation has not been performed meets a preset verification standard, and if so, call the statistics module based on the data volume for which the verification operation has not been performed , otherwise, call the data volume filtering module; The data volume filtering module is configured to filter the data volume for which the verification operation is not performed. 9. A data structure tree verification device, characterized in that, comprising: memory for storing computer programs; The processor is configured to implement the steps of the data structure tree verification method according to any one of claims 1 to 5 when executing the computer program. 10. A computer-readable storage medium, wherein a computer program is stored on the computer-readable storage medium, and when the computer program is executed by a processor, the data according to any one of claims 1 to 5 is realized The steps of the structure tree verification method.

Images