V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tubimasky
V2EX  ›  问与答

生成机构树 除了递归还有别的方法吗

  •  
  •   tubimasky · 2019-11-26 09:51:04 +08:00 · 3992 次点击
    这是一个创建于 1823 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1w6 数据

    如果从总公司开始 最多有 7 级

    mybatis 自查询 /java 递归查数据库 大概 30s

    java 全查 代码递归生成机构树 大概 10s

    第 1 条附言  ·  2019-11-26 10:33:00 +08:00
    得提供所有下级 结果集可以缓存
    也就是总公司才这么慢 华东大区 3000 多条
    java 500 ms 内
    30 条回复    2019-12-24 09:47:25 +08:00
    siroleaf
        1
    siroleaf  
       2019-11-26 10:05:49 +08:00
    用个 json 缓存起来。每当机构更新时去更新缓存的相应树节点就好。 查询机构树直接用缓存的
    12tall
        2
    12tall  
       2019-11-26 10:07:41 +08:00
    感觉可以通过先行数据结构(例如哈希表)构造树,可能会好一些吧
    因为我没试过,所以也不知道具体效率如何

    而且机构树这种弄一个静态的应该比较合适吧,开始时查询一次,后面就修改时更新。
    这个我试了,感觉还行~
    learnshare
        3
    learnshare  
       2019-11-26 10:12:44 +08:00
    缓存是一种方式
    另一种方式是分层级获取,比如刚开始只获取前两级,再根据父级查对应的子级(不过要考虑实际的使用场景)
    tubimasky
        4
    tubimasky  
    OP
       2019-11-26 10:14:47 +08:00
    @siroleaf #1 不太行 也可能是查某个分公司的下级
    helloSpringBoot
        5
    helloSpringBoot  
       2019-11-26 10:20:53 +08:00
    这个能满足吗,我们项目在用: https://jgrapht.org/
    joysir
        6
    joysir  
       2019-11-26 10:21:54 +08:00
    如果是多层,数据库表结构应该用一颗树表示(左值、右值的形式),而不是纯用 parentId 来做关联。
    tubimasky
        7
    tubimasky  
    OP
       2019-11-26 10:29:14 +08:00
    @learnshare #3 得提供所有下级 结果可以缓存 也就是总公司才这么慢 华东大区 3000 多条 java 大概是几百 ms
    javapythongo
        8
    javapythongo  
       2019-11-26 10:44:12 +08:00
    延迟加载?
    tubimasky
        9
    tubimasky  
    OP
       2019-11-26 10:50:14 +08:00
    @helloSpringBoot #5 好像不太一样哈
    rrfeng
        10
    rrfeng  
       2019-11-26 10:53:19 +08:00
    我给你个方案,直接用目录式存储,比如 ETCD (逃
    wysnylc
        11
    wysnylc  
       2019-11-26 10:55:22 +08:00
    丢 redis 缓存
    想要响应快就得数据有延迟
    想要数据没延迟就要接受响应慢
    同样的油量,你不能让一辆车跑得又快又远
    luckyrayyy
        12
    luckyrayyy  
       2019-11-26 11:00:55 +08:00
    插入的时候构建啊,不要每次读取的时候构建。这种数据应该是变动不太大的吧
    wc951
        13
    wc951  
       2019-11-26 11:04:33 +08:00 via Android
    用 ldap 存
    x66
        14
    x66  
       2019-11-26 11:25:57 +08:00
    关键词:树形结构的数据库表 Schema 设计
    cokolin
        15
    cokolin  
       2019-11-26 11:32:34 +08:00
    1. 缓存是一定可以的,我不相信公司机构会经常变化
    2. 如果要查数据,可以加一两个表字段表示上层结构,甚至可以直接用 id 也可以,思路如下:
    例如一个字段:level_index = 1020030040050060007
    其中 1 ~ 7 表示各个层级关系,然后你要找第四层级某个部门的所有数据可以查询:
    level_index > 1020030040000000000 and level_index < 1020030050000000000
    aguesuka
        16
    aguesuka  
       2019-11-26 12:38:49 +08:00
    缓存肯定要做,数据结构大概是 Node<E> {E data; Set<Node<E>> children; Node parent} 的结构;用 Hash 来构造,时间复杂度是 O(n),只要知道某个机构的 Node 就能找到它的子所有机构。为此你可以在建立一个 HashMap<ID, Node<E>> index;
    这样你前台传过来一个机构 id,返回所有子节点的代码大概就是:
    ID id;
    int deep ;
    //...
    Node<E> node = index.get(id);
    return traversing(node,deep); // traversing 是遍历所有子节点的方法,deep 是深度
    blodside
        17
    blodside  
       2019-11-26 13:10:45 +08:00
    16k 条数据怎么会要十秒的, 我想不通啊
    aguesuka
        18
    aguesuka  
       2019-11-26 13:12:35 +08:00   ❤️ 1
    ···
    public class TreeBuilderTest {
    private <E, ID> Node<E> buildTree(Collection<E> elements, Function<E, ID> getId, Function<E, ID> getParentId) {
    Map<ID, Node<E>> idNodeMap = elements.stream().collect(Collectors.toMap(getId, Node::new));
    Node<E> root = null;
    for (E element : elements) {
    ID parentId = getParentId.apply(element);
    ID selfId = getId.apply(element);
    Node<E> selfNode = idNodeMap.get(selfId);
    if (idNodeMap.containsKey(parentId)) {
    Node<E> parentNode = idNodeMap.get(parentId);

    parentNode.children.add(selfNode);
    selfNode.parent = parentNode;
    } else {
    if (root != null) {
    throw new IllegalArgumentException("root node more than one");
    }
    root = selfNode;
    }
    }
    Objects.requireNonNull(root, "there is not root node");
    return root;
    }

    @Test
    public void test() {
    Random random = new SecureRandom();
    List<TestData> resultFromSql = IntStream.range(0, 100_000)
    .mapToObj(i -> new TestData(i, random))
    .collect(Collectors.toList());
    long startTime = System.nanoTime();
    Node<TestData> testDataNode = buildTree(resultFromSql, e -> e.id, e -> e.parentId);
    System.out.println("cost = " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime));
    }

    private static class Node<E> {
    E data;
    Set<Node<E>> children;
    Node<E> parent;

    Node(E data) {
    this.data = data;
    children = new HashSet<>();
    }
    }

    private static class TestData {
    int id;
    int parentId;

    TestData(int id, Random r) {
    this.id = id;
    parentId = id == 0 ? -1 : r.nextInt(id);
    }
    }
    }
    ···
    抛砖引玉,十万条数据在我这里只要 0.1 秒。我觉得构造树的时间可以忽略不记。
    tubimasky
        19
    tubimasky  
    OP
       2019-11-26 14:39:07 +08:00
    @luckyrayyy #12 数据是来自其它系统的库


    @blodside #17 16k 我写的是递归 16k 次
    @aguesuka #18 感谢 我试试 能不能 套进去
    allenyang89
        20
    allenyang89  
       2019-11-26 14:43:04 +08:00 via iPhone
    一个表存 id 节点树结构直接扔内存里也没多少,具体信息根据 id 再查
    tubimasky
        21
    tubimasky  
    OP
       2019-11-26 16:59:18 +08:00
    @aguesuka #18 转成 json 无限递归了...
    egen
        22
    egen  
       2019-11-26 17:17:39 +08:00
    时间长是因为数据库查询太多吧,调整数据库结构可解
    aguesuka
        23
    aguesuka  
       2019-11-26 17:18:06 +08:00
    @tubimasky 因为 node 保存了父节点,你可以把序列化的时候忽略父节点字段。比如 fast json,@JSONField(serialize = false )
    stevenkang
        24
    stevenkang  
       2019-11-26 17:22:21 +08:00 via iPhone
    1w+ 的数据级别完全可以靠程序来遍历,全部查出来缓存到内存中再递归
    johnny23
        25
    johnny23  
       2019-11-26 19:51:40 +08:00
    多做一个字段存所有父子关系的 id 列表
    wuzhizuiguo
        26
    wuzhizuiguo  
       2019-12-23 09:35:46 +08:00
    @aguesuka 谢谢, 有效,可以直接生成分类数,不过直接返回 root 太长,每个 chidren 里的 parent 都会显示出来,用 @JSONField(serialize = false )返回可以去掉, 不过感觉不太美观(是个 json 字符串,), 如果没有最高的父节点时,会报 root node more than one. 还有答主的 buildTree 方法,感觉很强,第一次看到这种写法, 唉,要学的还有好多啊.
    aguesuka
        27
    aguesuka  
       2019-12-23 12:50:43 +08:00 via Android
    @wuzhizuiguo 里面的代码可以自己改,parent 完全可以去掉,root 节点在我这里是没有父节点的 node,你可以改成一个 list,或者把 root id 当参数传进去。lambda stream 和泛型,理解原理很简单。
    wuzhizuiguo
        28
    wuzhizuiguo  
       2019-12-23 18:46:52 +08:00
    @aguesuka 是的,可以改一点. 在你的基础上改了下,去掉了 parent. 传了个 parentId 和 ID 的判断相等的 Function. 对泛型类的比较该怎么实现不懂(怎么取参数,怎么判断大小) , 还有就是 Node::new 是什么意思, 调用 Node 的默认构造方法吗? 还是非默认的 Node(E data)?
    下面这个是自己改了老半天的, 可能还是有错误, 请路过的谨慎使用... (compare 是判断是否和 pid 的值相等)


    public static <E,ID> List<Node<E>> buildTree(Collection<E> elements, Function<E,ID> getID, Function<E,ID> getParentID,
    ID pid, Function<E,Boolean> compare){
    Map<ID,Node<E>> idNodeMap = elements.stream().collect(Collectors.toMap(getID,Node::new));
    //传进来的集合可能没有包含父类 /最顶级父类
    Node<E> root = null;
    //返回的列表
    List<Node<E>> nodes = new ArrayList<>();
    for (E element : elements){
    ID selfId = getID.apply(element);
    ID parentId = getParentID.apply(element);
    Node<E> selfNode = idNodeMap.get(selfId);
    //如果这个集合里 有元素有对应的父节点
    if (idNodeMap.containsKey(parentId)){
    Node<E> parentNode = idNodeMap.get(parentId);
    // selfNode.setParent(parentNode); //取消设置父节点,不然看起来很庞大
    parentNode.getChildren().add(selfNode);
    //如果设置了父节点 pid,而且该节点的父节点也是设置的值 pid
    if (pid!=null &&compare.apply(element) && !nodes.contains(selfNode)){
    nodes.add(selfNode);
    }
    }else {
    root = selfNode;
    //如果设置了父节点 pid,而且该节点的父节点也是设置的值 pid
    if (pid!=null &&compare.apply(element) && !nodes.contains(selfNode)){
    nodes.add(root);
    }

    }
    }
    return nodes;
    }


    public class Node<E> {
    E data;
    Set<Node<E>> children;
    Node<E> parent;

    public Node(E data) {
    this.data = data;
    children = new HashSet<>();
    }

    public E getData() {
    return data;
    }

    public void setData(E data) {
    this.data = data;
    }

    public Set<Node<E>> getChildren() {
    return children;
    }

    public void setChildren(Set<Node<E>> children) {
    this.children = children;
    }

    public Node<E> getParent() {
    return parent;
    }

    public void setParent(Node<E> parent) {
    this.parent = parent;
    }
    }

    具体调用
    List<MenuVO> menuVOList =... 从数据库查出来的结果列表
    // 去父节点 pid 为 2 的, 获取该菜单下所有的栏目,
    Collection<Node<MenuVO>> nodes = buildTree(menuVOList,e->e.getId(),e->e.getPid(),2,e->e.getPid().intValue() ==2 );
    aguesuka
        29
    aguesuka  
       2019-12-23 21:13:53 +08:00
    @wuzhizuiguo node 的 parent 字段是可以去掉的。内部类 Node 必须是 static 的,要不就单独建一个类。如果你想要 id 为 2 的菜单的所有子菜单,直接把 id 为 2 的菜单返回回来,它的 children 就是。一般情况比较可以用 Objects.equals。Function 可以用 Predicate 代替,::new 不好解释,你可以上网上搜搜。 如果还有别的问题可以加我微信。MTMzNzA4NDMyNjE= ( base64 )
    wuzhizuiguo
        30
    wuzhizuiguo  
       2019-12-24 09:47:25 +08:00
    @aguesuka 谢谢.是的,我把 Node 类放到外面单独建了, 返回 id 为 2 的菜单 用它的 children 这个方法好.谢谢!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3676 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 04:16 · PVG 12:16 · LAX 20:16 · JFK 23:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.