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

2018-04-10

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

SELECT ancestor FROM CategoryTree WHERE descendant=10 AND 
distance<(SELECT distance FROM CategoryTree WHERE descendant=10 AND ancestor=3) 
ORDER BY distance DESC

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

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

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

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)

DELETE FROM CategoryTree WHERE descendant=5

    /**
     * 将一个分类移动到目标分类下面（成为其子分类）。被移动分类的子类将自动上浮（成为指定分类
     * 父类的子分类），即使目标是指定分类原本的父类。
     * 例如下图(省略顶级分类)：
     *       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);
    }

    /**
     * 查询某个节点的第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);
     * 从树中删除某节点的路径。注意指定的节点可能存在子树，而子树的节点在该节点之上的路径并没有改变，

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

1.需求分析

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

2.1 直接记录父分类的引用

2.2 路径列表

2.3 前序遍历树

3.新方案的思考

4.基于ClosureTable的无限级分类存储

4.1 子节点查询

4.2 路径查询

4.3 查询节点所在的层级（深度）

4.4 查询某一层的所有节点

4.5 插入

4.6 移动