Tree data structure storage method (CUD)

The previous article briefly introduces the data model of nested collections, as well as the query method, portal: Tree data structure storage method (query)

Create

In the nested collection model, each data is actually a node, and each node occupies 2 bit values. For example, let's start by adding a first-level node of Smartphones.

INSERT INTO `categories` (`title`, `lft`, `rgt`) VALUES('Smartphones', 1, 2);

Smartphones As a main node (root), its lft must be 1, and the value of rgt will increase as the number of child elements in its collection increases.

Now, we want to add a child element Android within Smartphones. Use mysql stored procedures.

LOCK TABLE categories WRITE;
SELECT @root_left := lft FROM categories WHERE title = 'Smartphones';
UPDATE categories SET rgt = rgt + 2 WHERE rgt > @root_left;
UPDATE categories SET lft = lft + 2 WHERE lft > @root_left;
INSERT INTO categories (title, lft, rgt) VALUES('Android', @root_left + 1, @root_left + 2);
UNLOCK TABLES;
SELECT `title`, `lft`, `rgt` FROM `categories`;
+-------------+-----+-----+
| title       | lft | rgt |
+-------------+-----+-----+
| Smartphones |   1 |   4 |
| Android     |   2 |   3 |
+-------------+-----+-----+

We try to add a sub-element Xiaomi to Android again:

LOCK TABLE categories WRITE;
SELECT @root_left := lft FROM categories WHERE title = 'Android';
UPDATE categories SET rgt = rgt + 2 WHERE rgt > @root_left;
UPDATE categories SET lft = lft + 2 WHERE lft > @root_left;
INSERT INTO categories (title, lft, rgt) VALUES('小米', @root_left + 1, @root_left + 2);
UNLOCK TABLES;
SELECT `title`, `lft`, `rgt` FROM `categories`;
+-------------+-----+-----+
| title       | lft | rgt |
+-------------+-----+-----+
| Smartphones |   1 |   6 |
| Android     |   2 |   5 |
| 小米        |   3 |   4 |
+-------------+-----+-----+

At this time, we try to add a sub-element iOS to Smartphones. We have already added it in front An Android element, so here we need to adjust the stored procedure and insert iOS to the right of Android

LOCK TABLE categories WRITE;
SELECT @next_right := rgt FROM categories WHERE title = 'Android';
UPDATE categories SET rgt = rgt + 2 WHERE rgt > @next_right;
UPDATE categories SET lft = lft + 2 WHERE lft > @next_right;
INSERT INTO categories(title, lft, rgt) VALUES('iOS', @next_right + 1, @next_right + 2);
UNLOCK TABLES;
SELECT `title`, `lft`, `rgt` FROM `categories`;
+-------------+-----+-----+
| title       | lft | rgt |
+-------------+-----+-----+
| Smartphones |   1 |   8 |
| Android     |   2 |   5 |
| 小米        |   3 |   4 |
| iOS         |   6 |   7 |
+-------------+-----+-----+

Delete

When deleting a node, it can actually be seen as It is the inverse process of adding new nodes. We introduce a width to measure the width of the node, which is expressed as: rgt - lft 1 So we can write the stored procedure like this:

LOCK TABLE categories WRITE;
SELECT @delete_left := lft, @delete_right := rgt, @delete_width := rgt - lft + 1
FROM categories WHERE title = 'Android';
DELETE FROM categories WHERE lft BETWEEN @delete_left AND @delete_right;
UPDATE categories SET rgt = rgt - @delete_width WHERE rgt > @delete_right;
UPDATE categories SET lft = lft - @delete_width WHERE lft > @delete_right;
UNLOCK TABLES;
SELECT `title`, `lft`, `rgt` FROM `categories`;
+-------------+-----+-----+
| title       | lft | rgt |
+-------------+-----+-----+
| Smartphones |   1 |   4 |
| iOS         |   2 |   3 |
+-------------+-----+-----+

Update

Moving nodes is a relatively complicated process. For example, in the figure below, macOS should be classified under the Unix category.

To realize the movement of nodes, three steps are required:

1. Remove the node to be moved

2. Rearrange lft and rgt parameters

3. Move the node to the specified position

LOCK TABLE categories WRITE;
-- 将要移动的节点摘出来，并且重新边篇 lft 和 rgt
SELECT @move_left := lft , @move_right := rgt, @move_width := rgt - lft + 1
FROM categories WHERE title = 'macOS';
UPDATE categories SET rgt = -rgt WHERE lft BETWEEN @move_left AND @move_right;
UPDATE categories SET lft = -lft WHERE lft BETWEEN @move_left AND @move_right;
UPDATE categories SET rgt = rgt - @move_width WHERE rgt > @move_right;
UPDATE categories SET lft = lft - @move_width WHERE lft > @move_right;
-- 将节点放到 Unix 节点里
SELECT @root_left := lft FROM categories WHERE title = 'Unix';
UPDATE categories SET rgt = rgt + @move_width WHERE rgt > @root_left;
UPDATE categories SET lft = lft + @move_width WHERE lft > @root_left;
-- 
UPDATE categories SET lft = @root_left + 1 WHERE lft BETWEEN -@move_right AND -@move_left;
UPDATE categories SET rgt = @root_left + 2 WHERE rgt BETWEEN -@move_right AND -@move_left;
UNLOCK TABLES;

Summary

In fact, the data model of nested collections in SQL has been proposed for a long time Now, there are many packages that have implemented this function, such as laravel-nestedset or django-mptt

For production use, there is definitely no such simple table structure design, or even other optimizations, such as a called It is a closed table data model, which should be introduced to everyone in this series of articles.

The above is the detailed content of Tree data structure storage method (CUD). For more information, please follow other related articles on the PHP Chinese website!