• 技术文章 >后端开发 >php教程

    树状数据结构存储方式(CUD 篇)

    藏色散人藏色散人2019-09-10 11:31:16转载273
    前文简单介绍了嵌套集合的数据模型,以及查询的方法,传送门: 树状数据结构存储方式 (查询篇)

    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 分类下。

    fc14dd8f813809ac120a70439c95871.png

    要实现节点的移动,需要三步:

    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 篇)的详细内容,更多请关注php中文网其它相关文章!

    phpstudy集成环境下载
    本文转载于:learnku,如有侵犯,请联系a@php.cn删除
    专题推荐:数据结构
    上一篇:在 PHP 中格式化并高亮 SQL 语句 下一篇:PHP 不得不提的 session 与 cookie

    相关文章推荐

    • navicat怎么导出数据结构• 程序员,你应该知道的数据结构之栈• 什么是数据结构Hash表(哈希表)?又有哪些具体操作呢?• 树状数据结构存储方式(查询篇)

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网