树形模型设计

树形结构组件

因为每个帖子都有回贴，因此，该贴和回贴之间就形成一个父子关系，这样一个主题可能有多个回贴，关系如下：

[thread]

|- [message]

我们是通过ForumMessage中的parentMessage来记录这种树形关系的。

在数据库中，帖子和回帖保存的是以messageId和parentMessageId父子关系存储，而我们需要使用的是一个树形结构，这里有一个不顾性能后果的直觉错误行为，分析如下：

例如为获得某个Thread的所有子贴，包括子贴的回帖等等，直接查询数据库，如果这颗树包含的数据很多，这种办法是需要大量的数据库连接和反复查询，无疑非常耗费性能，尤其当访问量提升时，系统将会变得非常的慢，我们寻求的是一种可伸缩/可扩展的解决方案。

正确的解决方案：

我们需要将这颗树涉及的数据点（不是完整数据，而是数据ID）放入缓存中，在内存中建立一个树，这样，当反复访问这个Thread时，只要遍历内存中的树获得message ID，再根据ID从数据库获取完整的ForumMessage，当然，也可能这个ForumMessage同时也存在缓存中，直接从缓存获取即可，更加降低数据库的频繁访问。

首先，我们需要寻求如何根据messageId和parentMessageId形成一个树的算法，这实际是一颗二叉树的算法，一个节点有两个节点：左边是最靠近自己的孩子；右边是与自己平行的兄弟。LongTreeWalker是实现这种算法的一个类，该类来自原Jive版本，主要是对主键是long的值进行树形结构的运算。

树的遍历有两种种方式：

找出当前二叉树节点的左孩子，然后再找出该孩子左孩子和右兄弟，如此反复一直追溯到最后；这样获得所有孩子的主键ID集合在实际应用中，除了得到孩子集合，我们常需要了解一个孩子节点是属于枝或叶，根据枝或叶采取不同的行为，使用该方法则需要在遍历每个孩子集合时，再次回到二叉树中查询该节点是枝还是叶，有性能损耗。

使用Composite模式，将枝Branch和叶Leaf分别定义为TreeNode的两个子对象，再结合访问者模式，可实现不同的树遍历访问。灵活度和重要性很好，但是有些难度。

Composite模式

Compsite模式是让客户端访问某个对象时，这个对象可能是某个整体（如整个帖子集合ForumThread），也可能是某个部分（如某个帖子ForumMessage），不能因为这个对象有这些区别，导致客户端的代码不同，也就是说，我们通过Compsite模式将这些区别封装起来，统一对客户端访问接口，客户端只管访问即可，不用客户端自己进行代码区分，访问的是整体还是部分。

Compsite模式UML图如下表示：

Composite模式可以让我们封装复杂的树形结构，那么我们是否需要这种封装，还是为一个ForumThread提供一个TreeWalker功能，让任何客户端都通过TreeWalker来自己遍历这个树形结构呢？总结如下：

1. 采取Composite模式封装复杂的树形结构，这样外界要访问一个主题贴需要树形遍历时，由Composite内部来树形算法来遍历，外界只要告诉要怎样的结果即可。

优点：封装了树形结构的遍历算法，外界客户端无需自行进行帖子的树形结构相关判断代码。

缺点：对树形结构的操作有各种各样，而且以后可能有新增新的操作，这可能涉及修改Composite模式的Component接口。

Composite模式：http://www.jdon.com/designpatterns/composite.htm

这种采取Composite模式封装树形结构遍历的方法，为防止新增新的操作改动接口，可引入访问者模式，下面这篇文章谈到了用C++实现Composite模式+Visitor模式解决树形结构封装算法:

http://members.home.nl/r.f.pels/articles/misc/C++PatternsAndTreesSeparatingKnowledge.html

它主要讨论了如何分离树形结构的不同类的对象和用户界面的树形结构表现这两个方面。

2.不采取Composite模式进行树形结构封装，就象原来Jive一样，给每个主题贴提供一个TreeWalker对象，这样外界如果要遍历这个主题贴时，自己通过TreeWalker去遍历树形结构。

优点：比较简单方便，符合简单的模型编程，ForumThread主题贴是一个模型，里面提供一个自身树形结构遍历，非常开放，外界客户端有新的操作，只要得到模型ForumThread就可以了。

缺点：TreeWalker提供的树形结构遍历方法有限，有可能不能满足新的操作或新的功能的需要。

我们决定采取第一种方案，虽然第2种方案比较简单，但是问题也很明显，论坛主要功能是主题贴和回帖的显示功能，这种显示可能有各种方式：例如树形结构或扁平式样另外还可能有新的显示排列方式，因此必须建立一种机制能够方便拓展。

原来的Jive是怎样处理显示树形结构或扁平式样呢？显示树形结构时，是从TreeWalker中获得帖子集合；而扁平式是靠直接查询数据库SQL语句组合获得的，就不使用TreeWalker了，很显然这种方式是没有拓展机制的。

我们要将帖子集合的遍历在Composite模式中实现。外界只要告诉Composite模式，利用帖子集合实现的功能即可，也就是说，当我们需要利用树形结构遍历时，实现一个Visitor访问者子类即可。

使用Composite+Visitor模式带来缺点是：对访问者进行了一定限制，例如可能只是需要一个帖子集合，必须将将这段代码变成一个访问者类。

Composite模式是一种内敛式样或者趋向闭合的模式，该模式是将以前在客户端中实现的代码强制收回，这对一个Open开放结构有所伤害。

TreeModel建模

现在，我们已经决定采取这两种树形结构遍历方式，下面关键一步如何设计一个对象表达这两种方式共同点，这两种方式其实是一种处理过程，属于Service性质的功能，既然有处理功能，那么就有处理对象，这个对象就是我们需要建模的对象。

我们设计一个Domain Model为TreeModel，这个模型其实代表着一个主题下一系列帖子的树形关系，它是一个关系模型。当然，其中也包含了这些帖子主键这样的数据集合。

有了这个TreeModel，我们就可以通过专门处理TreeModel的处理器TreeManager来实现不同的树形结构遍历方式，如下图：

不管采取Compositor+Visitor或者直接使用TreeWalker，都可以通过TreeManager进行选择调用。

这样，Model和Service这两条路线我们都已经进行了概要设计。

下面谈谈TreeModel对象的生存周期：

TreeModel和ForumThread是一种关联关系，而且每个ForumThread有一个自己的树形结构TreeModel，这是一种强聚合，也即合成关系。

当我们从ForumMessageService通过getForumThread方法获得新的ForumThread时，同时读取其树形结构数据TreeModel，以下是getForumThread方法中的一段代码：

TreeModel treeModel = messageQueryDao.getTreeModel(forumThread);

forumThread.setTreeModel(treeModel);

有了这个ForumThread的TreeModel，我们就可以在代码其他地方根据TreeModel来判断一些和树形结构相关的问题，如某个帖子是否有回帖等。

组件的使用

1. 创建TreeModel：树形节点有一个根节点rootID，这个树有多少节点nodeCount。

TreeModel treeModel = new TreeModel(rootID, nodeCount)。

2. 构件TreeModel：关系数据库有ID和ParentID来表达树形两个节点。

treeModel.addChild（ID, ParentID）

3. 有了TreeModel，再构建相应操作Visitor。

4.       TreeNodeFactory TreeNodeFactory = new TreeNodeFactory(treeModel);
TreeNodeVisitable treeNode = TreeNodeFactory.createNode(key);
TreeVisitor myVisitor = new MyVisitor ();
treeNode.accept(myVisitor);