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

[tubimasky]

1w6 数据

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

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

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

得提供所有下级 结果集可以缓存
也就是总公司才这么慢 华东大区 3000 多条
java 500 ms 内

[siroleaf]

用个 json 缓存起来。每当机构更新时去更新缓存的相应树节点就好。 查询机构树直接用缓存的

[12tall]

感觉可以通过先行数据结构(例如哈希表)构造树，可能会好一些吧
因为我没试过，所以也不知道具体效率如何

而且机构树这种弄一个静态的应该比较合适吧，开始时查询一次，后面就修改时更新。
这个我试了，感觉还行~

[learnshare]

缓存是一种方式
另一种方式是分层级获取，比如刚开始只获取前两级，再根据父级查对应的子级（不过要考虑实际的使用场景）

[tubimasky]

@siroleaf #1 不太行 也可能是查某个分公司的下级

[helloSpringBoot]

这个能满足吗，我们项目在用： https://jgrapht.org/

[joysir]

如果是多层，数据库表结构应该用一颗树表示（左值、右值的形式），而不是纯用 parentId 来做关联。

[tubimasky]

@learnshare #3 得提供所有下级 结果可以缓存 也就是总公司才这么慢 华东大区 3000 多条 java 大概是几百 ms

[javapythongo]

延迟加载？

[tubimasky]

@helloSpringBoot #5 好像不太一样哈

[rrfeng]

我给你个方案，直接用目录式存储，比如 ETCD （逃

[wysnylc]

丢 redis 缓存
想要响应快就得数据有延迟
想要数据没延迟就要接受响应慢
同样的油量,你不能让一辆车跑得又快又远

[luckyrayyy]

插入的时候构建啊，不要每次读取的时候构建。这种数据应该是变动不太大的吧

[wc951]

用 ldap 存

[x66]

关键词：树形结构的数据库表 Schema 设计

[cokolin]

1. 缓存是一定可以的，我不相信公司机构会经常变化
2. 如果要查数据，可以加一两个表字段表示上层结构，甚至可以直接用 id 也可以，思路如下：
例如一个字段：level_index = 1020030040050060007
其中 1 ~ 7 表示各个层级关系，然后你要找第四层级某个部门的所有数据可以查询：
level_index > 1020030040000000000 and level_index < 1020030050000000000

[aguesuka]

缓存肯定要做，数据结构大概是 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]

16k 条数据怎么会要十秒的， 我想不通啊

[aguesuka]

···
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]

@luckyrayyy #12 数据是来自其它系统的库


@blodside #17 16k 我写的是递归 16k 次
@aguesuka #18 感谢 我试试 能不能 套进去

[allenyang89]

一个表存 id 节点树结构直接扔内存里也没多少，具体信息根据 id 再查

[tubimasky]

@aguesuka #18 转成 json 无限递归了...

[egen]

时间长是因为数据库查询太多吧，调整数据库结构可解

[aguesuka]

@tubimasky 因为 node 保存了父节点，你可以把序列化的时候忽略父节点字段。比如 fast json，@JSONField(serialize = false ）

[stevenkang]

1w+ 的数据级别完全可以靠程序来遍历，全部查出来缓存到内存中再递归

[johnny23]

多做一个字段存所有父子关系的 id 列表

[wuzhizuiguo]

@aguesuka 谢谢, 有效,可以直接生成分类数,不过直接返回 root 太长,每个 chidren 里的 parent 都会显示出来,用 @JSONField(serialize = false ）返回可以去掉, 不过感觉不太美观(是个 json 字符串,), 如果没有最高的父节点时,会报 root node more than one. 还有答主的 buildTree 方法,感觉很强,第一次看到这种写法, 唉,要学的还有好多啊.

[aguesuka]

@wuzhizuiguo 里面的代码可以自己改，parent 完全可以去掉，root 节点在我这里是没有父节点的 node，你可以改成一个 list，或者把 root id 当参数传进去。lambda stream 和泛型，理解原理很简单。

[wuzhizuiguo]

@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]

@wuzhizuiguo node 的 parent 字段是可以去掉的。内部类 Node 必须是 static 的，要不就单独建一个类。如果你想要 id 为 2 的菜单的所有子菜单，直接把 id 为 2 的菜单返回回来，它的 children 就是。一般情况比较可以用 Objects.equals。Function 可以用 Predicate 代替，::new 不好解释，你可以上网上搜搜。 如果还有别的问题可以加我微信。MTMzNzA4NDMyNjE= （ base64 ）

[wuzhizuiguo]

@aguesuka 谢谢.是的,我把 Node 类放到外面单独建了, 返回 id 为 2 的菜单 用它的 children 这个方法好.谢谢!