数据库中的树结构-JAVA设计-缓存 -

leaves615

浏览: 3548 次
性别:
来自: 广州

最近访客更多访客>>

陈睿mikechen

自由男神

woodding2008

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (2)

社区版块

存档分类

数据库中的树结构-JAVA设计-缓存

Java 设计模式数据结构 Office Apache

我们通常会在应用中碰到树形结构的内容，比如文件夹/文件模型，部门组织结构，目录树等等，通常在设计模式中叫做 compose 模式。

在数据库中常常这样表示：我们以Catalog (分级目录) 为例子

Catalog (分级目录)
字段名称	字段	类型	备注
目录ID	catalog_id	varchar(36)	pk, not null
目录名称	catalog_name	varchar(50)	not null
父目录ID	parent_id	varchar(36)	fk
创建时间	create_datetime	datetime	not null
目录描述	description	varchar(200)

我们考虑在数据库中一次将所有数据读入内存，然后在内存中生成一个Tree，这样可以减少数据库的访问，增加性能，并且只有的数据方式改变的时候，全部重新从数据库中生成Tree，否则一直保持在内存中。

我们使用标准的DAO模式先生成 POJO类(Catalog)和DAO类(CatalogDAO)。

然后我们建立相对通用的 Tree 和 TreeNode 类。

Tree.java

package com.humpic.helper.tree;

import java.util. * ;

import org.apache.commons.lang.StringUtils;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public abstract class Tree {
 protected static Log log = LogFactory.getLog(Tree. class );

 private Map treeNodeMaps = new Hashtable();
 private TreeNode root;

 /**
 * root if it's parent is empty
 */
 protected void reload(List nodes) {
 log.info( " tree will start reload all data " );

 synchronized ( this ) {
 // initialize
 treeNodeMaps.clear();
 root = null ;

 List treeNodes = new Vector(nodes.size());
 for ( int i = 0 ; i < nodes.size(); i ++ ) {
 TreeNode node = this .transform(nodes.get(i)); // transform
 treeNodes.add(node);
 node.setTree( this );
 treeNodeMaps.put(node.getNodeId(), node);
 }

 for ( int i = 0 ; i < treeNodes.size(); i ++ ) {
 TreeNode node = (TreeNode) treeNodes.get(i);
 String parentId = node.getParentId();
 if (this . isRootNode(node)) {
 if (root == null ) {
 root = node;
 } else {
 log.error( " find more then one root node. ignore. " );
 }
 } else {
 TreeNode parent = (TreeNode) treeNodeMaps.get(parentId);
 if (parent != null ) {
 parent.addChild(node);
 node.setParent(parent);
 } else {
 log.warn( " node [id= " + node.getNodeId() + " ]: missing parent node. " );
 }
 }
 }
 }

 if (root == null ) {
 log.error( " the root node is not be defined " );
 }
 }

 protected boolean isRootNode(TreeNode node ) {
 return StringUtils.isBlank(node.getParentId() ) ;
 }

public TreeNode getRootNode() {
 return root;
 }

 public TreeNode getTreeNode(String nodeId) {
 return (TreeNode) treeNodeMaps.get(nodeId);
 }

 public void addTreeNode(TreeNode node) {
 synchronized ( this ) {
 treeNodeMaps.put(node.getNodeId(), node);

 String parentId = node.getParentId();
 if (StringUtils.isNotBlank(parentId)) {
 TreeNode parent = getTreeNode(parentId);
 if (parent != null ) {
 parent.addChild(node);
 node.setParent(parent);
 } else {
 log.error( " parent cannot be found: " + node.getParentId());
 }
 } else {
 if (root == null ) {
 root = node;
 } else {
 log.error( " find more then one root node. ignore. " );
 }
 }
 }
 }

 public void deleteTreeNode(String nodeId) {
 synchronized ( this ) {
 TreeNode node = getTreeNode(nodeId);
 if (node == null )
 throw new IllegalArgumentException(nodeId + " cannot be found. " );

 if (node.getParent() == null ) {
 root = null ;
 treeNodeMaps.clear();
 log.warn( " the root node has been removed. " );
 } else {
 node.getParent().getChildren().remove(node);

 treeNodeMaps.remove(nodeId);
 List children = node.getAllChildren();
 for ( int i = 0 ; i < children.size(); i ++ ) {
 TreeNode n = (TreeNode) children.get(i);
 treeNodeMaps.remove(n.getNodeId());
 }
 }
 }
 }

 /**
 * <pre>
 * Usage: Office ->
 *
 * public TreeNode transform(Object info) {
 * OfficeInfo office_info = (OfficeInfo) info;
 * TreeNode node = new TreeNode();
 * node.setNodeId(office_info.getOfficeId());
 * node.setParentId(office_info.getParentId());
 * node.setBindData(office_info);
 * return node;
 * }
 * </pre>
 */
 protected abstract TreeNode transform(Object info);
}

TreeNode.java

package com.humpic.helper .tree;

import java.util.List;
import java.util.Vector;

import org.apache.commons.collections.Predicate;
import org.apache.commons.lang.ObjectUtils;

public class TreeNode {

 private Tree tree;
 private TreeNode parent;
 private List children = new Vector();
 private List childrenGroup = new Vector();
 private String nodeId;
 private String parentId;
 private Object bindData;

 public String getNodeId() {
 return nodeId;
 }

 public void setNodeId(String nodeId) {
 this .nodeId = nodeId;
 }

 public String getParentId() {
 return parentId;
 }

 public void setParentId(String parentId) {
 this .parentId = parentId;
 }

 public Object getBindData() {
 return bindData;
 }

 public void setBindData(Object bindData) {
 this .bindData = bindData;
 }

 public Tree getTree() {
 return tree;
 }

 public void setTree(Tree tree) {
 this .tree = tree;
 }

 public void setParent(TreeNode parent) {
 this .parent = parent;
 }

 public TreeNode getParent() {
 return this .parent;
 }

 public List getChildren() {
 return this .children;
 }

 public void addChild(TreeNode node) {
 children.add(node);
 }

 /**
 * get all children, and chilren's children
 */
 public List getAllChildren() {
 if ( this .childrenGroup.isEmpty()) {
 synchronized ( this .tree) {
 for ( int i = 0 ; i < this .children.size(); i ++ ) {
 TreeNode node = (TreeNode) this .children.get(i);
 this .childrenGroup.add(node);
 this .childrenGroup.addAll(node.getAllChildren());
 }
 }
 }
 return this .childrenGroup;
 }

 /**
 * get all children, and chilren's children
 */
 public List getAllChildren(Predicate predicate) {
 List groups = new Vector();
 fillAllChildren(groups, predicate);
 return groups;
 }

 private void fillAllChildren(List groups, Predicate predicate) {
 for ( int i = 0 ; i < this .children.size(); i ++ ) {
 TreeNode node = (TreeNode) this .children.get(i);
 if (predicate.evaluate(node)) {
 groups.add(node);
 node.fillAllChildren(groups, predicate);
 }
 }
 }

 /**
 * get all parents, and parent's parent
 */
 public List getParents() {
 List results = new Vector();
 TreeNode parent = this . getParent();
 while (parent != null ) {
 results.add(parent);
 parent = parent.getParent();
 }
 return results;
 }

 /**
 * A.isMyParent(B) == B is A' parent ? 
 * root.isMyParent(null) == true; 
 * root.isMyParent(*) == false 
 * *.isMyParent(null) == false
 */
 public boolean isMyParent(String nodeId) {
 TreeNode target = tree.getTreeNode(nodeId);
 TreeNode parent = this .getParent();
 if (parent == null ) {
 return target == null ;
 } else {
 return parent.equals(target);
 }
 }

 /**
 * A.isMyAncestor(B) == B is A' ancestor ? 
 * *.isMyAncestor(null) == true;
 */
 public boolean isMyAncestor(String nodeId) {
 TreeNode target = tree.getTreeNode(nodeId);
 if (target == null )
 return true ;

 return target.getAllChildren().contains( this );
 }

 /**
 * A.isMyBrother(B) == B is A' brother ? 
 * *.isMyBrother(null) == false
 */
 public boolean isMyBrother(String nodeId) {
 TreeNode target = tree.getTreeNode(nodeId);
 if (target == null )
 return false ;

 TreeNode p1 = this .getParent();
 TreeNode p2 = target.getParent();
 return ObjectUtils.equals(p1, p2);
 }

}

然后建立业务 Tree

CatalogTree.java

package com.humpic.helper.tree;

import java.util.List;
import org.apache.commons.collections.Predicate;

public class CatalogTree extends Tree {
    private static CatalogTree instance = null ;

    private CatalogTree() {}

    public static synchronized CatalogTree getInstance() {
        if (instance == null ) {
            instance = new CatalogTree();
            instance.reloadCatalogs();
        }
        return instance;
    }

    protected TreeNode transform(Object info) {
        Catalog catalog = (Catalog) info;
        TreeNode node = new TreeNode();
        node.setNodeId(catalog.getCatalogId());
        node.setParentId(catalog.getParentId());
        node.setBindData(catalog);
        return node;
    }

    public void reloadCatalogs() {
        List nodes = CatalogDAO.getInstance().findAll();
        super .reload(nodes);
    }

    public Catalog getCatalogNode(String catalogId) {
        TreeNode node = super .getTreeNode(catalogId);
        return node == null ? null : (Catalog) node.getBindData();
    }
}

最后，我们只要使用以下的语句就可以了：

1. CatalogTree.getInstance().getTreeNode(...)
2. CatalogTree.getInstance().getCatalogNode(...)
3. CatalogTree.getInstance().getRootNode()

然后通过 TreeNode，就可以得到 parent, parents 和 children, allChildren

分享到：