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

我们通常会在应用中碰到树形结构的内容，比如 文件夹/文件模型， 部门组织结构，目录树等等，通常在设计模式中叫做 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 -&gt;
     *
     * 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 ? <br>
     * root.isMyParent(null) == true; <br>
     * root.isMyParent(*) == false <br>
     * *.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 ? <br>
     * *.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 ? <br>
     * *.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