We often encounter such scenarios in project development: enterprise organizational structure, reply comment chain, product category and other tree structures. This article combines some information on the Internet, as well as my own practice in the project to say several ways to deal with tree structure.

My first thought is that I can save the parent_id of each data to meet the demand ah, so that I can find the layer by layer, write a recursive algorithm can get all its children or superiors. That’s one way to do it, and we’re not going to judge the merits of that.

Here are some common handling methods:

  • The Adjacency List
  • Closure Table Closure Table
  • Path Enumeration
  • Nested Sets

This article mainly discusses Path enumeration (Path enumeration). Other kinds of enumeration are only simple demonstration. If you need to know more, you can click on the link to check out

  • The Closure table explain in detail www.jianshu.com/p/951b742fd…

  • Four ways are on www.cnblogs.com/wjq310/p/88…

  • MySQL implementation model nested set yq.aliyun.com/articles/50…

The Adjacency List

The following diagram shows the organization of a simple adjacency list structure, as we said earlier

The way data is obtained

  • To obtain the department directly under an organization, we only need to query according to the ID of the organization
Select * from org where parent_id =1;Copy the code
  • Query all organizations under an organization, need recursive + loop get children, grandchildren… The child node of, is roughly written as follows:
public List<Org> getOrgTree(String parentId){
  List<Orgs> resultOrgs = new ArrayList<>();
  // Take it to the subordinate organization
  List<Org> children = getChildren(parentId);
  resultOrgs.addAll(children);
  for(Org org :children){
    resultOrgs.addAll(getOrgTree(org.parentID));
  }
  return resultOrgs;  
}
Copy the code

Closure Table Closure Table

This approach to introduce with post comments, data structure, borrowed from the www.jianshu.com/p/951b742fd… The database model is as follows:

! [] (xiao-files.oss-cn-beijing.aliyuncs.com/picgo/ closure table (2). The PNG)

Ancestor stores the recovered root Id, descendant stores the current Id, which takes up space. Theoretically, O(n²) space is needed to store the relationship.

Select C.* from comment c left join comment_path cp on (C.id = cp.descendant) select C.* from comment c left join comment_path cp on (C.ID = cp. where cp.ancestor = 4 and depth = 1; Select C.* from comment c join comment_path cp on (C.ID = cp.descendant) where cp.ancestor = 4;Copy the code

Nested Sets

The nested set solution stores information in each node, which corresponds to a collection of its descendants rather than the node’s immediate parent.

In nested set designs, tree manipulation, insertion, and movement of nodes are generally more complex than in other models.

When a new node is inserted, all left and right values greater than the new node’s lvalue need to be recalculated.

Nested sets are too complex for me to fully understand, so I won’t cover them in detail in this article. You can refer to MySQL to implement the nested collection model

Path Enumeration

This method takes the organization table in the project as an example. The difference with path enumeration is that org_num is used instead of path.

In the project, we agreed that the number length of each level is 2, the maximum level is 20, the number of child nodes of each level is 99, and the maximum number of storage nodes is 2 to the 19th power nodes

The hierarchy is as follows:

Several ways to manipulate data

OrgNum Specifies the number of a node. OrgLen Specifies the length of a node

  • Get the hierarchy of children of a node
OrgLen and maxLength select * from orgswhere org_num like '#{orgNum}%' and length(org_num) > #{orgLen} and length(org_num) <=#{maxLength}
Copy the code
  • Get all the children of a node
select * from orgs where org_num like '#{orgNum}%' and length(org_num) > #{orgLen}
Copy the code
  • Get the parent node or go up a few levels to the parent node
Select * from orgs where org_num = #{orgNum} select * from orgs where org_num = #{orgNum}Copy the code
  • Deleting the organizational structure
Delete from orgs where org_num like '#{orgNum}%' and length(org_num) > #{orgLen}Copy the code
  • Mobile node
// Update org_num of the current node and org_num of all its children
// If node ordering is involved, update orgNum of the current node and consider orders of the sibling node to which you are moving
Copy the code
  • Tissue tree structure
// Get the node's own rootOrg and all its subordinate orglists from the database
private OrgTreeDTO orgTreeGenerate(List<Org> OrgList, Org rootNode, Org parent) { List<Org> subNodes = OrgList.stream().filter(x -> x.getOrgNum().startsWith(rootNode.getOrgNum()) && x.getOrgNum().length() == rootNode.getOrgNum().length() + OrgConst.ORG_NODE_LENGTH && ! x.getId().equals(rootNode.getId()) ).collect(Collectors.toList()); OrgTreeDTO orgTreeDTO =new OrgTreeDTO().setId(rootNode.getId())
      .setName(rootNode.getName())
      .setOrders(rootNode.getOrders())
      .setType(rootNode.getType())
      .setChildren(subNodes.stream().map(x ->
        orgTreeGenerate(OrgList, x,rootNode)
      ).collect(Collectors.toList()));
   
    if(! ObjectUtils.isEmpty(parent)){ orgTreeDTO.setParentId(parent.getId()) .setParentName(parent.getName()); }return orgTreeDTO;
  }

Copy the code

The above methods can almost meet most organizational restructuring needs.

The advantage of this approach is that the desired data can be obtained from the database through simple queries, and the specific assembly is handled in Java code.

Disadvantages If the level is too deep, org_num will become longer and longer, affecting the query efficiency. Therefore, the limit of node depth in the project is 20, which can meet almost all organizational structure data.

conclusion

This is the end of this article, if similar design ideas or questions, welcome to discuss.

Team blog link, welcome to click

Theory clarifies the direction of practice, and practice authenticates the truth of theory.