树状结构存储与读取之Modified Preorder Tree

前言

一直以来存储树状结构都采用经典的结构<id,pid>的组合,即每一个节点持有其父节点的ID,并由此构成完整的树状结构。但是这样的结构在遇到大量的查询时会成为严重的性能瓶颈,因为它涉及了对数据库的递归查询。因此我查找了一下网上的各种层次结构的存储方式并决定对其分别实现。本文将通过MySQL+MyBatis+SpringBoot实现先序树存储。 阅读本文之前需要了解:

  • Spring Boot
  • MyBatis
  • MySQL CRUD & Procedure

本文的源码可以在GitHUB上查看。欢迎大家给出意见。

我们需要什么操作

在进入正文之前,我们需要从底层的具体实现抽离开来,从业务的角度来分析我们究竟需要对一棵树进行什么样的操作。这里我们将以分类管理作为具体场景。写过库存管理系统的盆友们都知道,我们需要用某种方式对各种商品的分类按照层次结构进行存储。比如我们有电子产品大类,底下还包括数码产品,家电等等各种小类,而在各个小类之下我们也还有多种更加具体的分类。这些分类在用户界面往往以直观的树状结构展示如下:

-电子产品
  - 数码产品
    - 手机类
    - 相机类
    - 电脑类
  - 家电

因此在业务层的角度来说我们需要以下操作:

public interface TreeService {

    /**
     * 获得rootId节点下的所有子节点
     * @param rootId
     * @return
     */
    Category getTree(int rootId);

    /**
     * 获得所有根节点
     * @return
     */
    List<Category> getRoots();


    /**
     * 添加一个分类
     * @param nodeName
     * @param parentId
     * @return
     */
    int addCategory(String nodeName, int parentId);

    /**
     * 删除一个分类
     * @param id
     * @return
     */
    void deleteCategory(int id);

    /**
     * 添加一个分类列表作为一个全新的分类
     * @param category
     * @return
     */
    int addCategoryList(Category category);
}

而业务层所看到的每一个分类的节点如下:

public class Category {
    
    private int id;
    private String name;
    private List<Category> subCategories;

    public Category(int id, String name){
        this(name);
        this.id = id;
    }

    public Category(String name){
        this.name = name;
        subCategories = new ArrayList<Category>();
    }
    public void addSubCategory(Category subCategory){
        subCategories.add(subCategory);
    }

    public boolean isLeaf(){
        return subCategories==null || subCategories.size() == 0;
    }
}

什么是Modified Preorder Tree

这篇文章当时给了我非常大的帮助,在阅读本文之前强烈建议先阅读这篇文章,来了解一下Modified Preorder Tree究竟是什么样的一个数据结构。在有了一个基础的认识之后我们将进一步利用SQL和Spring的事务来完成各项操作,从而实现之前列出的各项操作。

接下来了解一下Modified Proorder Tree的数据结构。

我们可以通过如下的建表语句在MySQL中新建一个Modified Preorder Tree的节点的表:

#建表语句
CREATE TABLE nested_category (
  category_id INT AUTO_INCREMENT PRIMARY KEY,
  name VARCHAR(20) NOT NULL,
  lft INT NOT NULL,
  rgt INT NOT NULL
);

并且先默认的插入一些数据:

INSERT INTO nested_category VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
  (4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
  (9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);

这里的数据就是之前那张图的层次结构。我们将在这个直观的层次结构的基础上进行存储和读取。 当然了,与之对应的JAVA中的类为:

import lombok.Data;
@Data
public class CategoryNode {

    private int id;
    private String name;
    private int lft;
    private int rgt;

    public boolean isLeaf(){
        return lft + 1 == rgt;
    }
}

本项目中很多地方的采用了lombok开源插件来简化getters和setters的书写。可以稍微了解一下lombok,非常方便。

一棵树

我们先从存取一棵树入手,来看看究竟如何实现节点的增删改查,以及插入一整棵树。下面我将分别列出相应操作的SQL语句以及对应的JAVA代码。

获得当前节点为根节点构成的树

Service中的接口为Category getTree(int rootId) 我们将用一条语句获取该节点所有的子节点(包括该节点本身),再在service层进行重组构成一棵树。相对于之前通过递归访问数据库,这样的方式明显效率更高。

    SELECT c1.* FROM nested_category c1, nested_category c2
        WHERE c1.lft >= c2.lft
              AND c2.rgt >= c1.rgt
              AND c2.category_id = #{id}
        ORDER BY c1.lft ASC

在逻辑层重组:

    public Category getTree(int rootId) {
        List<CategoryNode> categoryNodes = mapper.getSubCategoryNodesIncludingSelf(rootId);
        if (categoryNodes==null || categoryNodes.size() ==0) return null;
        CategoryNode root = categoryNodes.remove(0);
        return getTree(root, categoryNodes);
    }

    private Category getTree(CategoryNode parentCategory, List<CategoryNode> nodes){
        Category category = new Category(parentCategory.getId(), parentCategory.getName());
        if (!parentCategory.isLeaf()){
            while (nodes.size() > 0){
                CategoryNode tmpNode = nodes.get(0);
                if (tmpNode.getLft() > parentCategory.getRgt()) break;
                nodes.remove(0);
                category.addSubCategory(getTree(tmpNode, nodes));
            }
        }
        return category;
    }

添加一个分类

这里的添加操作是指在父节点之下添加一个新的分类。它并不影响原来的其他子节点。这里我们采用MySQL的过程存储加上Service层的事务管理来实现。

#插入节点-只能作为当前节点的一个新节点
CREATE PROCEDURE addCategory(
  IN categoryName VARCHAR(255),
  IN parentId INT,
  OUT categoryID INT
)
BEGIN
  SELECT @right := rgt FROM nested_category c WHERE c.category_id = parentId;
  UPDATE nested_category SET rgt = rgt + 2 WHERE rgt >= @right;
  UPDATE nested_category SET lft = lft + 2 WHERE lft >= @right;
  INSERT INTO nested_category(name, lft, rgt) VALUES(categoryName, @right, @right+1);
  SELECT LAST_INSERT_ID() INTO categoryID;
END;

CALL addCategory('GAME',1, @categoryId);
SELECT @categoryId;

这里可以使用MyBatis直接调用存储过程并获得返回结果,但是这里并不是本文的重点,所以不多赘述,可以直接前往Github查看。 Service层代码:

    @Transactional
    @Override
    public int addCategory(String nodeName, int parentId) {
        return mapper.addCategoryTo(nodeName, parentId);
    }

删除一个分类

删除一个分类意味着我们需要所有在该分类lft和rgt值之内的节点全部删除,同时需要更新其所有的父节点。

#删除节点
CREATE PROCEDURE delCategory(
  IN categoryID INT
)
BEGIN
  SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
  FROM nested_category
  WHERE category_id = categoryID;

  DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

  UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
  UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
END;

CALL delCategory(1);

这里同样需要过程管理加上事务的支持:

    @Override
    @Transactional
    public void deleteCategory(int id) {
        mapper.deleteCategory(id);
    }

多棵树

然而,我们的数据库往往并不会只有一个分类,分类之下往往会有多个独立的根节点,比如之前的电器类,还有家具类,书籍类。我们如何在Modified Preorder Tree结构下的分类管理中管理多棵树呢? 一般来说有两种思路:

  1. 默认所有的树都有一个隐藏的根节点,在此根节点的基础上,每个我们所知道的真实根节点为其直接子节点。缺点在于一棵树结构的变动将必然会影响所有节点
  2. 为每棵树冗余一定的空间,假设为1024,那么每棵树的根节点的lft值为1024的倍数。每次插入一棵新的树,我们将从下一个最小的1024的倍数作为lft值构建整棵树。缺点在于如果树的大小超过了1024,那么需要对整棵树进行重新转储。而且如果树的大小不均匀,那么将会产生很多的空余值没有被使用。
  3. 每个节点冗余一个字段,引入根节点的ID,这样的话所有的lft都可以从0开始写起并且树与树之前不会相互干扰。缺点:冗余字段,插入树是需要先获取根节点的ID,再传递给所有的子节点

这里我采用了第一种实现,后面会陆续更新第二和第三种。 可以看到,之前的实现在该场景下全部可以完美适用。

获得所有的根节点

如果一个节点不是根节点,那么一定存在一个节点,其lft值小于该节点的lft值,rgt值大于该节点的rgt值。

    SELECT * FROM nested_category c1
        WHERE c1.category_id
        NOT IN (
        SELECT DISTINCT c2.category_id
        FROM nested_category c2,
        nested_category c3
        WHERE c2.lft > c3.lft AND c3.rgt > c2.rgt)

当然了,service层要求传递完整结构的树节点,因此我们可以复用之前的构造一棵树的代码:

    @Override
    public List<Category> getRoots() {
        List<CategoryNode> roots = mapper.getRoots();
        List<Category> result = new ArrayList<Category>();
        for (CategoryNode n : roots){
            Category root = this.getTree(n.getId());
            result.add(root);
        }
        return result;
    }

添加一棵新的树

添加一棵新的树意味着需要获取当前lft的起始值,并按照中序遍历递归的为每个节点赋予lft和rgt值。然后将其一次性插入数据库中。这里直接饮用了mybatis代码。

    <select id="getMaxRightValue" resultType="INT">
        SELECT MAX(rgt) FROM nested_category;
    </select>
    
    <insert id="addCategories" parameterType="List" >
        INSERT INTO nested_category(name, lft, rgt) VALUES
        <foreach collection="list" item="element" index="index" open="(" separator="),("  close=")" >
            #{element.name}, #{element.lft}, #{element.rgt}
        </foreach>
    </insert>
    /**
     * 这里都不考虑异常情况
     * @param category
     * @return
     */
    @Override
    public int addCategoryList(Category category) {
        int lftValue = mapper.getMaxRightValue() + 1;
        List<CategoryNode> nodes = new ArrayList<CategoryNode>();
        CategoryNode root = labelCategory(category, lftValue, nodes);
        mapper.addCategories(nodes);
        return root.getId();
    }

    /**
     * 传入lftValue并设置各个node的左右值
     * @param category
     * @param lftValue
     * @return rgtValue
     */
    private CategoryNode labelCategory(Category category, int lftValue, List<CategoryNode> nodes){
        CategoryNode categoryNode = new CategoryNode();
        nodes.add(categoryNode);
        categoryNode.setName(category.getName());
        categoryNode.setLft(lftValue);
        int rgtValue = lftValue + 1;
        if (category.isLeaf()){
            categoryNode.setRgt(rgtValue);
        }else{
            for (Category subCategory : category.getSubCategories()){
                rgtValue = labelCategory(subCategory, rgtValue, nodes).getRgt() + 1;
            }
            categoryNode.setRgt(rgtValue);
        }
        return categoryNode;
    }

总结

<id, pid>结构的层次存储往往对读取友好而对更新不友好,所以我们往往需要根据具体的业务场景来决定如何来实现层次结构的存储和读取。

参考文章

Managing Hierarchical Data in Mysql Hierarchical data database 树状结构的数据表如何存储

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨建荣的学习笔记

运维建设的方向和思路

今天和同事聊需求的时候,突然发现目前我们在做的一些系统,其实他感觉有些迷茫,主要就是一个建设的思路和方向这一块,我想了下,也确实,目前来看,其实系统的功能初期避...

26320
来自专栏天天

java写数据接口

44920
来自专栏Java帮帮-微信公众号-技术文章全总结

怎么才算一个合格的程序员?【大牛经验】

产品经理经常改需求这是程序员最头疼的事情,作为程序员应该也站在PM的角度思考,帮助PM分析出本质的需求,这也许可以减少需求的变更。当然,前提是得干一行爱一行,...

23420
来自专栏Coding迪斯尼

使用预先训练好的单词向量识别影评的正负能量

上一节我们讨论路单词向量化的算法原理。算法的实现需要有大量的数据,一般而言你要收集到单词量在四十亿左右的文本数据才能通过上一节的算法训练处精准的单词向量,问题在...

20030
来自专栏友弟技术工作室

区块链 价值互联网的基石

这是我很久之前看的一本书,对区块链的概念解释简单易懂,适合入门, 好久没有写区块链的开发,所以现在重拾起。这本书也推荐给想要入门的朋友。

22910
来自专栏领域驱动设计DDD实战进阶

微服务实战(六):落地微服务架构到直销系统(事件存储)

在CQRS架构中,一个比较重要的内容就是当命令处理器从命令队列中接收到相关的命令数据后,通过调用领域对象逻辑,然后将当前事件的对象数据持久化到事件存储中。主要的...

15320
来自专栏杨建荣的学习笔记

给二三线城市的技术爱好者的几点建议

最近有很多朋友问我一些学习上的想法,最开始我是本着高大上的思维来考虑的,但是经过了解发现有不少的朋友有此疑问,而且很多是来自于二三线城市。突然我意识到我...

17620
来自专栏UAI人工智能

使用 Ray 用 15 行 Python 代码实现一个参数服务器

参数服务器是很多机器学习应用的核心部分。其核心作用是存放机器学习模型的参数(如,神经网络的权重)和提供服务将参数传给客户端(客户端通常是处理数据和计算参数更新的...

53720
来自专栏阮一峰的网络日志

每周分享第 24 期

以前的 3D 打印,一般都使用塑料。今年,3D 金属打印机问世了,可以用金属打印零件,生成更轻、更坚固、更复杂的形状,而且成本更低、速度更快。这为复杂的金属模具...

17330
来自专栏Java成长之路

局域网中连接windows环境下的oracle数据库

将该TNS信息配置到同事本地的tnsnames.ora文件,使用pl/sql developer无法连接,报错TNS-12535: TNS操作超时1。

20010

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励