祝贺Javaeye2.0, 关联数据结构
Javaeye2.0 社区的版面，感觉很不错。
我也在做一个数据关联结构的开源内容系统。
现在把核心数据结构写在这里，供参考，抛砖引玉。
文中的例子和说明，是和femto讨论的过程中加上的。
-----------------------------------------
我正在做一个内容组织整理的开源作品。
主要功能是：
能够让用户自由指定homepage （或者其他任何属于自己的page）上显示什么内容，可以任意组织整理。
功能上相当于 CMS + 具有FTP功能的个人空间。
要达到这个目的，需要一个非常灵活的数据结构。all in one, cover all content formats。
我就把这个数据结构，写在这里，和大家讨论，也算是一个具体例子。
Entity 说明如下（用户相关信息省略）：
1. Content.
这个Entity 很简单，主要具有一个 name 字段, 和 content 字段。
可以代表 blog, news, tag, directory, topic, thread, article, post, wiki item, etc.
2. Ref
所有的关系都在这里管理。content本身不具有任何关系。
Ref 要达到这样的功能，多对多。任意的 content 之间，都可以组装成父子关系。递归都没有关系。没有任何限制。
id,
target_id
id 就是一个 ref id, alias id.
target id 就是 content id.
3. Ref_relation.
parent_ref_id
child_ref_id
Ref + Ref_Relation 两个table，就可以表述所有的多对多关系。
---------
为什么不用一个 content_relation ( parent_content_id, child_content_id ) 表达多对多，非要多出一个Ref ？
这是为了按照ref提取一棵数据树.
如果只有content_relation，无法确定如何从这些关系中，提取某个确定组织的数据树。
这个理解起来不那么直观，可以思考几个自由组织的例子。
举例，
几个论坛 bbs1, bbs2....
每个论坛都有 A, B, C 等分类。
每个分类都有 a, b, c, 等版块。
每个版块都有 topic
每个topic 都有 reply.
这是一个树形结构数据。
wiki 也是一个树形结构数据。
我设想的结构中，任何一个content item 可以出现在任何地方，多次出现。毫无限制。
比如，我有一个content item，叫做 "新世纪"
我想，让它成为 BBS1 下面的分类。
那么。Ref 数据
id, target_id
1001, bbs1
1002, 新世纪
----------------------
ref_relation 数据
parent, child
1001 , 1001
----------------------
这样就可以了。
其实这个就是用来表达
parent, child
bbs1 , 新世纪
这个父子关系。
多出来一个Ref是为了提取数据的需要。
设想一个多层数据的例子，就会发现简单的 parent child 不够用。必须多出来一个Ref。
想想看这样的例子。
现在content table 就有一个 新世纪 记录。
现在需要构成一个这样的树形结构。
新世纪
|- 新世纪
.........|- 新世纪
.........|- 新世纪
................| - 新世纪
|- 新世纪
如何表达？用简单的parent child根本没有办法。
用ref就没有问题。
Ref数据
id, target_id
1001, 新世纪
1002, 新世纪
1003, 新世纪
1004, 新世纪
1005, 新世纪
1006, 新世纪
----------------------
ref_relation 数据
parent, child
1001 , 1002
1002, 1003
1002, 1004
1004, 1005
1001, 1006
----------------------
一个更具体的例子。写起来，太麻烦了。就不写了。:D 可以设想出来很多。
为了看起来方便，上面出现 新世纪 的地方。实际上是 新世纪 这个内容对应的 content ID。
数据核心结构就是这么多. 具体让它工作起来, 来需要更多的辅助数据结构. 比较繁琐, 不再赘述.
大家可能有更好的设计方案。
我把自己的基本设计写在这里，抛砖引玉。
femto:
可不可以把你的ref理解成alias,一个content可以有多个别名，这样可以在多个地方被引用？
my answer:
对阿。
ref引用就是alias的意思。
文件系统中的快捷方式link.
多个virtual node指向真正的node。
我想，content name字段，应该足以标识了。
比如，
有一个content, name叫作 xxx 论坛，下面连接了很多 topic 。
有一个content, name叫作 xxx wiki，下面也连接了很多 topic 。
我想，content name字段，应该足以标识了。
比如，
有一个content, name叫作 xxx 论坛，下面连接了很多 topic 。
有一个content, name叫作 xxx wiki，下面也连接了很多 topic 。
这样的话要显示如下的tree,那就要按照字符串匹配每个fm_ref对应的content.name了吧?除了这个办法我还是没想到怎么表示弄处这么个tree.
新世纪
|- 新世纪
.........|- 新世纪
.........|- 新世纪
................| - 新世纪
|- 新世纪 8 楼 jackyz 2006-08-10 buaawhl 写道
我设想的结构中，任何一个content item 可以出现在任何地方，多次出现。毫无限制。
比如，我有一个content item，叫做 "新世纪"
我想，让它成为 BBS1 下面的分类。
那么。Ref 数据
id, target_id
1001, bbs1
1002, 新世纪
----------------------
ref_relation 数据
parent, child
1001 , 1001
----------------------
这样就可以了。
其实这个就是用来表达
parent, child
bbs1 , 新世纪
这个父子关系。
多出来一个Ref是为了提取数据的需要。
设想一个多层数据的例子，就会发现简单的 parent child 不够用。必须多出来一个Ref。
想想看这样的例子。
现在content table 就有一个 新世纪 记录。
现在需要构成一个这样的树形结构。
新世纪
|- 新世纪
.........|- 新世纪
.........|- 新世纪
................| - 新世纪
|- 新世纪
如何表达？用简单的parent child根本没有办法。
用ref就没有问题。
Ref数据
id, target_id
1001, 新世纪
1002, 新世纪
1003, 新世纪
1004, 新世纪
1005, 新世纪
1006, 新世纪
----------------------
ref_relation 数据
parent, child
1001 , 1002
1002, 1003
1002, 1004
1004, 1005
1001, 1006
----------------------
我也正在思考相同的问题，在“Content集中管理”这一点上，思路似乎很接近。
不过，对于你的这个ref(Alias)，除了这种“自己的parent是自己”需要Alias之外，我想象不出还有什么情况下必须这个概念？或许我没能清楚的理解到你的意思，能否展开说明一下？
另外，我不觉得这种二元的ref_relation结构能够表示所有应用之中的“结构”。我比较倾向于为每一种“应用”建立自己的“关系结构”。
比如，论坛中的Post：
Posts(
board_id, -- 版
thread_id, -- 主题
parent_id, -- 回复对象
post_id -- 帖子
)
这些id都可以参照Content表之中的数据，这一点我们看法一致。
如果用ref_relation，固然也可以实现这样的结构，但比如：列表一个版内的所有帖子(注意，跨越了主题这个层次)，这样的需求，实现起来似乎就有些别扭。
此外，如，一条内容可以出现在多个不同的地方，比如，发一篇东西，既是某贴的回复，又是网志的内容，同时又与n个标签关联。这里已经提到了3个概念，如果全部都塞到这一个ref_relation表，那么它：A,是否需要一个类型标示？B,是否足够(比如，如果单就这个内容而言就同时需要不止一个关联对象，如上例中的Post有必要同时关联Board，Thread和Parent)。
我想你的ref方案中可能需要多个ref纪录来处理这件事情。如果是这样的话，那就是用ref的复杂性来化解这个问题了，如果在一个这么“单纯”的ref上赋予太多的职责，那么除了减少表，这样的代价是否带来了其它的价值？ 9 楼 buaawhl 2006-08-11 xmx0632 写道
这样的话要显示如下的tree,那就要按照字符串匹配每个fm_ref对应的content.name了吧?除了这个办法我还是没想到怎么表示弄处这么个tree.
新世纪
|- 新世纪
.........|- 新世纪
.........|- 新世纪
................| - 新世纪
|- 新世纪
这里使用 新世纪，是为了容易说明。实际上数据表使用的不是content.name，而是content.id。
在我的设计中，数据结构本身不体现blog, wiki, forum等分类。
这些分类是依靠 View 来表现的。
用户需要给某一棵数据树指定一个View。
这部分属于辅助数据结构，db schema更加复杂。
由于 data is a tree。view template 定义也要是一棵树。
比如，前3层按照Portal的方式，行列嵌套，下面3层按照wiki tree方式来显示，最多只能显示6层数据，每层数据最多显示前10条。等定义。
程序会提供很多 default view, 比如 blog, forum, wiki, cms, news, portal. etc.
用户也可以自己随意组织view。
Jackyz 写道
我也正在思考相同的问题，在“Content集中管理”这一点上，思路似乎很接近。
不过，对于你的这个ref(Alias)，除了这种“自己的parent是自己”需要Alias之外，我想象不出还有什么情况下必须这个概念？或许我没能清楚的理解到你的意思，能否展开说明一下？
另外，我不觉得这种二元的ref_relation结构能够表示所有应用之中的“结构”。我比较倾向于为每一种“应用”建立自己的“关系结构”。
比如，论坛中的Post：
Posts(
board_id, -- 版
thread_id, -- 主题
parent_id, -- 回复对象
post_id -- 帖子
)
这些id都可以参照Content表之中的数据，这一点我们看法一致。
如果用ref_relation，固然也可以实现这样的结构，但比如：列表一个版内的所有帖子(注意，跨越了主题这个层次)，这样的需求，实现起来似乎就有些别扭。
此外，如，一条内容可以出现在多个不同的地方，比如，发一篇东西，既是某贴的回复，又是网志的内容，同时又与n个标签关联。这里已经提到了3个概念，如果全部都塞到这一个ref_relation表，那么它：A,是否需要一个类型标示？B,是否足够(比如，如果单就这个内容而言就同时需要不止一个关联对象，如上例中的Post有必要同时关联Board，Thread和Parent)。
我想你的ref方案中可能需要多个ref纪录来处理这件事情。如果是这样的话，那就是用ref的复杂性来化解这个问题了，如果在一个这么“单纯”的ref上赋予太多的职责，那么除了减少表，这样的代价是否带来了其它的价值？
确实需要多个ref记录来处理这件事情。事实上，ref的数据一般来说是content数据的5倍或者更多，因为主要希望体现的是 组织整理。
除了减少表，还有就是达到了随意组织的目标。
我的这个设想只是一个 内容组织整理系统，并没有forum, post, thread, topic等概念，也没有blog, wiki, portal等概念。
这些概念都不体现在系统的数据结构定义db schema中，而是体现在数据中。
举一个例子。比如，论坛精华贴。并不是依靠某一个字段来标志，而是用ref完全重新整理出另外一套贴子组合。这就是说，任何一个用户都可以按照自己的口味来组织一套精华贴。
对了，在系统中，任何一个用户都可以开辟管理自己的wiki, 论坛，portal, cms。并在他人许可的情况下，引入其他用户内容系统里面的内容。
这种设计的主要思路是，利用数据代替结构，达到最大的灵活性。性能会有很大影响。其中有一个关键字段 display order来提高性能。
fm_ref_relation{
parent_id bigint,
child_id bigint,
display_order int,
}
这里面有个 display order。用来代替 order by
能够提高分页速度。比如，display_order >= 11 and display_order <= 20。
display order 什么时候设置。一个是用户明确指定，一个是自动处理，比如按照时间倒序，按照下一层数据的时间倒序等。 10 楼 jackyz 2006-08-11 buaawhl 写道
我的这个设想只是一个 内容组织整理系统，并没有forum, post, thread, topic等概念，也没有blog, wiki, portal等概念。这些概念都不体现在系统的数据结构定义db schema中，而是体现在数据中。
如果把这些概念化解到数据之中，那么在你的设想之中，是如何来提供显示所需要的“数据视图”的呢？
比如：仍然是forum，比如boardlist的页面。
首先，我需要知道总共有多少个版以及每个版的名称等信息，这个需求可以通过特定的ref_id来获得(不过这个“特定”是怎么标记出来的？)。
然后，我需要知道每个版的最后更新时间，这个也可以通过对tree的递归查询获得，但，因为post的回复层次是不定的，而ref_relation又只表达了二元的关系，那么这个递归的深度也会是不定的。
再者，我需要知道每个版面的主题和回复的总数，和上面一样，也可以通过递归获得，递归深度不定。
似乎是可以满足数据的需求，但是，如果加上权限呢？比如，某个版，只能高级会员访问，那么这个权限的设定，要写到哪里？如果是forum有自己的结构，那么可以写在这个结构数据上，而现在没有这个结构，似乎就不好办了。
buaawhl 写道
这种设计的主要思路是，利用数据代替结构，达到最大的灵活性。性能会有很大影响。其中有一个关键字段 display order来提高性能。
对，性能问题是个大问题。displayorder似乎不能解决上述“获取数据的复杂性”带来的性能问题。 11 楼 partech 2006-08-11 越抽象就越缺少控制、越灵活、越不好理解，越具体就越好控制、越容易理解、越僵硬。
我认为，两个极端都不是好的选择。 12 楼 xmx0632 2006-08-11 buaawhl 写道xmx0632 写道
这样的话要显示如下的tree,那就要按照字符串匹配每个fm_ref对应的content.name了吧?除了这个办法我还是没想到怎么表示弄处这么个tree.
新世纪
|- 新世纪
.........|- 新世纪
.........|- 新世纪
................| - 新世纪
|- 新世纪
这里使用 新世纪，是为了容易说明。实际上数据表使用的不是content.name，而是content.id。
在我的设计中，数据结构本身不体现blog, wiki, forum等分类。
这些分类是依靠 View 来表现的。
用户需要给某一棵数据树指定一个View。
这部分属于辅助数据结构，db schema更加复杂。
由于 data is a tree。view template 定义也要是一棵树。
比如，前3层按照Portal的方式，行列嵌套，下面3层按照wiki tree方式来显示，最多只能显示6层数据，每层数据最多显示前10条。等定义。
程序会提供很多 default view, 比如 blog, forum, wiki, cms, news, portal. etc.
用户也可以自己随意组织view。
哦,我的表达有点问题,其实我的意思是现在的结构怎么判断树节点与叶子节点呢? 13 楼 sorphi 2006-08-11 俺倒是很关心如何建模一个高效的树形结构（排除特定数据库提供的递归sql）。 14 楼 buaawhl 2006-08-11 讨论深入化了，多谢大家的讨论和思考。
庄表伟给我发了一个信息，他以前的opengis的设计。
http://cosoft.org.cn/docman/display_doc.php?docid=4839&group_id=5092
http://cosoft.org.cn/docman/display_doc.php?docid=4840&group_id=5092
他关于权限方面，考虑的比较全面。
我下面先说一下关于view部分的处理。
首先，数据结构本身是一个无限深度的tree，并不区分叶子还是树，都一视同仁。
但是，view需要显示这个tree，需要定义一个深度限制，还要定义每一层显示的最多的Node个数。
具体显示成哪个view，是需要和template相联系。
系统提供了多种tempate，这些template之间能够同样连接成tree结构。和数据tree进行匹配。
data tree + template tree = result
data tree 和 template tree 之间的关系，由view定义。这部分的db schema 非常复杂难懂，而且很散，因为需要配置太多的信息，就不列出来了。
大致就是 view, view def, show, show def, .... 等等。很多表示template 的组织关系。
下面讲述性能问题。采用的选取策略都类似于是 hibernate 的 lazy batch load。
从理论上来说，view 需要显示data tree 多少层，就需要查询多少次数据库，一次都不能少。那种庞大的join，这里是不敢使用的。
比如，6 层数据，就需要查询数据库6次。这已经是最优化的结果，无法再提升了。
display order 能够很大程度上缓解分页的性能问题。因为再也不需要 order by + range ( start, max).
而且，输出data tree + template tree = result的过程也在mvc层进行了优化，不需要先把所有数据都放入到内存，再一次写出。而是可以类似于open session in view那样，每个node + tempate 输出。这样可以节省内存。
但是，最终的性能还是需要依靠 Cache + 静态发布解决。
正在做一个粒度控制很细的cache。domplus, fastm对于静态发布支持的很好，可以反复处理同一个template。
静态发布的页面，一般只有用户的登陆信息部分等小块内容需要变化，这小块动态部分使用ajax来解决。
权限部分，我还没有做到那里，大致是一个和view 类似的并行role结构。这部分我一般会采取粗粒度的控制方法，否则性能问题无法解决。我还要好好研究庄表伟的设计方案。
我采取的数据结构，属于极端抽象。原因是我不想重复做已经存在的东西，但是自己又想不出来，于是采用这种结构，提供这种自由组织的功能，可以让用户来自己组织一些创新的东西。
