Shulou(Shulou.com)06/03 Report--

Today, I will talk to you about the database table design of Mysql tree structure, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following contents for you. I hope you can get something according to this article.

Preface

Recently, I have looked for a lot of examples of tree menu on the Internet. The following is some information found on the Internet, and then practice it again, so as not to forget it next time.

In the process of programming, we often use tree structure to represent the relationship of some data, such as enterprise superior and subordinate departments, column structure, commodity classification and so on. Generally speaking, these tree structures need to be persisted with the help of database. However, at present, all kinds of relational databases record and store data information in the form of two-dimensional tables, so Tree can not be directly stored in DBMS. The design of appropriate Schema and its corresponding CRUD algorithm is the key to realize the storage tree structure in relational databases.

Ideally, the tree structure should have the following characteristics: small data storage redundancy and strong intuition; simple and efficient retrieval and traversal process; efficient CRUD operation of node addition, deletion, modification and query. Accidentally found a very ingenious design on the Internet, the original text is in English, after reading it, I felt a little interesting, so I sorted it out. This paper will introduce two kinds of Schema design schemes with tree structure: one is an intuitive and simple design idea, and the other is an improved scheme based on left and right value coding.

I. basic data

In this paper, an example of food genealogy is given to explain. Food is organized by category, color and variety. The tree structure is as follows:

Second, inheritance relationship-driven design

The most intuitive analysis of the tree structure is that a two-dimensional relational table can be established by explicitly describing the parent node of a node, then the Tree table structure of this scheme is usually designed as: {Node_id,Parent_id}, the above data can be described as shown in the following figure:

The advantage of this scheme is obvious: the design and implementation are natural, very intuitive and convenient. The disadvantage is, of course, unusual: because the inheritance relationship between nodes is directly recorded, any CRUD operation on Tree will be inefficient, which is mainly due to frequent "recursive" operations, the recursive process constantly accesses the database, and each database IO has a time overhead. Of course, this scheme is not without the opportunity to exert its ability. When the scale of Tree is relatively small, we can make optimization with the help of cache mechanism to load the information of Tree into memory for processing, so as to avoid the performance overhead of database IO operation directly.

Third, the design based on left and right value coding

In general applications based on database, the requirement of query is always greater than that of deletion and modification. In order to avoid the "recursive" process of tree structure query, a new left and right value coding scheme without recursion query and infinite grouping is designed based on the preorder traversal of Tree to save the data of the tree.

When you see this table structure for the first time, I believe most people do not know how the left value (Lft) and right value (Rgt) are calculated, and this table design does not seem to preserve the inheritance relationship between the parent and child nodes. But when you point your finger at the numbers in the table from 1 to 18, you should find something. Yes, the order in which you move your fingers is the order in which you traverse the tree in pre-order, as shown in the following figure. When we start on the left side of the root node Food, mark it as 1, and mark the traversal path with numbers along the direction of the preorder traversal, finally we go back to the root node Food and write 18 on the right.

According to this design, we can infer that all nodes with left values greater than 2 and right values less than 11 are subsequent nodes of Fruit, and the structure of the whole tree is stored by left and right values. However, this is not enough, our goal is to be able to CRUD the tree, that is, we need to construct a corresponding algorithm.

4. Tree structure CRUD algorithm (1) to obtain the descendant nodes of a node

You only need a SQL statement to return the preorder traversal list of the descendants of this node. Take Fruit as an example:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC

The query results are as follows:

So how many descendant nodes are there in a node? Through the left and right values of the node, we can circle its descendant nodes, then the total number of descendants = (right-left-1) / 2, taking Fruit as an example, the total number of descendants is (11-2-1) / 2 = 4. At the same time, in order to show the tree structure more intuitively, we need to know the level of the node in the tree, which can be realized by SQL query of left and right values. Take Fruit as an example: SELECTCOUNT (*) FROM tree WHERE lft = 11. To facilitate description, we can create a view for Tree and add a hierarchical series of values that can be calculated by writing a custom function, which is defined as follows:

Create a tabl

CREATE TABLE `tree` (`id` int (11) NOT NULL, `name` varchar (255) DEFAULT NULL, `lft` int (255) DEFAULT NULL, `rgt` int (11) DEFAULT NULL) ENGINE=InnoDB DEFAULT CHARSET=utf8;INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('1Qing,' Food', '1Qing,' 18'); INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('2', 'Fruit',' 2,'11') INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('3Qing,' Red', '3levels,' 6'); INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('44th,' Cherry', '44th,' 5'); INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('5', 'Yellow',' 7', '10') INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('6years,' Banana', '8levels,' 9'); INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('7levels,' Meat', '12cycles,' 17'); INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('84th,' Beef', '130s,' 14') INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('999,' Pork', '1515,' 16'); CREATE VIEW `treeview`AS SELECT `a`.`id`AS `id`, `a`.`name` AS `name`, `a`.`lft` AS `lft`, `a`.`rgt` AS `rgt`, `CountLayer` (`a`.`id`) AS `layer`FROM `tree`a`

Based on the hierarchical calculation function, we create a view and add a new sequence of records node hierarchy:

> CREATE FUNCTION `CountLayer` (`CountLayer` (`CountLayer`) RETURNS INT (11) BEGIN DECLARE result INT (10) DEFAULT 0; DECLARE lftid INT; DECLARE rgtid INT; SELECT lft,rgt INTO lftid, rgtid FROM tree WHERE id = node_id; SELECT COUNT (*) INTO result FROM tree WHERE lft = rgtid; RETURN (result); END

Create a stored procedure that calculates all descendant nodes of a given node and the corresponding hierarchy:

CREATE PROCEDURE `GetChildrenNodeList` (IN `GetChildrenNodeList` INT) BEGINDECLARE lftid INT;DECLARE rgtid INT;SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;SELECT * FROM treeview WHERE lft BETWEEN lftid AND rgtid ORDER BY lft ASC;END

Now, we use the above stored procedure to calculate all descendant nodes and their corresponding levels of the node Fruit. The query results are as follows:

From the above implementation, we can see that the design scheme using left and right value coding only needs to do two database queries during the query traversal of the tree, eliminating recursion, coupled with the comparison of query conditions are numeric. The efficiency of the query is extremely high. With the continuous expansion of the tree scale, the design scheme based on left and right value coding will improve the query efficiency more than the traditional recursive scheme. Of course, we only give a simple algorithm to get the descendants of nodes. In order to really use this tree, we need to insert and delete translation nodes on the same layer and other functions.

(2) obtain the genealogical path of a node

Suppose we want to get the genealogical path of a node, then according to the left and right values, only one SQL statement is needed to complete the analysis. Take Fruit as an example: SELECT* FROM tree WHERE lft

11 ORDER BY lft ASC, relatively complete stored procedures:

CREATE PROCEDURE `GetParentNodePath` (IN `GetParentNodePath` INT) BEGINDECLARE lftid INT;DECLARE rgtid INT;SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;SELECT * FROM treeview WHERE lft

Rgtid ORDER BY lft ASC;END (3) add a descendant node to a node

Suppose we want to add a new child node "Apple" under the node "Red", and the tree will become as shown in the following figure, where the red node is the new node.

CREATE PROCEDURE `AddSubNode` (IN `AddSubNode` (IN `AddSubNode`) node_ name` VARCHAR (64)) BEGIN DECLARE rgtid INT; DECLARE t_error INT DEFAULT 0; DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET tweak errorhandling 1;-- error handling SELECT rgt INTO rgtid FROM tree WHERE id= node_id; START TRANSACTION; UPDATE tree SET rgt = rgt + 2 WHERE rgt > = rgtid; UPDATE tree SET lft = lft + 2 WHERE lft > = rgtid; INSERT INTO tree (NAME,lft,rgt) VALUES (node_name,rgtid,rgtid+1) IF t_error = 1 THEN ROLLBACK; ELSE COMMIT; END IF;END (4) Delete a node

If we want to delete a node, all descendants of that node will be deleted at the same time, and the number of deleted nodes is: (right value of deleted node-left value of deleted node + 1) / 2. The left and right values of the remaining nodes will be adjusted when they are greater than the left and right values of the deleted node. Let's see what happens to the tree. Take Beef as an example, the deletion effect is shown in the following figure.

Then we can construct the corresponding stored procedure:

CREATE PROCEDURE `DelNode` (IN `DelNode` INT) BEGIN DECLARE lftid INT; DECLARE rgtid INT; DECLARE t_error INT DEFAULT 0; DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET tweak errorhandling 1;-- error handling SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id; START TRANSACTION; DELETE FROM tree WHERE lft > = lftid AND rgt lftid; UPDATE tree SET rgt = rgt-(rgtid-lftid + 1) WHERE rgt > rgtid; IF t_error=1 THEN ROLLBACK; ELSE COMMIT END IF; end V. Summary

We can make a summary of this tree structure Schema design scheme which achieves infinite grouping by left and right value coding:

(1) advantage: infinite grouping is realized on the premise of eliminating recursive operation, and the query condition is based on the comparison of shaping numbers, which is very efficient.

(2) disadvantages: the cost of adding, deleting and modifying nodes is high, and it will involve changes in many aspects of the data in the table.

After reading the above, do you have any further understanding of the database table design of Mysql tree structure? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.