存档

‘算法’ 分类的存档

分级查询与递归查询的区别

2013年4月11日 没有评论

概要说明

以oracle数据库hr用户下自带的employees表为例:
要查询出employees表中manager_id为100的雇员的所有下级:

递归查询

在hibernate中可以写如下的hql语句:

"from Employees e where e.manager_id = 100"

递归的方法如下:

public String getEmployeesRoot()
{
	String HQL =“from Employees e where e.manager_id = 100”;
	List list = baseService.getAllByHQL(HQL);
	for(int i=0;i<list.size();i++)
	{
		Employees employees = (Employees) list.get(i);
		Set childNodes = employees.getChilds();
		recursionEmployees (childNodes);
	}
}

private void recursionEmployees(Set childNodes) {
	Iterator it = childNodes.iterator();
	while (it.hasNext()) {
		Employees employees = (Employees) it.next();
		Set node = employees.getChilds();
		if (!node.isEmpty()) {
			recursionEmployees(node);
		}
	}
}

现在对以上的递归查询进行分析:
1、访问数据库的次数:
因为每一个节点在取出来之后都要通过getChild(Set childSet)去取当前节点的子节点,(实际上就是执行from employees e where e.manager_id = ?)并判断是否为空,如果非空则再次进入递归;
所以每一个节点有要请求一次数据库,所有请求次数与树的节点数相同!
2、内存占用程度:
在递归时要存在动态的压栈与弹栈的过程,并随着节点数与节点层数的增加面增加!

阅读全文…

数据库中树形结构存储与优化 左右值树的处理

2012年8月3日 1 条评论

       无论是成本核算中的产品结构BOM,还是价格概算中的WBS工作任务分解,你都会遇到要在数据库中存储树型结构数据的情况。同时,除非你使用一种像XML的数据库,否则关系数据库中的表都不是层次结构的,他们只是一个平坦的列表。所以你必须找到一种把树型结构进行数据库转化的方法。

       在本文中,我们将探讨改进前序遍历树算法。我将举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下:

阅读全文…