无涯

无所谓无 无所谓有

目录设计之—邻接表

发表于 更新于

前言

目录在日常开发中是一种非常常见的需求，今天我们来详细讨论下一种实现方案，以及查询思路。

设计思路

目录其实就是一种树形结构，子目录与父目录形成一种父子关系，所以很自然 的想到维护他们这种关系就能实现了。

数据库设计

1
2
3
4
5
6
create table tree_node
(
	id bigint not null comment '主键id'
		primary key,
	parent bigint null comment '父节点(root节点为0)'
)
  • parent存储父子关系
  • 这种设计很直观，也最容易理解，专业术语成为邻接表
  • 唯一的缺点是在做修改、删除的时候比较麻烦，建议在确定结构后不要再修改目录结构

树节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class TreeNode<T> {

    /**
     * 节点ID
     */
    private Long id;

    /**
     * 节点数据
     */
    private T date;

    /**
     * 节点父节点ID
     */
    private Long parent;

    /**
     * 孩子节点
     */
    private List<TreeNode<T>> child;

    public void addChild(TreeNode<T> node) {
        if (CollectionUtils.isEmpty(this.child)) {
            this.child = new ArrayList<>();
        }
        this.child.add(node);
    }

    // Get Set ...
}

常见需求

生成树

根据节点列表生成树

  • 给列表根据id建立索引
  • 遍历列表，将自己加入父节点的孩子列表， 形成父子关系
  • 建立一个ROOT节点作为根节点，将一级目录放在根节点下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 生成树
 *
 * @param nodes 所有节点
 * @return tree
 */
public static <T> TreeNode<T> tree(List<TreeNode<T>> nodes) {
    // 建立索引
    Map<Long, TreeNode<T>> map = nodes.stream().collect(Collectors.toMap(TreeNode::getId, item -> item));
    // ROOT 节点
    TreeNode<T> root = new TreeNode<>();
    for (TreeNode<T> node : nodes) {
        if (node.getParent() == null || node.getParent() == 0) {
            root.addChild(node);
        } else {
            Long parent = node.getParent();
            map.get(parent).addChild(node);
        }
    }
    return root;
}

获取树的某个节点

由于是目录设计，这里采用广度优先遍历，优先遍历上层目录

  • 使用队列实现的广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 获取节点 采用广度优先遍历
 *
 * @param id   节点id
 * @param tree 树
 * @return result
 */
public static <T> TreeNode<T> getNode(long id, TreeNode<T> tree) {
    Queue<TreeNode<T>> queue = new LinkedBlockingQueue<>();
    queue.add(tree);
    while (!queue.isEmpty()) {
        TreeNode<T> node = queue.poll();
        if (Objects.equals(node.getId(), id)) {
            return node;
        }
        if (!CollectionUtils.isEmpty(node.getChild())) {
            queue.addAll(node.getChild());
        }
    }
    return null;
}

获取所有节点

有时候需要获取某个节点下面的全部节点信息，例如在做搜索的时候就有这个需求

  • 这里采用深度优先遍历所有节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 深度优先遍历获取所有节点
 *
 * @param tree 树
 * @param list 节点列表
 */
public static <T> void getAllTreeNode(TreeNode<T> tree, List<TreeNode<T>> list) {
    list.add(tree);
    List<TreeNode<T>> child = tree.getChild();
    if (!CollectionUtils.isEmpty(child)) {
        for (TreeNode<T> node : child) {
            getAllTreeNode(node, list);
        }
    }
}