1w6 数据
如果从总公司开始 最多有 7 级
mybatis 自查询 /java 递归查数据库 大概 30s
java 全查 代码递归生成机构树 大概 10s
1
siroleaf 2019-11-26 10:05:49 +08:00
用个 json 缓存起来。每当机构更新时去更新缓存的相应树节点就好。 查询机构树直接用缓存的
|
2
12tall 2019-11-26 10:07:41 +08:00
感觉可以通过先行数据结构(例如哈希表)构造树,可能会好一些吧
因为我没试过,所以也不知道具体效率如何 而且机构树这种弄一个静态的应该比较合适吧,开始时查询一次,后面就修改时更新。 这个我试了,感觉还行~ |
3
learnshare 2019-11-26 10:12:44 +08:00
缓存是一种方式
另一种方式是分层级获取,比如刚开始只获取前两级,再根据父级查对应的子级(不过要考虑实际的使用场景) |
5
helloSpringBoot 2019-11-26 10:20:53 +08:00
这个能满足吗,我们项目在用: https://jgrapht.org/
|
6
joysir 2019-11-26 10:21:54 +08:00
如果是多层,数据库表结构应该用一颗树表示(左值、右值的形式),而不是纯用 parentId 来做关联。
|
7
tubimasky OP @learnshare #3 得提供所有下级 结果可以缓存 也就是总公司才这么慢 华东大区 3000 多条 java 大概是几百 ms
|
8
javapythongo 2019-11-26 10:44:12 +08:00
延迟加载?
|
9
tubimasky OP @helloSpringBoot #5 好像不太一样哈
|
10
rrfeng 2019-11-26 10:53:19 +08:00
我给你个方案,直接用目录式存储,比如 ETCD (逃
|
11
wysnylc 2019-11-26 10:55:22 +08:00
丢 redis 缓存
想要响应快就得数据有延迟 想要数据没延迟就要接受响应慢 同样的油量,你不能让一辆车跑得又快又远 |
12
luckyrayyy 2019-11-26 11:00:55 +08:00
插入的时候构建啊,不要每次读取的时候构建。这种数据应该是变动不太大的吧
|
13
wc951 2019-11-26 11:04:33 +08:00 via Android
用 ldap 存
|
14
x66 2019-11-26 11:25:57 +08:00
关键词:树形结构的数据库表 Schema 设计
|
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 |
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 是深度 |
17
blodside 2019-11-26 13:10:45 +08:00
16k 条数据怎么会要十秒的, 我想不通啊
|
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 秒。我觉得构造树的时间可以忽略不记。 |
19
tubimasky OP |
20
allenyang89 2019-11-26 14:43:04 +08:00 via iPhone
一个表存 id 节点树结构直接扔内存里也没多少,具体信息根据 id 再查
|
22
egen 2019-11-26 17:17:39 +08:00
时间长是因为数据库查询太多吧,调整数据库结构可解
|
23
aguesuka 2019-11-26 17:18:06 +08:00
@tubimasky 因为 node 保存了父节点,你可以把序列化的时候忽略父节点字段。比如 fast json,@JSONField(serialize = false )
|
24
stevenkang 2019-11-26 17:22:21 +08:00 via iPhone
1w+ 的数据级别完全可以靠程序来遍历,全部查出来缓存到内存中再递归
|
25
johnny23 2019-11-26 19:51:40 +08:00
多做一个字段存所有父子关系的 id 列表
|
26
wuzhizuiguo 2019-12-23 09:35:46 +08:00
|
27
aguesuka 2019-12-23 12:50:43 +08:00 via Android
@wuzhizuiguo 里面的代码可以自己改,parent 完全可以去掉,root 节点在我这里是没有父节点的 node,你可以改成一个 list,或者把 root id 当参数传进去。lambda stream 和泛型,理解原理很简单。
|
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 ); |
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 )
|
30
wuzhizuiguo 2019-12-24 09:47:25 +08:00
@aguesuka 谢谢.是的,我把 Node 类放到外面单独建了, 返回 id 为 2 的菜单 用它的 children 这个方法好.谢谢!
|