You get a bonus - 1 coin for daily activity. Now you have 1 coin

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Lecture



Introduction
At one time or another, most users were faced with building hierarchical information in an SQL database, and they realized that managing hierarchical data is clearly not the purpose of a relational database. Relational database tables are not hierarchical (similar to XML ), but simple flat lists. Hierarchical data has parent-child relationships that, naturally, are not represented in the relational database table.

In relational databases, storing information in the form of tree-like structures is a task with additional overhead. Such additional expenses can be either an increase in the number of requests or an increase in the amount of information that serves to organize the data structure.

Common approaches for organizing tree structures are:

Adjacency List
List of adjacent vertices

The organization of the data structure is that each object stores information about the parent object, that is, there is an additional field in the row of the table that indicates the ID of the object in which the object is nested.
Nested set
Nested set
Nested sets store information not only about the so-called left and right keys, as well as the level of nesting. This version of the organization of the data structure is convenient for reading, but it is more difficult to modify.
Materialized Path
Materialized way
The idea of ​​this data structure is that each record stores the full path to the root element of the tree.

Consideration of these data structures was caused by the need to introduce comments (with a tree structure) for articles to the support site.

The Adjacency List is a somewhat inconvenient solution for organizing comments, since there can be problems with finding parent objects and building a tree structure, although the approach itself allows you to quickly remove and add elements.

Nested Set is a rather cumbersome method for organizing comments on a small site, and even if you look in the direction of large resources, then under articles there are not so often 5000 comments. I was also embarrassed by the fact that it would be necessary to add a hidden root element, the so-called first empty comment in the article, from which the whole tree will be built. Why produce extra entities? - Although maybe I'm wrong. Well, the last argument against was the need to recalculate keys when adding new comments. In general, despite the advantages of this structure, within the framework of this site and its current state - this way of storing comments will become gunfire on sparrows.

Materialized Path - Each comment contains the full path. And at the same time under the article can be organized several comment trees. That is, any comment that is on the first level is automatically considered root for its tree. And when you add a new comment, you must take the full path from the future parent and add to it only the ID of the new comment. when selecting comment trees, you can sort by these arrays, which automatically allows you to place all comments in chronological order while preserving the tree structure

In our example, hierarchical data is a set of elements in which each element has one parent and zero or more children (except for the root element, which has no parents). Hierarchical data can be found in a variety of database applications, including forums and newsletters, business organization diagrams, content category management, and product categories. For our example, we will use the following hierarchy of product categories from a fictional electronics store:

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Mysql to version 8.0, it is possible to store hierarchical data in the form of nested walrus, model of the list of neighbors. Starting with version 8.0 of MYSQL, it is possible to work with table expressions to process and store hierarchical data.

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

These categories form a hierarchy, like the examples above. In this article, we will look at two models for working with hierarchical data in MySQL, starting with the traditional Adjacency List Model.

Adjacency List Model

As a rule, the examples mentioned above will be stored in a table with the following definition (I include in the example all the CREATE and INSERT expressions so that we can follow along the train of thought):


 
  1. CREATE TABLE category (
  2. category_id INT AUTO_INCREMENT PRIMARY KEY,
  3. name VARCHAR (20) NOT NULL ,
  4. parent INT DEFAULT NULL );
  5. INSERT INTO category
  6. VALUES (1, 'ELECTRONICS', NULL ), (2, 'TELEVISIONS', 1), (3, 'TUBE', 2),
  7. (4, 'LCD', 2), (5, 'PLASMA', 2), (6, 'PORTABLE ELECTRONICS', 1),
  8. (7, 'MP3 PLAYERS', 6), (8, 'FLASH', 7),

  9. (9, 'CD PLAYERS', 6), (10, '2 WAY RADIOS', 6);
  10. SELECT * FROM category ORDER BY category_id;
  11. + ------------- + ---------------------- + -------- +

  12. | category_id | name | parent |
  13. + ------------- + ---------------------- + -------- +
  14. | 1 | ELECTRONICS | NULL |
  15. | 2 | TELEVISIONS | 1 |
  16. | 3 | TUBE | 2 |

  17. | 4 | LCD | 2 |
  18. | 5 | PLASMA | 2 |
  19. | 6 | PORTABLE ELECTRONICS | 1 |
  20. | 7 | MP3 PLAYERS | 6 |
  21. | 8 | FLASH | 7 |

  22. | 9 | CD PLAYERS | 6 |
  23. | 10 | 2 WAY RADIOS | 6 |
  24. + ------------- + ---------------------- + -------- +
  25. 10 rows in set (0.00 sec)


In the adjacency list model, each element of the table contains a pointer to its parent. The topmost element, in this case ELECTRONICS , is NULL for its parents. Model adjacency has the advantage, you can quite easily see that FLASH is a child of MP3 PLAYERS , which is a child of portable electronics, which is a child of electronics. While the adjacency list model is fairly easy to implement, there may be a problem with SQL implementations.

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Getting a full tree

The first common task when working with hierarchical data is to display the entire tree, as a rule, with different depths. The most common way to do this is in pure SQL , by combining tables:


 
  1. SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
  2. FROM category AS t1
  3. LEFT JOIN category AS t2 ON t2.parent = t1.category_id
  4. LEFT JOIN category AS t3 ON t3.parent = t2.category_id
  5. LEFT JOIN category AS t4 ON t4.parent = t3.category_id

  6. WHERE t1.name = 'ELECTRONICS';
  7. + ------------- + ---------------------- + ------------ - + ------- +
  8. | lev1 | lev2 | lev3 | lev4 |
  9. + ------------- + ---------------------- + ------------ - + ------- +
  10. | ELECTRONICS | TELEVISIONS | TUBE | NULL |

  11. | ELECTRONICS | TELEVISIONS | LCD | NULL |
  12. | ELECTRONICS | TELEVISIONS | PLASMA | NULL |
  13. | ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |
  14. | ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS | NULL |
  15. | ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL |

  16. + ------------- + ---------------------- + ------------ - + ------- +
  17. 6 rows in set (0.00 sec)

View all leaf nodes

We can find all the nodes in the tree (i.e. without children) using


 
  1. LEFT JOIN, query:
  2. SELECT t1.name FROM
  3. category AS t1 LEFT JOIN category as t2
  4. ON t1.category_id = t2.parent
  5. WHERE t2.category_id IS NULL ;

  6. + -------------- +
  7. | name |
  8. + -------------- +

  9. | TUBE |
  10. | LCD |
  11. | PLASMA |
  12. | FLASH |
  13. | CD PLAYERS |

  14. | 2 WAY RADIOS |
  15. + -------------- +


Getting one way
Combining also allows us to see the full path of our hierarchy:


 
  1. SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
  2. FROM category AS t1
  3. LEFT JOIN category AS t2 ON t2.parent = t1.category_id
  4. LEFT JOIN category AS t3 ON t3.parent = t2.category_id
  5. LEFT JOIN category AS t4 ON t4.parent = t3.category_id

  6. WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';
  7. + ------------- + ---------------------- + ------------ - + ------- +
  8. | lev1 | lev2 | lev3 | lev4 |
  9. + ------------- + ---------------------- + ------------ - + ------- +
  10. | ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |

  11. + ------------- + ---------------------- + ------------ - + ------- +
  12. 1 row in set (0.01 sec)


The main limitation of this approach is that you need to combine for each level in the hierarchy, and the performance will deteriorate significantly with each added level, the complexity will increase.

Limitations of the Approximate Adjacency List

Working with a model adjacency list in pure SQL can be difficult at best. Before you see the full path to the category, we need to know at what level it is located. In addition, special attention should be paid to the removal of nodes due to the possibility of orphaning the entire branch (remove the category of portable electronics category and all its orphans). Some of these limitations can be resolved using client code or stored procedures. With procedural language, we can start at the bottom of the tree and repeat upwards the return of a full tree or one path. We can also use procedural programming to remove the nodes of an entire branch without orphanhood, promoting one child and changing the order of the rest of the children to point to the new parent.

Extended list of ridiculousness (sessions) in databases

sometimes add special fields of the level path in which to contain information about the node and the path to the parents

another kind of storage of the list of neighbors using the binary Materialized Path

Solving the problem of sorting trees using a binary Materialized Path


use not decimal IDs in the path, but encode to another number system in order to have less restrictions
in the length of the path. At the same time, separators in the form of dots or other characters are not needed, since the field will be
used only for sorting.
You can use the base 95, this is just the number of printable characters in ASCII.
If for each value in the path we use a fixed length, we get the following upper threshold ID:
1 - 95 ^ 1 - 1 = 94
2 - 95 ^ 2 - 1 = 9,024
3 - 95 ^ 3 - 1 = 857 374
4 - 95 ^ 4 - 1 = 81 450 624
5 - 95 ^ 5 - 1 = 7 737 809 374

5 characters is enough to not worry about the maximum number of comments.
The maximum level of nesting, in this case, for VARCHAR 255/5 = 51

Theoretically, it is possible to take not BASE95, but BASE256 (together with non-printing characters),
but storing it all is binary in a blob, although I’m not sure about performance with
sorting (need to check). Then by 3 characters we could encode
16,777,215 options, and 4–4,294,967,295.

/ * sorting nested comments along the way * /

function bpath ($ mpath, $ sep = '/', $ max_len = 5) {

$ bpath = ";

$ chunks = explode ($ sep, trim ($ mpath, $ sep));

$ zero = substr (BASE95, 0, 1);

foreach ($ chunks as $ chunk)

$ bpath. = str_pad ($ this-> dec2base ($ chunk, 95, $ BASE95), $ max_len, $ zero, STR_PAD_LEFT);

return $ bpath;

}

// convert a base value

function dec2base ($ dec, $ base, $ digits = FALSE) {

if ($ base <2 or $ base> 256) return error ("Invalid Base:". $ base, 0);
bcscale (0);
$ value = "";
if (! $ digits) $ digits = digits ($ base);
while ($ dec> $ base-1) {
$ rest = bcmod ($ dec, $ base);
$ dec = bcdiv ($ dec, $ base);
$ value = $ digits [$ rest]. $ value;
}
$ value = $ digits [intval ($ dec)]. $ value;
return (string) $ value;
}


$ BASE95 = '! "# $% & \' () * +, -. / 0123456789:; <=>? @ ABCDEFGHIJKLMNOPQRSTUVWXYZ [\] ^ _` abcdefghijklmnopqrstuvwxyz {|} ~ ';

The Nested Set Model

What I would like to dwell on in this article is a different approach, called, as a rule, the Nested Set Model . In the nested set model, we can look at our hierarchy in a new way, not as nodes and lines, but as nested containers. Let's try to draw our electronics categories as follows:

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Please note that our hierarchy is still preserved; parent categories retain children. We represent this form of hierarchy in a table using pointers to the left and right nodes in our sets:


 
  1. CREATE TABLE nested_category (
  2. category_id INT AUTO_INCREMENT PRIMARY KEY,
  3. name VARCHAR (20) NOT NULL ,
  4. lft int NOT NULL ,
  5. rgt INT NOT NULL

  6. );
  7. INSERT INTO nested_category
  8. VALUES (1, 'ELECTRONICS', 1,20), (2, 'TELEVISIONS', 2,9), (3, 'TUBE', 3,4),

  9. (4, 'LCD', 5,6), (5, 'PLASMA', 7,8), (6, 'PORTABLE ELECTRONICS', 10,19),
  10. (7, 'MP3 PLAYERS', 11,14), (8, 'FLASH', 12,13),
  11. (9, 'CD PLAYERS', 15,16), (10, '2 WAY RADIOS', 17,18);
  12. SELECT * FROM nested_category ORDER BY category_id;
  13. + ------------- + ---------------------- + ----- + ----- +
  14. | category_id | name | lft | rgt |

  15. + ------------- + ---------------------- + ----- + ----- +
  16. | 1 | ELECTRONICS | 1 | 20 |
  17. | 2 | TELEVISIONS | 2 | 9 |
  18. | 3 | TUBE | 3 | 4 |
  19. | 4 | LCD | 5 | 6 |

  20. | 5 | PLASMA | 7 | 8 |
  21. | 6 | PORTABLE ELECTRONICS | 10 | 19 |
  22. | 7 | MP3 PLAYERS | 11 | 14 |
  23. | 8 | FLASH | 12 | 13 |
  24. | 9 | CD PLAYERS | 15 | 16 |

  25. | 10 | 2 WAY RADIOS | 17 | 18 |
  26. + ------------- + ---------------------- + ----- + ----- +


We use lft and rgt because left and right are MySQL reserved words; see http://dev.mysql.com/doc/mysql/en/reserved-words.html for a full list of reserved words.

So how do we define left and right values? We start numbering on the left side of the external nodes and continue to the right:

This design can be represented by a typical tree, as in the image:

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

When working with a tree, we work from left to right, one layer after another, going down to the children of each node before assigning rgt and moving to the right. Such an approach is called a change in the tree traversal algorithm (preorder tree traversal algorithm).

Getting a full tree

We can get a complete tree using a join that binds parents to nodes on the basis that the lft value of the node will always appear between its parent's lft and the rgt value:


 
  1. SELECT node.name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. AND parent.name = 'ELECTRONICS'

  6. ORDER BY node.lft;
  7. + ---------------------- +
  8. | name |

  9. + ---------------------- +
  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |

  14. | PLASMA |
  15. | PORTABLE ELECTRONICS |
  16. | MP3 PLAYERS |
  17. | FLASH |
  18. | CD PLAYERS |

  19. | 2 WAY RADIOS |
  20. + ---------------------- +


Unlike our previous model with the adjacency list model, this query will work regardless of the tree depth. We do not deal with the value of the rgt node in our predicate BETWEEN , since the value of rgt always falls under the same parents as the lft values.

Finding all end nodes

Finding all the nodes in the nested set model is even simpler than the LEFT JOIN method used in the adjacency list model. If you look at the nested_category table, you may notice that the LFT and RGT values ​​for the end nodes are consecutive numbers. To find the end nodes, we look for nodes where rgt = lft + 1 :


 
  1. SELECT name
  2. FROM nested_category
  3. WHERE rgt = lft + 1;
  4. + -------------- +
  5. | name |
  6. + -------------- +
  7. | TUBE |
  8. | LCD |

  9. | PLASMA |
  10. | FLASH |
  11. | CD PLAYERS |
  12. | 2 WAY RADIOS |
  13. + -------------- +


Getting one way

With the model of nested sets, we can get one path without forming several table joins:


 
  1. SELECT parent.name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. AND node.name = 'FLASH'

  6. ORDER BY parent.lft;
  7. + ---------------------- +
  8. | name |
  9. + ---------------------- +

  10. | ELECTRONICS |
  11. | PORTABLE ELECTRONICS |
  12. | MP3 PLAYERS |
  13. | FLASH |
  14. + ---------------------- +


Determination of knot depth

We have already looked at how the entire tree is shown, but what if we also want to show the depth of each node in the tree to better determine how each node is placed in the hierarchy? This can be done by adding the COUNT function and the predicate (clause) GROUP BY to our existing queries to display the entire tree:


 
  1. SELECT node.name, (COUNT (parent.name) - 1) AS depth
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. + ---------------------- + ------- +
  8. | name | depth |
  9. + ---------------------- + ------- +

  10. | ELECTRONICS | 0 |
  11. | TELEVISIONS | 1 |
  12. | TUBE | 2 |
  13. | LCD | 2 |
  14. | PLASMA | 2 |

  15. | PORTABLE ELECTRONICS | 1 |
  16. | MP3 PLAYERS | 2 |
  17. | FLASH | 3 |
  18. | CD PLAYERS | 2 |
  19. | 2 WAY RADIOS | 2 |

  20. + ---------------------- + ------- +


We can use the depth value to indent with our categories using the CONCAT and REPEAT string functions.


 
  1. SELECT CONCAT (REPEAT ('', COUNT (parent.name) - 1), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. + ----------------------- +
  8. | name |
  9. + ----------------------- +

  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |
  14. | PLASMA |

  15. | PORTABLE ELECTRONICS |
  16. | MP3 PLAYERS |
  17. | FLASH |
  18. | CD PLAYERS |
  19. | 2 WAY RADIOS |

  20. + ----------------------- +


Of course, in the client application, you will often use the depth value directly to display the hierarchy. Web developers can repeat the loop on the tree by adding tags

and

as the size of the depth increases and decreases.

Subtree depth (branches)

When we need detailed information about a branch, we cannot limit the node or parent tables in our union (self-join), because it will spoil our results. Instead, we will add a third join, as well as a subquery, to determine the depth that will be the new starting point for our branch:


 
  1. SELECT node.name, (COUNT (parent.name) - (sub_tree.depth + 1)) AS depth
  2. FROM nested_category AS node,
  3. nested_category AS parent,
  4. nested_category AS sub_parent,
  5. (

  6. SELECT node.name, (COUNT (parent.name) - 1) AS depth
  7. FROM nested_category AS node,
  8. nested_category AS parent
  9. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  10. AND node.name = 'PORTABLE ELECTRONICS'

  11. GROUP BY node.name
  12. ORDER BY node.lft
  13. ) AS sub_tree
  14. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  15. AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt

  16. AND sub_parent.name = sub_tree.name
  17. GROUP BY node.name
  18. ORDER BY node.lft;
  19. + ---------------------- + ------- +
  20. | name | depth |
  21. + ---------------------- + ------- +
  22. | PORTABLE ELECTRONICS | 0 |
  23. | MP3 PLAYERS | 1 |

  24. | FLASH | 2 |
  25. | CD PLAYERS | 1 |
  26. | 2 WAY RADIOS | 1 |
  27. + ---------------------- + ------- +


This function can be used with any node name, including the root node. The depth values ​​are always relative to the node name.
Finding immediate subordinate nodes

Imagine that you are showing the categories of electronics products on the seller’s website. When a user clicks on a category, you want the products of this category to be displayed, and also its subcategories are listed immediately, but not the entire category tree under it. To do this, we need to show the nodes and its immediate subnodes, but not lower down the tree. For example, when showing the category PORTABLE ELECTRONICS , we want to show MP3 PLAYERS , CD PLAYERS and 2 WAY RADIOS , but not FLASH .

This can be easily done by adding a HAVING clause to our previous queries:


 
  1. SELECT node.name, (COUNT (parent.name) - (sub_tree.depth + 1)) AS depth
  2. FROM nested_category AS node,
  3. nested_category AS parent,
  4. nested_category AS sub_parent,
  5. (

  6. SELECT node.name, (COUNT (parent.name) - 1) AS depth
  7. FROM nested_category AS node,
  8. nested_category AS parent
  9. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  10. AND node.name = 'PORTABLE ELECTRONICS'

  11. GROUP BY node.name
  12. ORDER BY node.lft
  13. ) AS sub_tree
  14. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  15. AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt

  16. AND sub_parent.name = sub_tree.name
  17. GROUP BY node.name
  18. HAVING depth <= 1
  19. ORDER BY node.lft;
  20. + ---------------------- + ------- +
  21. | name | depth |
  22. + ---------------------- + ------- +
  23. | PORTABLE ELECTRONICS | 0 |
  24. | MP3 PLAYERS | 1 |

  25. | CD PLAYERS | 1 |
  26. | 2 WAY RADIOS | 1 |
  27. + ---------------------- + ------- +


If you do not want the parent node to be displayed, change the HAVING depth <= 1 to HAVING depth = 1 .

Aggregation functions in nested sets

Let's add a table of products that we can use to demonstrate the aggregate functions:


 
  1. CREATE TABLE product (
  2. product_id INT AUTO_INCREMENT PRIMARY KEY,
  3. name varchar (40)
  4. category_id INT NOT NULL
  5. );

  6. INSERT INTO product (name, category_id) VALUES ('20 "TV ', 3), (' 36" TV ', 3),
  7. ('Super-LCD 42"',4),('Ultra-Plasma 62"',5),('Value Plasma 38"',5),
  8. ('Power-MP3 5gb',7),('Super-Player 1gb',8),('Porta CD',9),('CD To go!',9),

  9. ('Family Talk 360',10);
  10. SELECT * FROM product;
  11. +------------+-------------------+-------------+

  12. | product_id | name | category_id |
  13. +------------+-------------------+-------------+
  14. | 1 | 20" TV | 3 |
  15. | 2 | 36" TV | 3 |
  16. | 3 | Super-LCD 42" | 4 |

  17. | 4 | Ultra-Plasma 62" | 5 |
  18. | 5 | Value Plasma 38" | 5 |
  19. | 6 | Power-MP3 128mb | 7 |
  20. | 7 | Super-Shuffle 1gb | 8 |
  21. | 8 | Porta CD | 9 |

  22. | 9 | CD To go! | 9 |
  23. | 10 | Family Talk 360 | 10 |
  24. +------------+-------------------+-------------+


Теперь давайте выполним запрос, который сможет получить дерево наших категорий, а также количество продуктов по каждой категории:


 
  1. SELECT parent.name, COUNT(product.name)
  2. FROM nested_category AS node ,
  3. nested_category AS parent,
  4. product
  5. WHERE node.lft BETWEEN parent.lft AND parent.rgt

  6. AND node.category_id = product.category_id
  7. GROUP BY parent.name
  8. ORDER BY node.lft;
  9. +----------------------+---------------------+
  10. | name | COUNT(product.name) |
  11. +----------------------+---------------------+
  12. | ELECTRONICS | 10 |
  13. | TELEVISIONS | 5 |

  14. | TUBE | 2 |
  15. | LCD | 1 |
  16. | PLASMA | 2 |
  17. | PORTABLE ELECTRONICS | 5 |
  18. | MP3 PLAYERS | 2 |

  19. | FLASH | 1 |
  20. | CD PLAYERS | 2 |
  21. | 2 WAY RADIOS | 1 |
  22. +----------------------+---------------------+


Это наше типичное целое дерево запроса с добавленными COUNT и GROUP BY , наряду со ссылкой на продукт таблицы и соединением между узлом и продуктами таблицы в предикате WHERE . Как вы видите, есть запись для каждой категории и число подкатегорий содержащихся в родительских категориях.

Добавление новых узлов

Теперь, когда мы узнали, как получить наше дерево, мы должны взглянуть на то, как обновить наше дерево путем добавления новых узлов. Давайте посмотрим на нашу схему модели вложенных множеств снова:

Working with hierarchical data in MySQL (Adjacency List List of Adjacent Vertices, Nested Set Nested Set, Materialized Path Materialized Path)

Если мы хотим добавить новый узел между узлами TELEVISIONS и PORTABLE ELECTRONICS , новый узел будет иметь lft и rgt значения 10 и 11, и все его узлы справа будут иметь свои lft и rgt значения увеличена на два. Затем мы добавляем новый узел с соответствующим значениями lft и rgt . Хотя это может быть сделано с помощью хранимых процедур в MySQL 5 , я буду считать, что в данный момент большинство читателей используют 4.1, так как это последняя стабильная версия, и я буду изолировать мой запрос с выражением LOCK TABLES :


 
  1. LOCK TABLE nested_category WRITE;
  2. SELECT @myRight := rgt FROM nested_category
  3. WHERE name = 'TELEVISIONS';

  4. UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
  5. UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

  6. INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);
  7. UNLOCK TABLES;

Мы можем проверить наши вложения с нашими отступом дерева запроса:


 
  1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. +-----------------------+
  8. | name |

  9. +-----------------------+
  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |

  14. | PLASMA |
  15. | GAME CONSOLES |
  16. | PORTABLE ELECTRONICS |
  17. | MP3 PLAYERS |
  18. | FLASH |

  19. | CD PLAYERS |
  20. | 2 WAY RADIOS |
  21. +-----------------------+


Если вместо этого мы хотим добавить узел в качестве дочернего узла, который не имеет существующих детей, мы должны немного изменить наши процедуры. Давайте добавим новый узел FRS ниже узла 2 WAY RADIOS :


 
  1. LOCK TABLE nested_category WRITE;
  2. SELECT @myLeft := lft FROM nested_category
  3. WHERE name = '2 WAY RADIOS';

  4. UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
  5. UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;
  6. INSERT INTO nested_category(name, lft, rgt) VALUES('FRS', @myLeft + 1, @myLeft + 2);

  7. UNLOCK TABLES;


Как видите, наш новый узел теперь правильно вложен:


 
  1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. +-----------------------+
  8. | name |

  9. +-----------------------+
  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |

  14. | PLASMA |
  15. | GAME CONSOLES |
  16. | PORTABLE ELECTRONICS |
  17. | MP3 PLAYERS |
  18. | FLASH |

  19. | CD PLAYERS |
  20. | 2 WAY RADIOS |
  21. | FRS |
  22. +-----------------------+

Удаление узлов

Последние основной задачей в работе с вложенными множествами заключается в удалении узлов. Набор ваших действий при удалении узла, зависит от положения узла в иерархии, удаление сделать листьев легче, чем удаление узлов с детьми, потому что мы должны обращаться с сиротами узлов.

При удалении листа узла, в отличие от добавления новых узлов, мы удаляем узел и его ширину от каждого узла правее:


 
  1. LOCK TABLE nested_category WRITE;
  2. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
  3. FROM nested_category

  4. WHERE name = 'GAME CONSOLES';
  5. DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
  6. UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
  7. UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
  8. UNLOCK TABLES;

И опять, мы выполняем запрос оформляя отступы в дереве, чтобы подтвердить что наш узел был удален без нарушения иерархии:


 
  1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. +-----------------------+
  8. | name |

  9. +-----------------------+
  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |

  14. | PLASMA |
  15. | PORTABLE ELECTRONICS |
  16. | MP3 PLAYERS |
  17. | FLASH |
  18. | CD PLAYERS |

  19. | 2 WAY RADIOS |
  20. | FRS |
  21. +-----------------------+


Этот подход работает одинаково хорошо при удалении узла и всех его детей:


 
  1. LOCK TABLE nested_category WRITE;
  2. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
  3. FROM nested_category

  4. WHERE name = 'MP3 PLAYERS';
  5. DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
  6. UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
  7. UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
  8. UNLOCK TABLES;


И опять, мы запрашиваем, чтобы увидеть, успешно ли мы удалили все ветки:


 
  1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. +-----------------------+
  8. | name |

  9. +-----------------------+
  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |

  14. | PLASMA |
  15. | PORTABLE ELECTRONICS |
  16. | CD PLAYERS |
  17. | 2 WAY RADIOS |
  18. | FRS |

  19. +-----------------------+

Другой сценарий, который можно использовать при удаление родительского узла, а не детей. В некоторых случаях вы можете просто изменить название заполнителя до замены представлены, например, когда увольняют руководителя. В других случаях, дочерние узлы должны быть подняты до уровня удаленного родителя:


 
  1. LOCK TABLE nested_category WRITE;
  2. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
  3. FROM nested_category

  4. WHERE name = 'PORTABLE ELECTRONICS';
  5. DELETE FROM nested_category WHERE lft = @myLeft;
  6. UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
  7. UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
  8. UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
  9. UNLOCK TABLES;

В этом случае мы вычитаем два от всех элементов справа от узла (так как без детей, это будет иметь ширину двух), и один из узлов, которые являются его дети (чтобы закрыть пробел, созданный потерей левой родителей значение). Еще раз, мы можем подтвердить наши элементы были повышены:


 
  1. SELECT CONCAT( REPEAT( ' ', (COUNT(parent.name) - 1) ), node.name) AS name
  2. FROM nested_category AS node,
  3. nested_category AS parent
  4. WHERE node.lft BETWEEN parent.lft AND parent.rgt
  5. GROUP BY node.name

  6. ORDER BY node.lft;
  7. +---------------+
  8. | name |

  9. +---------------+
  10. | ELECTRONICS |
  11. | TELEVISIONS |
  12. | TUBE |
  13. | LCD |

  14. | PLASMA |
  15. | CD PLAYERS |
  16. | 2 WAY RADIOS |
  17. | FRS |
  18. +---------------+


Другие сценарии при удалении узлов будут включать содействие одному из детей родители положение и перемещение ребенка узлов под братом родительский узел, но ради пространство этих сценариев не рассматривается в этой статье.

Заключительное слово
Хотя я надеюсь, что информация в данной статье, будет полезна для вас, концепция вложенных множеств в SQL была вокруг в течение более десяти лет, и есть много дополнительной информации, имеющейся в книгах и в интернете. На мой взгляд, наиболее полным источником информации об управлении иерархической информации является книга под названием Деревья Джо Celko и иерархии в SQL для Smarties, написанная очень уважаемым автором в области передовых SQL, Джо Celko. Джо Celko часто приписывают модель вложенных множеств и на сегодняшний день является самым плодовитым автором по этому вопросу. Я нашел книгу Celkoto be an invaluable resource in your research and highly recommend it. The book discusses complex issues that I am not in this article, and also provides additional methods for managing hierarchical data in addition to the adjacency list and nested Set models.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

MySql (Maria DB)

Terms: MySql (Maria DB)