左右值分析
表结构
B_Tree
id
name 名称
leftValue 左值
rightValue 右值
treelevel 级别
左右值规则:
某一节点的leftValue,rightValue
leftValue为该节点包含子节点的开始
rightValue为该节点包含子节点的左值的结束
也就是 leftValue=<leftValue<=rightValue
为这个节点包含子节点的所有范围
左右数据插入实现:
pId==0
如果是第一层:
select max(rightValue) maxRight from B_Tree where treelevel=0;
查询第一层最大的右值 maxRight
新的数据的左右值为
leftValue=maxRight+1;
rightValue=maxRight+1;
如果非第一层:pId!=0
select leftValue p_leftValue, rightValue p_rightValue,treelevel p_treelevel from B_Tree where id=:pId;
查询要添加节点(C)的父级一层的 p_leftValue,p_rightValue
select max(rightValue) maxRight from B_Tree where treelevel=p_treelevel+1 and leftValue>p_leftValue and rightValue<p_rightValue
获取要添加节点父节点(P)下一级节点最大的右值 maxRight 最大右值:maxLeft
如果maxRight==0表示P下还没有子节点
C 的左右值和treelevel为:
maxRight=p_leftValue+1
leftValue=maxRight;
rightValue=maxRight;
treelevel=p_treelevel+1;
如果maxRight>0表示P下已经有子节点
C 的左右值和treelevel为:
maxRight++;
leftValue=maxRight;
rightValue=maxRight;
treelevel=p_treelevel+1;
maxRight 已经是P节点包含的最大值
update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)
将原先右值>=maxRight的所有列的右值+1,
update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight
将原先左值>=maxRight的所有列的左值+1
例如:
左值 名称 右值 层级
首次插入:
1 首 1 0
表中没有数据,查到为0 添加数据的 左右值都为1
第二次插入
2 第二 2 0
表中有数据,查到maxRight为1 添加数据 的左右都为maxRight+1=2
第三次插入
3 第三 3 0
插入子节点: 插入子节点后父节点层次的变更
2 首一 2 1 1 首次 2 0 3 第二 3 0 4 第三 4 0
在第三层级中插入子节点
查到 maxRight=0 当前节点的左右值直接使用父节点的左值p_leftValue+1=2
maxRight=2
update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)
update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight
3 首二 3 1 1 首次 3 0 4 第二 4 0 5 第三 5 0
查到 maxRight=2 当前节点的左右值直接使用父节点的左值=2+1
maxRight=2
update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)
update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight
4 首二(A) 4 2 1 首次 4 0 5 第二 5 0 6 第三 6 0
查到 maxRight=0 当前节点的左右值直接使用父节点的左值=p_leftValue+1=4
maxRight=5
update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)
update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight
获取该节点和子节点: id
select leftValue pleft,rightValue pright from B_Tree where id=:id; select * from B_Tree where leftValue>=pleft and rightValue<=pright;
合体后的查询
select a.* from B_Tree a join (select leftValue pleft,rightValue pright from B_Tree where id=:id) b on 1=1 where leftValue>=b.pleft and rightValue<=b.pright; select a.* from B_Tree a where exists (select 1 from B_Tree b where b.id=:id and a.leftValue>=b.leftValue and a.rightValue<=b.rightValue)
代码实现
注:该实现是基于hibernate建表的实体+spring+mybatis的实现
@Override public synchronized void saveTreeNode(T item) throws Exception{ if(item!=null&&item.getpId()!=null){ String tableName=ReflectGenricUtil.getTableName(item.getClass()); Integer maxRight=0; //第一层 if("0".equals(item.getpId())){ StringBuffer maxRightSql=new StringBuffer(); maxRightSql.append("select max(rightValue) MAXRIGHT from ").append(tableName).append(" where treeLevel=? "); Map<String, Object> mapMax = this.getBaseDao().findMapBySql(maxRightSql.toString(), 0); if(mapMax!=null&&mapMax.size()>0){ maxRight=(Integer) mapMax.get("MAXRIGHT"); if(maxRight==null){ maxRight=0; } } maxRight++; item.setLeftValue(maxRight); item.setRightValue(maxRight); }else{ StringBuffer parentSql=new StringBuffer(); parentSql.append("select leftValue P_LEFTVALUE, rightValue P_RIGHTVALUE,treelevel P_TREELEVEL from ").append(tableName) .append(" f ").append(" where id=?"); Map<String, Object> parentMap = this.getBaseDao().findMapBySql(parentSql.toString(), item.getpId()); if(parentMap!=null&&parentMap.size()>0){ Integer p_rightValue=(Integer) parentMap.get("P_RIGHTVALUE"); Integer P_leftValue=(Integer) parentMap.get("P_LEFTVALUE"); Integer p_treelevel=(Integer)parentMap.get("P_TREELEVEL"); StringBuffer rightMaxSql=new StringBuffer(); rightMaxSql.append(" select max(rightValue) MAXRIGHT from ").append(tableName) .append(" where treelevel=").append(p_treelevel+1) .append(" and leftValue>").append(P_leftValue) .append(" and rightValue<? "); Map<String, Object> mapMax = this.getBaseDao().findMapBySql(rightMaxSql.toString(), p_rightValue); if(mapMax!=null&&mapMax.size()>0){ maxRight=(Integer) mapMax.get("MAXRIGHT"); } if(maxRight==null){ maxRight=P_leftValue+1; }else{ maxRight++; } item.setLeftValue(maxRight); item.setRightValue(maxRight); item.setTreeLevel(p_treelevel+1); } } StringBuffer rightUpdateSql=new StringBuffer(); rightUpdateSql.append("update ").append(tableName) .append(" set rightValue=rightValue+1 ") .append(" where rightValue>=?"); StringBuffer leftUpdateSql=new StringBuffer(); leftUpdateSql.append("update ").append(tableName) .append(" set leftValue=leftValue+1 ") .append(" where leftValue>=?"); this.getBaseDao().updateBySql(rightUpdateSql.toString(), maxRight-1); this.getBaseDao().updateBySql(leftUpdateSql.toString(), maxRight); this.getBaseDao().save(item); } }
相关代码
/** * 功能说明:根据注解获取类注解上的表名 * @author ducc * @updated * @param clazz * @return */ public static String getTableName(final Class clazz){ Table table = (Table) clazz.getAnnotation(Table.class); return table.name(); } public Map<String,Object> findMapBySql(String sql,Object... obj )throws SQLException{ SqlRunner sr=new SqlRunner(getSqlSession().getConnection()); List<Map<String,Object>> selectAll=sr.selectAll(sql, obj); if(selectAll!=null&&selectAll.size()>0){ return selectAll.get(0); } return null; } public Integer updateBySql(String sql,Object... obj)throws SQLException{ SqlRunner sr=new SqlRunner(getSqlSession().getConnection()); return sr.update(sql, obj); } public Integer save(T item) { generateId(item); return this.getSqlSession().insert(getSqlName(SQL_SAVE),item); }
测试结果
文章评论
预排序遍历树算法牺牲写性能的改进http://wenku.baidu.com/view/634656b0561252d381eb6e8f