TA的每日心情 | 开心
2021-3-12 23:18 |
|---|
签到天数: 2 天 [LV.1]初来乍到
|
|
树是一种常用的数据结构，有多种实现方法。本文讨论一种简单的实现及其改进。
1
－2
－－3
－－－4
－－5
－6
对应的存储实现为
Id
ParentId
1
0
0的话代表是根节点
2
1
代表父节点是1
3
2
代表父节点是2
4
3
代表父节点是3
5
3
代表父节点是3
6
2
代表父节点是2
这种实现的优点在于
1） 表示直接。能够表示无限深度的树型结构。
2） 插入简单。插入主键id 和 parentId即可
3） 更新简单。如果将一个节点移到另外一个节点，只需要更新parentId即可。但注意应该避免圈的存在，比如不能将2的父节点设为4，为4是2的子节点之一。
缺点在于
1） 查询困难，需要递归实现。比如要找出1节点的所有子孙
2） 删除。比如删除节点1，则需要将1节点下的所有节点全部删除。
在实际项目中，查询是使用最频繁的，比如要查询1节点下的所有孩子。
为了实现快速查询，增加一个code字段用来描述本节点到跟节点的路径，上述树型结构表示如下：
Id
ParentId
Code
1
0
0001
2
1
0000100002
3
2
000010000200003
4
3
00001000020000300004
5
3
00001000020000300005
6
2
000010000200006
Code 是由固定5个字符组成的序列，用来描述本节点到根节点的路径,而且唯一索引。有了code后，实现查询就容易很多了，比如要查询1节点下的所有孩子，可以使用
Select * from where code like ‘%00001%’
采用Code后的优点：
1． 表示直接
2． 查询简单
3． 插入简单。
4． 删除简单。 Delete where code like ‘%00001%’
缺点：
1． 不能表示无限级的树型结构，最多只能到99999，即10万个节点，这个对于一般应用足够了
2． 更新复杂，需要更新子节点的所有code。
总结：对于web应用来说，查询是多的，更新和删除相对很少，采用code之后能够有效的方便查询，由于code是唯一索引，速度也不会很差，能满足大多数情况下的应用。
Hibernate 代码
/**
*
* 功能：模版的类别,树型结构
*
*/
public class TemplateCategoryEntity extends HibernateEntity {
public static final int CODE_LENGTH = 5;
private String name; //名称，比如杯子，衣服
private String parentId;
private String code;
private int weight = 100; //排序的权值
}
/**
*
* 功能：
*
*/
public class TemplateCategoryEntityDAO extends HibernateDAO {
public HibernateEntity getEntity() {
return new TemplateCategoryEntity();
}
public String getQueryString() {
return "from TemplateCategoryEntity entity";
}
/**
* 继承原有方法
*/
public void insert(IEntity entity) throws DAOException {
final TemplateCategoryEntity category = (TemplateCategoryEntity) entity;
getHibernateTemplate().execute(new HibernateCallback() {
public Object doInHibernate(Session session)
throws HibernateException, SQLException {
//保存当前节点
session.save(category);
if ("0".equals(category.getParentId())) {
category.setCode(ConvertUtil.toFixString(category.getId(),
TemplateCategoryEntity.CODE_LENGTH));
session.update(category);// 更新对象
} else {
// 重新计算code
TemplateCategoryEntity parent = (TemplateCategoryEntity) session.load(
TemplateCategoryEntity.class, category
.getParentId()); // 加载父节点
category.setCode(parent.getCode()
+ "|"
+ ConvertUtil.toFixString(category.getId(),
TemplateCategoryEntity.CODE_LENGTH));
session.update(category);// 更新对象
}
return category;
}
});
}
public void update(IEntity generic) throws DAOException {
final TemplateCategoryEntity entity = (TemplateCategoryEntity) generic;
getHibernateTemplate().execute(new HibernateCallback() {
public Object doInHibernate(Session session)
throws HibernateException, SQLException {
//-----------------------------------------------
if (entity.getId() == entity.getParentId()) {
throw new DAOException("id 和 parentId 不能一样");
}
//检查是否存在圈
if ("0".equals(entity.getParentId())) {
entity.setCode(ConvertUtil.toFixString(entity.getId(),
TemplateCategoryEntity.CODE_LENGTH));
session.update(entity);// 更新对象
} else {
// 重新计算code
TemplateCategoryEntity parent = (TemplateCategoryEntity) session
.load(TemplateCategoryEntity.class, entity
.getParentId()); // 加载父节点
entity.setCode(parent.getCode()
+ "|"
+ ConvertUtil.toFixString(entity.getId(),
TemplateCategoryEntity.CODE_LENGTH));
session.update(entity);// 更新对象
}
// 更新子树里的所有节点
// 如果是把某个节点置为无效，则需要将子树都设置为无效，反之依然
log.debug("current code=" + entity.getCode());
updateChildrenCode(session, entity.getId(), entity.getCode(),
entity.isValidTag());
// ----------------------------------------------
return entity;
}
});
}
/**
* 递归更新子树
*
* @param session
* @param id
* @param code
* @throws DAOException
*/
private void updateChildrenCode(Session session, String id, String code,
boolean validTag) throws DAOException {
String CHILDREN_SQL = "from TemplateCategoryEntity entity where entity.parentId=:id";
Query query = session.createQuery(CHILDREN_SQL);
query.setString("id", id);
List list = query.list();
for (int i = 0; i < list.size(); i++) {
TemplateCategoryEntity child = (TemplateCategoryEntity) list.get(i);
child.setCode(code
+ "|"
+ ConvertUtil.toFixString(child.getId(),
TemplateCategoryEntity.CODE_LENGTH));
child.setValidTag(validTag);
session.update(child);
updateChildrenCode(session, child.getId(), child.getCode(), child
.isValidTag());
}
}
public void delete(IEntity generic) throws DAOException {
final TemplateCategoryEntity entity = (TemplateCategoryEntity) generic;
getHibernateTemplate().execute(new HibernateCallback() {
public Object doInHibernate(Session session)
throws HibernateException, SQLException {
//-----------------------------------------------
TemplateCategoryEntity category = (TemplateCategoryEntity) entity;
ArrayList ids = new ArrayList();
ids.add(category.getId());
listAllChildrenIds(session, ids, category.getId());
log.debug("delete TemplateCategoryEntity ids=" + ids);
String DELETE = "delete from TemplateCategoryEntity where id in (:ids)";
Query query = session.createQuery(DELETE);
query.setParameterList("ids", ids);
query.executeUpdate();
// ----------------------------------------------
return entity;
}
});
}
/**
* 递归查找孩子
*
* @param session
* @param list
* @param id
*/
private void listAllChildrenIds(Session session, List list, String id) {
String CHILDREN_SQL = "select entity.id from TemplateCategoryEntity entity where entity.parentId=:id";
Query query = session.createQuery(CHILDREN_SQL);
query.setString("id", id);
List children = query.list();
for (int i = 0; children != null && i < children.size(); i++) {
String child = ((String) children.get(i));
log.debug("found children:" + child);
list.add(child);
listAllChildrenIds(session, list, child);
}
}
} |
|
|手机版|Java学习者论坛
( 声明：本站资料整理自互联网，用于Java学习者交流学习使用，对资料版权不负任何法律责任，若有侵权请及时联系客服屏蔽删除 )
发表于 2014-11-7 00:03:45