在数据库中存储一棵树，实现无限级分类

哈喽！今天心血来潮给大家带来了《在数据库中存储一棵树，实现无限级分类》，想必大家应该对数据库都不陌生吧，那么阅读本文就都不会很困难，以下内容主要涉及到MySQL、Java、mybatis，若是你正在学习数据库，千万别错过这篇文章~希望能帮助到你！

原文发表于我的博客： https://blog.kaciras.com/article/6/store-tree-in-database

在一些系统中，对内容进行分类是必需的功能。比如电商就需要对商品做分类处理，以便于客户搜索；论坛也会分为很多板块；门户网站、也得对网站的内容做各种分类。

分类对于一个内容展示系统来说是不可缺少的，本博客也需要这么一个功能。众所周知，分类往往具有从属关系，比如铅笔盒钢笔属于笔，笔又是文具的一种，当然钢笔还可以按品牌来细分，每个品牌下面还有各种系列...

这个例子中从属关系具有5层，从上到下依次是：文具-笔-钢笔-XX牌-A系列，但实际中分类的层数却是无法估计的，比如生物中的界门纲目科属种有7级。显然对分类的级数做限制是不合理的，一个良好的分类系统，其应当能实现无限级分类。

在写自己的博客网站时，刚好需要这么一个功能。

完整的代码以及动态演示见 https://github.com/Kaciras/ClosureTable

1.需求分析

首先分析一下分类之间的关系是怎样的，很明显，一个分类下面有好多个下级分类，比如笔下面有铅笔和钢笔；那么反过来，一个下级分类能够属于几个上级分类呢？这其实并不确定，取决于如何对类型的划分。比如有办公用品和家具，那么办公桌可以同时属于这两者，不过这会带来一些问题，比如：我要显示从顶级分类到它之间的所有分类，那么这种情况下就很难决定办公用品和家具显示哪一个，并且如果是多对一，实现上将更加复杂，所以这里还是限定每个分类仅有一个上级分类。

这样一来，分类的关系可以表述为一父多子的继承关系，正好对应数据结构中的树，那么问题就转化成了如何在数据库中存储一棵树，并且对分类所需要的操作有较好的支持。

对于本博客来说，分类至少需要以下操作：

1. 对单个分类的增删改查。
2. 查询一个分类的直属下级和所有下级，在现实某一分类下所有文章时需要使用。
3. 查询出由顶级分类到文章所在分类之间的所有分类，并且是有序的。
4. 查询分类是哪一级的，比如顶级分类是1，顶级分类的直属下级是2，再往下依次递增。
5. 移动一个分类，换句话说就是把一个子树（或者仅单个节点）移动到另外的节点下面，这个在分类结构不合理，需要修改时使用。

在性能的衡量上，这些操作并不是平等的。查询操作使用的更加频繁，毕竟分类不会没事就改着玩，性能考虑要以查询操作优先，特别是2和3分别用于搜索文章和在文章简介中显示其分类，所以是重中之重。

另外，每个分类除了继承关系外，还有名字，简介等属性，也需要存储在数据库中。每个分类都有一个id，由数据库自动生成（自增主键）。

无限级多分类多存在于企业应用中，比如电商、博客平台等，这些应用里一般都有缓存机制，对于分类这种不频繁修改的数据，即使在底层数据库中存在缓慢的操作，只要上层缓存能够命中，一样有很快的响应速度。但是对于抽象的需求：在关系数据库中存储一棵树，并不仅存在于有缓存的应用中，所以设计一个高效的存储方案，仍然有其意义。

下面就以这个卖文具的电商的场景为例，针对这6条需求，设计一个数据库存储方案（对过程没兴趣可以直接转到第4节）。

2.一些常见设计方案的不足

2.1 直接记录父分类的引用

在许多编程语言中，继承关系都是一个类仅继承于一个父类，添加这种继承关系仅需要声明一下父类即可，比如JAVA中extends xxx。根据这种思想，我们仅需要在每个分类上添加上直属上级的id，即可存储它们之间的继承关系。

表中

SELECT id,name FROM pathlist WHERE path LIKE '1,%'

一句话搞定，

SELECT id,name FROM pathlist WHERE path LIKE '%2'

而找出所有上级分类这个需求，直接查出

SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance=1

查询所有子节点：

SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance>0

查询某个上级节点的子节点，换句话说就是查询具有指定上级节点的节点，也就是

SELECT ancestor FROM CategoryTree WHERE descendant=10 ORDER BY distance DESC

查询id为10的节点（含）到id为3的节点（不含）之间的所有节点，按照层级由小到大排序

SELECT ancestor FROM CategoryTree WHERE descendant=10 AND 
distance

查询路径，只需要知道

SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=0

查询id为5的节点是id为10的节点往下第几级

SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=10

查询层级（深度）非常简单，因为

SELECT descendant FROM CategoryTree WHERE ancestor=0 AND distance=3

这个就不详细说了，非常简单。

4.5 插入

插入和移动就不是那么方便了，当一个节点插入到某个父节点下方时，它将具有与父节点相似的路径，然后再加上一个自身连接即可。

所以插入操作需要两条语句，第一条复制父节点的所有记录，并把这些记录的

INSERT INTO CategoryTree(ancestor,descendant,distance) (SELECT ancestor,10,distance+1 FROM CategoryTree WHERE descendant=5)

然后就是加入自身连接的记录。

INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(10,10,0)

4.6 移动

节点的移动没有很好的解决方法，因为新位置所在的深度、路径都可能不一样，这就导致移动操作不是仅靠UPDATE语句能完成的，这里选择删除+插入实现移动。

另外，在有子树的情况下，上级节点的移动还将导致下级节点的路径改变，所以移动上级节点之后还需要修复下级节点的记录，这就需要递归所有下级节点。

删除id=5节点的所有记录

DELETE FROM CategoryTree WHERE descendant=5

然后配合上面一节的插入操作实现移动。具体的实现直接上代码吧。

ClosureTableCategoryStore.java是主要的逻辑，这里只展示部分代码

    /**
     * 将一个分类移动到目标分类下面（成为其子分类）。被移动分类的子类将自动上浮（成为指定分类
     * 父类的子分类），即使目标是指定分类原本的父类。
     * 

     * 例如下图(省略顶级分类)：
     *       1                                     1
     *       |                                   / | \
     *       2                                  3  4  5
     *     / | \             move(2,7)               / \
     *    3  4  5         --------------->          6   7
     *         / \                                 /  / | \
     *       6    7                               8  9  10 2
     *      /    /  \
     *     8    9    10
     *
     * @param id 被移动分类的id
     * @param target 目标分类的id
     * @throws IllegalArgumentException 如果id或target所表示的分类不存在、或id==target
     */
    public void move(int id, int target) {
        if(id == target) {
            throw new IllegalArgumentException("不能移动到自己下面");
        }
        moveSubTree(id, categoryMapper.selectAncestor(id, 1));
        moveNode(id, target);
    }

    /**
     * 将一个分类移动到目标分类下面（成为其子分类），被移动分类的子分类也会随着移动。
     * 如果目标分类是被移动分类的子类，则先将目标分类（连带子类）移动到被移动分类原来的
     * 的位置，再移动需要被移动的分类。
     * 

     * 例如下图(省略顶级分类)：
     *       1                                     1
     *       |                                     |
     *       2                                     7
     *     / | \           moveTree(2,7)         / | \
     *    3  4  5         --------------->      9  10  2
     *         / \                                   / | \
     *       6    7                                 3  4  5
     *      /    /  \                                     |
     *     8    9    10                                   6
     *                                                    |
     *                                                    8
     *
     * @param id 被移动分类的id
     * @param target 目标分类的id
     * @throws IllegalArgumentException 如果id或target所表示的分类不存在、或id==target
     */
    public void moveTree(int id, int target) {
        /* 移动分移到自己子树下和无关节点下两种情况 */
        Integer distance = categoryMapper.selectDistance(id, target);
        if (distance == null) {
            // 移动到父节点或其他无关系节点，不需要做额外动作
        } else if (distance == 0) {
            throw new IllegalArgumentException("不能移动到自己下面");
        } else {
            // 如果移动的目标是其子类，需要先把子类移动到本类的位置
            int parent = categoryMapper.selectAncestor(id, 1);
            moveNode(target, parent);
            moveSubTree(target, target);
        }

        moveNode(id, target);
        moveSubTree(id, id);
    }

    /**
     * 将指定节点移动到另某节点下面，该方法不修改子节点的相关记录，
     * 为了保证数据的完整性，需要与moveSubTree()方法配合使用。
     *
     * @param id 指定节点id
     * @param parent 某节点id
     */
    private void moveNode(int id, int parent) {
        categoryMapper.deletePath(id);
        categoryMapper.insertPath(id, parent);
        categoryMapper.insertNode(id);
    }

    /**
     * 将指定节点的所有子树移动到某节点下
     * 如果两个参数相同，则相当于重建子树，用于父节点移动后更新路径
     *
     * @param id     指定节点id
     * @param parent 某节点id
     */
    private void moveSubTree(int id, int parent) {
        int[] subs = categoryMapper.selectSubId(id);
        for (int sub : subs) {
            moveNode(sub, parent);
            moveSubTree(sub, sub);
        }
    }

其中的categoryMapper 是Mybatis的Mapper，这里只展示部分代码

    /**
     * 查询某个节点的第N级父节点。如果id指定的节点不存在、操作错误或是数据库被外部修改，
     * 则可能查询不到父节点，此时返回null。
     *
     * @param id 节点id
     * @param n 祖先距离（0表示自己，1表示直属父节点）
     * @return 父节点id，如果不存在则返回null
     */
    @Select("SELECT ancestor FROM CategoryTree WHERE descendant=#{id} AND distance=#{n}")
    Integer selectAncestor(@Param("id") int id, @Param("n") int n);

    /**
     * 复制父节点的路径结构,并修改descendant和distance
     *
     * @param id 节点id
     * @param parent 父节点id
     */
    @Insert("INSERT INTO CategoryTree(ancestor,descendant,distance) " +
            "(SELECT ancestor,#{id},distance+1 FROM CategoryTree WHERE descendant=#{parent})")
    void insertPath(@Param("id") int id, @Param("parent") int parent);

    /**
     * 在关系表中插入对自身的连接
     *
     * @param id 节点id
     */
    @Insert("INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(#{id},#{id},0)")
    void insertNode(int id);

    /**
     * 从树中删除某节点的路径。注意指定的节点可能存在子树，而子树的节点在该节点之上的路径并没有改变，
     * 所以使用该方法后还必须手动修改子节点的路径以确保树的正确性
     *
     * @param id 节点id
     */
    @Delete("DELETE FROM CategoryTree WHERE descendant=#{id}")
    void deletePath(int id);

5.结语

在分析推论后，终于找到了一种既有查询简单、效率高等优点，也符合数据库设计范式，而且是真正的无限级分类的设计。本方案的写入操作虽然需要递归，但相比于前序遍历树效率仍高出许多，并且在本博客系统中分类不会频繁修改。可见对于在关系数据库中存储一棵树的需求，ClosureTable是一种比较完美的解决方案。

今天关于《在数据库中存储一棵树，实现无限级分类》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！