树状数据结构存储方式（CUD 篇）

Create

在嵌套集合模型中，每个数据其实就是一个节点 (node)，而每个节点占用 2 个位值，比如我们先新增一个 Smartphones 一级节点开始。

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

Smartphones 作为一个主节点 (root)，它的 lft 必定为 1，而 rgt 的值，会随着其集合内的子元素增加而增加。

现在，我们希望在 Smartphones 内，添加一个子元素 Android。借助 mysql 的存储过程。

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 |  ------------- ----- ----- 

我们再尝试往 Android 内添加一个子元素 小米：

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 |  ------------- ----- ----- 

这时候，我们再尝试往 Smartphones 内添加一个子元素 iOS，在前面，我们已经在里面添加了一个 Android 元素，所以这里要调整一下存储过程，将 iOS 插入到 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

删除节点时，其实可以看做是新增节点的逆过程，我们引入一个宽度，来衡量节点的宽段，其表示为： rgt - lft 1 所以我们可以这样写存储过程：

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

移动节点，是一个比较复杂的过程，例如下图，macOS 应该归类到 Unix 分类下。

要实现节点的移动，需要三步：

1、将要移动的节点摘出来

2、重新编排 lft 和 rgt 参数

3、将节点移动到指定位置

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;

总结

其实 SQL 中的嵌套集合的数据模型已经提出很久了，也有很多包已经实现了这个功能，比如 laravel-nestedset 或者 django-mptt

对于生产使用中，肯定是没有这么简单的表结构设计，或者甚至别的优化，比如一种称为闭合表的数据模型，这个应该会在本系列文章中介绍给大家。

以上就是树状数据结构存储方式（CUD 篇）的详细内容，更多请关注教程集其它相关文章！

您可能感兴趣的文章：
树状数据结构存储方式（CUD 篇）
数据结构-树和二叉树(Golang)
数据结构与算法–四叉树（javascript实现）
树状数据结构存储方式（查询篇）
数据结构中树与二叉树基础算法的比较
php与mysql实现的无限级分类
数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
json为什么像花儿一样红
golang key map 所有_golang系列——高级语法之map
golang sdk后端怎么用_Golang资深后端工程师需要了解的知识点