Method a parent node representation

Each node holds a reference to the parent node. In order to better process the forest, abstract a non-existent 0 node, all trees in the forest hang under the node, and convert the forest into a tree for processing.

CREATE TABLE node1 ( id INT AUTO_INCREMENT PRIMARY KEY , name VARCHAR(12) NOT NULL, Num INT NOT NULL DEFAULT 0 COMMENT ', p_id INT NOT NULL DEFAULT 0 COMMENT ');Copy the code

This method is simple in structure and update, but inefficient in querying descendant nodes.

Method two: path representation

Add the path_key (search_key) field to the first method, which stores the identified path from the root node to the node, again abstracting a nonexistent 0 node.

CREATE TABLE node2 ( id INT AUTO_INCREMENT PRIMARY KEY , name VARCHAR(12) NOT NULL , Num INT NOT NULL DEFAULT 0 COMMENT ' ', p_id INT NOT NULL DEFAULT 0 COMMENT ' ' ', Search_key VARCHAR(128) DEFAULT '' COMMENT ', level INT DEFAULT 0 COMMENT '); search_key VARCHAR(128) DEFAULT '' COMMENT ');Copy the code

Insert data

INSERT INTO 2 (id, name, num, p_id, search_key) VALUES (1, 'A', 10, 0, '0 and 1), (2,' B ', 7, 1, '0-1-2), (3, "C",, 1, 3' 0-1-3), (4, 'D', 1, 3, '0-1-3-4), (5,' E ', 2, 3, '0-1-3-5), (6,' F ', 2, 0, '0 to 6), (7,' G ', 2, 6, '0-6-7);Copy the code

Query data

SELECT * FROM node2 WHERE p_id = 0 AND search_key LIKE '0-%' AND level = 0; ##### SELECT * FROM node2 WHERE search_key LIKE '{a.search_key}%'; SELECT * FROM node2 WHERE search_key LIKE '0-1-%';Copy the code

Update data (when a certain number of leaf nodes are inserted)

#, for instance, UPDATE node2,(SELECT sum(num) AS sum FROM node2 WHERE search_key LIKE '0-1-3-%') rt SET num = rt.sum WHERE search_key = '0-1-3-% id=3;Copy the code

When the weights of nodes are accumulated, add 1 to the weights of all parents, just divide search_key of this node with ‘-‘, and get the ids of all parents (except 0). For example, if the weight of node D is +1, using where locate, it is actually better to split search_key first and then use where in

UPDATE node2,(SELECT search_key FROM node2 WHERE id = 4) rt SET num=num+1 WHERE locate(id,rt.search_key);
Copy the code

Delete a node, for example, node B

Assume that all descendants of deleted nodes are deleted

DELETE FROM node2 WHERE search_key LIKE '0-1-2%';
Copy the code

Method 3: Sequential traversal

Assign left and right values to the node, set the lvalue when the node is reached for the first time, set the rvalue when the node is reached for the second time, and increment the serial number by 1 for each step

CREATE TABLE node3 (id INT AUTO_INCREMENT PRIMARY KEY, tree_id INT NOT NULL COMMENT ' Name VARCHAR(12) NOT NULL, num INT NOT NULL DEFAULT 0 COMMENT '表 示 数 据, 表 示 数 据 ', LFT INT NOT NULL, rgt INT NOT NULL , level INT DEFAULT 0 ); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (1,'B',7,2,3,2); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (1,'D',1,5,6,3); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (1,'E',2,7,8,3); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (1,'C',3,4,9,2); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (1,'A',10,1,10,1); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (2,'G',2,2,3,2); Insert into node3 (tree_id, name, num, LFT, RGT, level) VALUE (2,'F',2,1,4,1);Copy the code

A tree_ID field is added here to ensure that the update operation on one tree will not affect other trees, which is beneficial to improve efficiency.

Insert data (use tree_id to determine if it is the same tree)It can be found that if there is an append node M under a node, the left and right values of M should be continuous, and the left and right values of the following nodes should be +2 respectively, and the rvalue of the parent node of M must also be +2.

Query data

Select * from node3 where LFT < LFT && RGT < RGT select * from node3 where LFT < LFT && RGT > RGTCopy the code