Traditional Culture Encyclopedia - Traditional stories - Great, a tree data table is designed and implemented to prevent foreigners from recursively querying all sub-departments!

Great, a tree data table is designed and implemented to prevent foreigners from recursively querying all sub-departments!

catalogue

Usually, the storage of tree structure is to store the number of the parent node on the child nodes to determine the parent-child relationship of each node. For example, the organizational structure is as follows: [image-a14d87-1651886833418]

Corresponding Table Data (Department):

[Image upload failed ... (Picture-A73B71-1651886833418)]

Department Table Structure (Department)

This method is very good, it can intuitively reflect the relationship between nodes, and usually can meet most of the needs. However, this method is no longer suitable for production when the business requirements become a lot and the amount of data is huge.

For example, PM adds the following requirements:

Using the specified department number and recursively looking down layer by layer may be the method that most people will think of. Although mysql8.0 supports cte (common table expression), the recursive efficiency is obviously improved compared with the traditional recursive method, but with the increase of department tree level depth, the query efficiency will still become worse. Another method is to find out all the data at once and put it into memory for processing (you can choose when the amount of data is small. With a large amount of data, people who are not afraid of being beaten can also choose this) ~

Recursively query the number of each layer and finally add it up.

Method 1: You can add the field isLeaf to indicate whether the node is a leaf node. Method 2: directly query whether the count of parent_id= current id is greater than 0. If it is greater than 0, it means it is not a leaf node; if it is equal to 0, it means it is a leaf node. In daily life, similar methods mentioned above may often be used to solve similar problems, but I think this method is not the optimal solution in efficiency. So I began to look for better solutions to solve these problems.

It was not until later that I checked a foreign blog and saw the so-called "improved priority tree traversal" article (Oh, my God, it was published in 2003) ~ How did he do it specifically? Or go back to the previous organizational structure [image-8b11AC-165188683417].

Let's start with the root node, set the left value of the chairman to 1, and the left value of the general manager of the subordinate department to 2, and so on, start to traverse along the border, add the left value to each node, add the right value to the node when encountering the leaf node, continue to traverse along the border, and return to the right side of the root node after the traversal, and you will get a structure similar to this. [image upload failed ... (image-f5f389-165188683417)]

After traversal, each node has its corresponding left and right values. At this point, you can delete the parent_id field and add LFT and RGT to store the left and right values.

[image upload failed ... (image-278dca-165188683417)]

The data and structure are ready, let's try to solve the above requirements ~

According to the rules of the current table structure, if you want to find out all the descendant departments, you only need to check the nodes whose left value is between the left and right numbers of the searched department, and they are all his children. For example, when querying all the sub-departments of the CEO, the left and right numbers of the CEO are 9 and 18 respectively, so the between query of lft field only needs 9 and 18, and the query result is the data of the inspected department and all subordinate departments;

& ltpre MP-original-font-size = " 17 " MP-original-line-height = " 27.200000762939453 " style = " margin:0px； Filling: 0px Outline: 0px Maximum width:100%; Box size: border-box! Important; Word wrap: hyphenation! Important; Caret color: rgb(34, 34, 34); Color: rgb(34, 34, 34); font-size: 17px； Font style: normal; Font-Variant-Capitalization: Normal; Font thickness: 400; Letter spacing: 0.5440000295639038px Orphan: car; Text alignment: alignment; Text Indentation: 0px Text Conversion: None; Widow: car; Word spacing: 0px-WebKit-text-size-adjust: auto; -WebKit-text-stroke-width:0px； Text-Decoration: None; Line height: 27.20453 pixels & gt

Perfect ~

& lt/pre & gt；

At this point, it may be said that the demand for 1 has been solved, and the total number will naturally be solved. Just choose count directly, there is nothing wrong with it, but it is not necessary, because there is a simple formula that can be directly calculated. Formula: Total = (right value-left value-1)/2 For example:

With the experience of calculating the total with the above formula, it is now judged whether it is a leaf node. Some friends already know how to do it, that is, if the right value is-1 == the left value, it is a leaf node, or if the left value is+1 == the right value, it is a leaf node, otherwise it is not. For example: design department, 5- 1 == 4, so it is a leaf node. Chairman, 20- 1! = 1, so it is not a leaf node. At this point, the above requirements have been perfectly solved, and then try the basic operation of the business.

When adding a department, you need to add 2 to the subsequent side of the new node position, because each node has two values. This operation usually needs to be handled in a transaction. For example, add a new department under the R&D department: [Image upload failed ... (image-36a719-1651886833417)]

Corresponding sql:

& lt/pre & gt；

Deleting a department is similar to adding a department, except that you need to subtract 2 from the subsequent edge nodes of the deleted node. For example, delete the newly added department: [image upload failed ... (image-504fd7-165188683417)]

Corresponding sql

& lt/pre & gt；

Query the subordinate departments of a department (that is, excluding grandson departments), for example, query the subordinate departments under the general manager. Back to the product department and the administrative director [it's normal for the picture to fail to upload ... (picture-E2C88e-1651886833417)].

Corresponding sql

& lt/pre & gt；

Query the ancestor chain path of a department. For example, if you query the ancestral chain path of the product department, you need to return to the chairman and general manager under normal circumstances.

& lt/pre & gt；

Personally, the only disadvantage of this method is that every time it is added or deleted, the nodes next to the operation node must be added/subtracted by 2.

Welcome to correct, exchange and comment, and discuss more solutions together. ...

-Link guide:

/s/GDmrIwo89WVfDyAWYSBWQA

Previous article:The Development Model of Yachang Enterprise (Group) Co., Ltd.
Next article:Livestock research report