数据库设计-请教无限级树存储数据表结构设计？

Question

一般会这么设计树的表结构id name parentid，但如果是无限级的大树，这种设计方法性能上就很差，请教还有什么别的设计方式。

Answer 1

左右值是一种非常不直观的方法。 毛遂自荐一种更简单的无限深度树方案：https://my.oschina.net/drinkjava2/blog/828781 或 https://github.com/drinkjava2/Multiple-Columns-Tree

其特点是只需要利用行号(已排序)和深度两个额外字段(加上尾部的结束标记)，即可以高效地实现SQL子树、父子节点的查询/删除/插入操作，缺点是节点的移动操作不太方便，适用于只增减，不经常移动节点的场合。

Answer 2

想了下，没有想到太完美的做法，但是想到几个能够解决适应特定场合的做法：

如果需要一次性展示所有节点，那我可以假定这棵树的规模并不大，因为数据量足够大的情况下，很少会有这种需求，所以字段有id,name,parentid足够，在编程时一次性查出所有节点，然后在内存中建立树结构。
如果数据量非常大，那我们可能更加趋向于采用通过用户点击来逐渐展开的方式，这种情况下有id,name,parentid也足够了，因为通过parentid即可查出一个节点的所有子节点。

如果有需求是一次性展示一个节点下的所有子孙节点，那么同样也可以假定这棵树规模不大，我们可以增加一个varchar类型的ancestors字段，并将该字段设为索引，用于存储从树顶点到该节点的路径，格式为"1,5,6,8"，在查询时我们可以先查出父节点的ancestors，然后和父节点的id拼出所有子孙节点的ancestors前缀，最后用like "[prefix]%"查询即可。因为varchar类型的长度限制，所以这棵树不能说是无限级的，但是可以在层次不深的情况下解决问题。

最后一种就是解决数据量很大，层次很深，但需要根据某个节点展开指定层次n的子孙节点的情况，这个时候我们可以参考情况3， 增加ancestors字段，但是ancestors字段不是记录从顶点到该节点的访问路径，而是记录该节点之前n + m (m >= 0)层祖父节点到该节点的访问路径，假设n=3，我们的参考节点的id为4, ancestors为"1,2,3"，然后在程序里依次用 = "2,3,4"，like "3,4,%", like "4,%"来查询并union出结果即可，这个设计的问题就是当m < 0时，该设计失效。

在更新维护方面，这几种方案都不困难，方案1,2只需要更改parentid，3的话除了更新parentid，还要取一下新的父节点的ancestors,最后和parentid拼接变成该节点的ancestors,4比3稍微多做点字符串处理即可

Answer 3

"id name parentid"的设计，慢在建立树时,每次得到当前节点的孩子节点都要去DB中查询:

"select * from xxx where parentid=curID"

性能损失在磁盘IO，虽然DB会缓存部分数据到内存，但不一定就会缓存"parentid=curID"的节点(当前节点的孩子)。

我有一个方法是: 增加字段"节点所在树的层次编号"、"节点在当前层的次序"。这样每次从数据库取出一些列节点，甚至全部取出。语句如下:

"select * from xxx where 层次编号>=yyyy and 层次编号<zzzzz"

然后从内存中按"parentid"、"层次"、"次序"依次建立树。如果我去掉了parentid，这样无法确定是谁的孩子。比如：

 A   B
 ^   |
D E  F
| ^  ^
GH IK L

若只查出第二层和第三层，无法确定G是D的子。加上parentid就可以了确定了。

也可以参考:
采用左右值编码来存储无限分级树形结构的数据库表设计

Answer 4

大概说下我的想法：

1.考虑到的是无限级的大树数据量可能相当大，所以先垂直分表，顶级节点一个表（A），二级节点一个表(B)，三级节点一个表(C)，从 4 - n 都用一个表存储(D)。个人感觉 即使是 无限级，三级以后的节点数量可能相当要少。可以根据实际情况划分。
A表字段 大概 就是 id , name
B,C表字段必须有 id,name,pid
D表与B,C表相同，但是要多一个字段来存放 节点是第几级

2.程序设计上，首先显示查询顶级节点（最好利于cache），其余的节点用户点击时在查询