树形结构在java下数据库存取的最佳实践

Question

CSDN中关于树形结构的文章很多，看了之后仍然没有答案，由于应用系统中树形结构使用很多，希望找到一种最佳实践，在应用开发中全部采用这种模式。因此希望这是一种优雅而简洁的方式，开发人员容易理解和实现。
不同的需求，最佳实践也不同，因此先介绍一下条件吧：
1、用parentId关联方式设计数据库，树形数据库常见的设计思路有：A、基于parentid关联的、B、通过01，0101等长度不同的ID，可通过sort查询的方式、C、其它变种的，增加冗余字段使查询简单而维护复杂的方式，第二种方式下，树的调整很困难，比如改变某些节点的位置，而且位数限制了长度，第三种做法其维护太复杂，不利于广泛采用，因此认为在数据库设计中，基于parentid关联方式是最好的，也作为本题的条件。
2、能够实现返回任意节点的所有下级节点；
3、能够找到任意节点的所有上级节点
4、能够调整节点在树中的位置
5、使用java语言，.net下好象有现成的解决方案
6、数据库通用性，这个作为可选条件，能通用最好，不能通用无非多写几套代码树形数据库存取也有几种做法：
1、用存储过程实现存取，直接获得排好序的结果集，能够方便在java中转为树形，缺点是代码复杂，不同数据库无法通用
2、取出所有结果集在java中循环判断而建立树形结构，缺点是对大数据量的表无法采用，性能差
3、先取出第一层，然后在java中反复调用多次访问数据库，缺点是数据库连接过多
4、只取第一层，在页面上点击子节点时通过AJAX动态读取下层，缺点是仅能用于页面展现，不符合前面的条件：实现返回任意节点的所有下级节点我想最佳实践大概也是上述方式中一种吧，有更佳方式请大家告诉我，请大家评估一下，哪种方式是树形数据库存取的最佳实践？如果您是技术总监，您希望开发团队采用何处方式处理各种树形结构？

Answer 1

我是综合了上面俩种机制来做的，，
表中有 id，parentid，typid，，
在树的展现的时候通过，id和parentid，来做连接的，，
至于层次，排序，用typeid ，，typeid 的取值，
一层 A                B   C
二   AA，AB，
三   AAA，AAB，ABA，

Answer 2

可以说LZ描述的够详细了，分析的也很透彻
我用两种框架做过：
1.structs1 + ajax :
2.jsf + ajax
这两个框架的特点是一样的：
  a.基于parentid关联的
  b.只取第一层，在页面上点击子节点时通过AJAX动态读取下层
  c.没有实现返回任意节点的所有下级节点，也没有定位要说最佳实现方案是哪个，这个要基于涉及到的业务以及所实现的功能，其实LZ基本上已经提出来了：
1.如果是大数据量:一定要用异步的，其他的功能可以想方法弥补（我还未实现定位:)）
2.小数据量(临界点500个节点左右)：取出所有结果集在java中循环判断而建立树形结构，可定位，加一个字段即可我的观点就两点：大数据量，异步

Answer 3

B、通过01，0101等长度不同的ID，可通过sort查询的方式、
1、用存储过程实现存取，直接获得排好序的结果集，能够方便在java中转为树形，缺点是代码复杂，不同数据库无法通用 最近做的两个比较大的项目,都是采用的B方式
个人感觉遍历起来很方便的,而且开发起来很简单.不容易出错!这是最关键的.
至于其缺点,象楼主所说"代码复杂",楼主是说代码量大吗?个人感觉并不是很复杂,刚毕业的学生也可以很快上手开发.而且维护起来也很方便.
"直接获得排好序的结果集",我们使用的B方式无需要排序,在程序中判断一下就可以了,所以不用考虑数据库通用的问题所以我推荐楼主所说的B方式

Answer 4

11楼的意思是用长度不同的ID再结合存储过程实现吗？
B方式如果要修改树的排序或调整层级位置时，比较麻烦，比如把第三层中某个节点及子节点挪到第二层的某个位置，这样会有大量的节点ID都需要修改（通常不是ID，而是另一个用于排序的字段，ID实际上是不可以修改的），而且还要避免改错，其实是很不容易实现的，但parentID的方式，调整位置就比较容易

Answer 5

再说一遍,无需要在数据库中排序.顺序在定义ID的时候就已经排好了(ID值就代表着节点自身的位置),这些是代码中的工作.数据库中存放的是一些无序的ID号,节点名等信息
通过某些手段将它们持久化到数据库
至于更改节点位置,再方便不过了,直接在代码中修改就是了,而后持久化一遍就OK了!看看,无论是开发,或者是维护,都是多么的方便!将复杂的问题分散开,便于开发和维护,B方式自然成为我的首选了

Answer 6

我一般是用parentId，然后ID用层级方式保存，
比如
ID，ParentId，value
1,     0,     根节点
1.1，  1，   第一层1
1.1.1, 1.1,  第二层1
1.1.2, 1.1,  第二层2oracle中有现成的函数可以根据parentId直接查询出树形结构的

Answer 7

结点定义
class Node {
 public String viewName;//前台显示的值
 public int id;//数据库中id
 public int father;//此结点的父结点
 public List<Integer> childs = new ArrayList<Integer>();//所有儿子结点的id
}
树的定义，此树应为单例！
class Tree {
  private Map<Integer, Node> map = new HashMap<Integer, Node>();//存放树的所有结点
  public Node getNodeById(int id) {
     return map.get(id);
  } 
  private Tree(){
  ......................
  把数据库里的东西转化成node放到map里
  }
  public List<Node> getChildsById(int id) {
      List<Node> list = new ArrayList<Node>();
      for (int child : map.get(id).childs) {
           list.add(map.get(child));
      }
      return list;
   }
   public Node getFather(int id) {
        Node node = map.get(id);
        return node == null ? null : map.get(node.id);
   }
   public List<Node> getAllFather(int id) {
        List<Node> list = new ArrayList<Node>();
        Node currNode = map.get(id);//这里要非空判断的
        while (!"root".equals(currNode.viewName)) {//看下是否为根
             currNode = map.get(currNode.father);  
             list.add(currNode);
        }
         return list;
   }
   public boolean delete(int id) {
      List<Node> childs = this.getAllChildsById(id);
      for (Node delNode : childs)
          map.remove(delNode.id);
      map.remove(id);
      return !childs.isEmpty();
    }
     。。
    关于调整位置的可能性有很多，自己补上吧
}
构造一个结点记录为20万的树大约为40，50M内存吧！
不信用这个构造函数试试生成一个maxtree个结点，mode叉的树
public Tree(int maxtree, int mode) {
  int id = 0;
  Node root = new Node();
  root.viewName = "root";
  root.id = id;
  Queue<Node> queue = new LinkedList<Node>();
  map.put(root.id, root);
  queue.add(root);
  while (id < maxtree) {
   Node node = queue.poll();
   for (int i = 0; i < mode; i++) {
    Node temp = new Node();
    temp.id = ++id;
    temp.viewName = "" + id;
    temp.father = node.id;
    node.childs.add(temp.id);
    map.put(temp.id, temp);
    queue.add(temp);
   }
  }
  queue.clear();
 }
上面的只是伪码，梢加修改应该可以用。我们的树有了，现在分析下lz提出的问题
1、用存储过程实现存取，直接获得排好序的结果集，能够方便在java中转为树形，缺点是代码复杂，不同数据库无法通用 
2、取出所有结果集在java中循环判断而建立树形结构，缺点是对大数据量的表无法采用，性能差 
这个不会成为问题吧？难到你打算有一个用户，你就调存储过程构建一根树（20万个结点的）？结果集专为树型很简单啊，就算你写的算法再垃圾，给你一个小时够不？我只初始化一根树，而且是在起服务器时！用户不会受到影响，除非你天天重起，而且可以不用存储过程
3. 先取出第一层，然后在java中反复调用多次访问数据库，缺点是数据库连接过多
我们已经把显示的内容（树的结点 Node的viewName）放到tree里了，而当户想看具体内容时，根据id查数据库就OK了（如果用hibernate,可以把常用的信息缓存起来），对于20万结点的树，一个用户通常看几条详细信息而已，不存在连接过多的问题 
4、只取第一层，在页面上点击子节点时通过AJAX动态读取下层，缺点是仅能用于页面展现，不符合前面的条件：实现返回任意节点的所有下级节点
 这个是通常的做法了，不过数据来自于tree，而不是数据库。当想看详细信息时，再查数据库不迟。后面的缺点没理解什么意思当结点信息改变时，要在树中相应的方法添加对数据库的修改

Answer 8

defonds:你的思路是否类似laodizhq的？还是不明白你的这几句话：
“数据库中存放的是一些无序的ID号”与这句“ID值就代表着节点自身的位置”是否冲突呢，那就是ID体现顺序了
“更改节点位置,再方便不过了,直接在代码中修改”，是否指修改所有节点的ID，然后再把数据库中的数据全部update呢？laodizhuq:这种方式如果需要调整层级或改变节点顺序就很困难，因为这意味着要改变ID，但是这个ID作为主键及其它表的外键，通常是无法修改的（如用户表中组织机构ID作为外键，如果修改了组织机构的ID，相关表都需要修改）。再有一种变通的做法是加一个字段以1，1.1,1.1.1这种方式保存层级关系，而ID仍作为单一主键，修改层级和顺序时时则只修改那个字段，但是这也很困难，层级的修改会影响许多条数据，都要修改，而parentID方式通常只需要改一条记录的parentID就可以了。当然你用了parentid,但如果需要调整层级，相当于要做两种操作（改parentid，改ID），更为复杂了。