Simple implementation of department tree management based on MPTT

preface

MPTT (Modified Preorder Tree Taversal) is a Modified Preorder Tree traversal. In fact, MPTT adds left and right attributes to each node on the basis of sequential traversal of the tree, making tree query operations (such as querying all children of a node, querying all leaf nodes) very efficient. Next, this article introduces some basic concepts of MPTT and the corresponding table structure in the database, and uses a simple example based on the SpringBoot + Vue framework to demonstrate the practice. The code used in this article has been uploaded to GitHub.

Sequential traversal and`MPTT`

Before introducing MPTT, let’s review the sequential tree traversal: After traversing a node, output the value of the node immediately, and then continue traversing the left and right nodes of the node respectively. The overall process is as follows:

The final traversal sequence is A -> B -> D -> E -> C, and the corresponding code operation is as follows:

public class Tree<T> {
    
	public T val;
    
	public Tree<T> left;
    
	public Tree<T> right;
    
	public Tree(T val) {
		this.val = val;
	}
    
	public static <T> void preOrder(Tree<T> tree, List<T> nodeList) {
		if (tree == null) {
			return;
		}
		nodeList.add(tree.val);
		preOrder(tree.left, nodeList);
		preOrder(tree.right, nodeList);
	}
    
	public static void main(String[] args) {
		Tree<String> tree = new Tree<>("A");
		tree.left = new Tree<>("B");
		tree.left.left = new Tree<>("D");
		tree.left.right = new Tree<>("E");
		tree.right = new Tree<>("C");
		List<String> nodeList = new ArrayList<>();
		preOrder(tree, nodeList);
		System.out.println(String.join("- >", nodeList)); }}Copy the code

In MPTT, LFT and RGT are added to the node in the process of sequential traversal. LFT is set before the left node of the node is accessed for the first time, and RGT is set after the right node is accessed, as shown in the following figure:

The order	val	lft	rgt
1	A	1	10
2	B	2	7
3	D	3	4
4	E	5	6
5	C	8	9

The corresponding code operation is as follows:

public class Tree<T> {
    
	public Node<T> node;
    
	public Tree<T> left;
    
	public Tree<T> right;
    
	public Tree(Node<T> node) {
		this.node = node;
	}
    
	public static class Node<T> {
		public T val;
		public long lft;
		public long rgt;
		public Node(T val) {
			this.val = val; }}public static <T> long preOrder(Tree<T> tree, long num, List<Node<T>> nodeList) {
		if (tree == null) {
			return num - 1;
		}
		tree.node.lft = num;
		nodeList.add(tree.node);
		long lft = preOrder(tree.left, num + 1, nodeList);
		long rgt = preOrder(tree.right, lft + 1, nodeList);
		tree.node.rgt = rgt + 1;
		return rgt + 1;
	}
    
	public static void main(String[] args) {
		Tree<String> tree = new Tree<>(new Node<>("A"));
		tree.left = new Tree<>(new Node<>("B"));
		tree.left.left = new Tree<>(new Node<>("D"));
		tree.left.right = new Tree<>(new Node<>("E"));
		tree.right = new Tree<>(new Node<>("C"));
		List<Node<String>> nodeList = new ArrayList<>();
		preOrder(tree, 1, nodeList);
		System.out.println("val | lft | rgt");
		for (Node<String> node : nodeList) {
			System.out.printf(" %s | %s | %s%n", node.val, node.lft, node.rgt); }}}Copy the code

By adding LFT and RGT to the nodes, we can easily find a conclusion: The LFT and RGT values of all children of a node must be between the LFT and RGT values of the node. For example, the LFT and RGT values of all children of node B are between 2 and 7. As mentioned above, the LFT of a node is set before accessing the left node of the node. Therefore, the LFT and RGT values of all the children of the node must be greater than the LFT and RGT values of the node, and the RGT value of a node is set after accessing the right node of the node. Therefore, the RGT value of the node must be greater than the LFT and RGT values of all the children of the node. We can easily query all children of a node.

In addition, if we observe carefully, we can find that the RGT value of all leaf nodes must be its LFT value plus one, so it is easy to find all leaf nodes or all leaf nodes under a node.

Database design

After introducing some of the basic concepts of MPTT, let’s take a look at its practical application by converting the above data into database storage.

Create table first:

create table mptt (
    id bigint auto_increment primary key,
    val varchar(20) not null,
    lft bigint not null,
    rgt bigint not null
);
Copy the code

Then add a few pieces of data:

insert into mptt (id, val, lft, rgt) 
	values (1.'A'.1.10), (2.'B'.2.7), (3.'D'.3.4), (4.'E'.5.6), (5.'C'.8.9);
Copy the code

These data are still corresponding to the tree structure above:

Then explain some common operations:

Query all child nodes of a node:

The following statement is used to query node B and all its children
If you want to query child nodes, drop the = sign
select id, val, lft, rgt from mptt where lft > = 2 and rgt < = 7
Copy the code

Query all leaf nodes:

select id, val, lft, rgt from mptt where lft = rgt - 1
If you want to query only the leaf nodes under a node, add restrictions on LFT and RGT
The following statement is used to query all leaf nodes under B
select id, val, lft, rgt from mptt where lft > = 2 and rgt < = 7 and lft = rgt - 1
Copy the code

Query all parent nodes of a specified node:

The following statement is used to query all the parent nodes of node D
select id, val, lft, rgt from mptt where lft < 3 and rgt > 4
Copy the code

Get the depth/level of the node:

select node.val, (count(parent.val) - 1) as deep
    from mptt as node, mptt as parent
    where node.lft between parent.lft and parent.rgt
    group by node.val
Copy the code

Add, delete and modify operations

Different from the tree structure of < ID, PID >, MPTT is more complex in the operation of add, delete and modify, which involves the LFT and RGT value Settings of add, delete and modify nodes and affected nodes. Therefore, MPTT is more suitable for query operations, but not for the tree structure requiring frequent add, delete and modify operations. The following describes how to update the LFT and RGT values of a node during the add, delete, or change operation.

Add node

In order to facilitate the operation, we increase the default node is always in its parent all child nodes of the far right, is simply assume that there is A node A, there are two child node B and C, then A new node on the right side of the C, B – > C – > D, but in the real business, we may want to control the order of the new node in the child nodes, For example, if B -> D -> C, then you only need to add a sort field to the table.

Based on the above conditions, adding a node can be divided into the following three steps. Take adding node F under node E as an example:

Obtaining a New NodeFThe parent nodeEthergt(6) value.
Will alllftandrgtGreater than or equal nodeEthergt(6) Add 2 to all values.
Insert the data of the new nodeFthelftIs its parent nodeEthergt(6),rgtAs the parent nodeEthergtGal. (7).

The changes are as follows:

val lft rgt
 E   5   8
 F   6   7
 C   10  11
 A   1   12
Copy the code

The corresponding SQL statement is as follows:

select @tmpRgt := rgt from mptt where val = 'E';

update mptt set lft = lft + 2 where lft > = @tmpRgt;
update mptt set rgt = rgt + 2 where rgt > = @tmpRgt;

insert into mptt(val, lft, rgt) values ('F'.@tmpRgt.@tmpRgt + 1);
Copy the code

Remove nodes

In fact, deleting a node can be regarded as the reverse operation of adding a node, which is also divided into three steps. Take deleting the newly added F node as an example:

Gets the node to be deletedFthergt(7) value.
deleteFNode.
Will alllftandrgtIs greater than the nodeFthergt(7) All values are reduced by 2.

The corresponding SQL statement (delete any node, if specific leaf node, @width fixed 2) is as follows:

select @tmpLft := lft, @tmpRgt := rgt, @width := rgt - lft + 1 from mptt where val = 'F';

delete from mptt where lft between @tmpLft AND @tmpRgt;

update mptt set rgt = rgt - @width where rgt > @tmpRgt;
update mptt set lft = lft - @width where lft > @tmpRgt;
Copy the code

Modify the node

If the modified node does not modify the node’s parent, is simply the nodes corresponding changes of the field, if changed the node’s parent, you can simply as a first remove the node from the old parent node, and then add the node under the new parent node, delete and add the steps refer to the above two steps. (id, val, LFT, RGT) (id, val, LFT, RGT) (id, val, LFT, RGT) (id, val, LFT, RGT)

select id, val, lft, rgt from mptt where lft < 3 and rgt > 4 order by lft desc limit 1
Copy the code

So in actual implementation below, I still chose to add a combination of LFT fell and RGT parentId field for use (in addition to being able to make it easier to find the direct parent node, it can also easily find a node child nodes directly, not need to increase the level field or more complex SQL statements of operations).

The practical application

In the end to briefly introduce based on the above ideas, and then use SpringBoot + Vue framework simple implementation of a department tree management code, here will not introduce specific code details, want to understand the direct view of the source code in the foreword, here mainly show the final effect and some design ideas.

The first is the table structure design of the database:

CREATE TABLE `sys_dept`  (
  `id` bigint(20) UNSIGNED NOT NULL COMMENT 'id',
  `parent_id` bigint(20) UNSIGNED NOT NULL COMMENT 'parent id',
  `lft` bigint(20) UNSIGNED NULL DEFAULT NULL COMMENT 'Left node',
  `rgt` bigint(20) UNSIGNED NULL DEFAULT NULL COMMENT 'Right node',
  `code` varchar(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL COMMENT 'coding',
  `name` varchar(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL COMMENT 'name',
  `gmt_create` datetime NULL DEFAULT NULL COMMENT 'Creation time',
  `gmt_modified` datetime NULL DEFAULT NULL COMMENT 'Modification time',
  `del_flag` int(2) NULL DEFAULT 0 COMMENT 'Deleted or not (0: no 1: yes)'.PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;
Copy the code

And then the final look:

conclusion

This paper briefly introduces the basic concepts of MPTT and its practical application scenarios.

The resources

[1] Monika Handayani,Muhammad Hendra,Muhammad Bahit,Noor Safrina. Traversal Tree Implementation in Chart of Account Design[P]. 1st Annual Management, Business and Economic Conference (AMBEC 2019),2020.

Simple implementation of department tree management based on MPTT

preface

Sequential traversal andMPTT

Database design

Add, delete and modify operations

Add node

Remove nodes

Modify the node

The practical application

conclusion

The resources

Related Posts

Remember a weird @async annotation failure event

Node Basics

Mariadb knowledge combing – query statement

Sequential traversal and`MPTT`