商品无限分类的算法如何优化?

    现在做一个系统,里面涉及到了信息的无限分类,以前也做过(一次数据库取出所有记录返回一个list 递归循环调用list来分组显示所有信息的归属关系),于是就拿过来用,后来发现信息显示页面超慢,有时要等上几分钟还不能完全显示,问题来了,客户不满意,在这里想请教下大家,有没更好的实现方法,下面是我的数据表结构:

类别表: type
字段:     id          标识(自动增长)
         code       分类级别
           typename    分类名称

(code表示方法:
一级目录 : 1,
一级目录第一个子栏目: 1_1,
一级目录第二个子栏目: 1_2,
一级目录第一个子栏目的第一个栏目: 1_1_1,
以此类推...)

信息表: msg
字段:  id
       typeid       类别ID(对应type表id)
       title       标题
       messge      内容

评论

30 楼 playfish 2008-03-19  

tree的一次性load指的是数据结构,不是生成整棵树..后台程序通过java或者php生成javascript的数组,也就是准备好了所有的数据而已.不会调用js方法.js方法会在dom ready后执行,第一次只生成一级节点,不会有cpu消耗的问题的

29 楼 pig345 2008-03-19  

playfish 写道

* 数据一次性加载 ... 但是它的缺点也是非常多的：设计模式比数据一次性加载要复杂得多，要考虑到 Browser/Server 之间的应答，要判断子节点是否含有孙节点，后台数据源的层级关系模型等。对网络传输的信赖性太大，每个节点的展开都需要连一次 Server，只要在取某节点数据时网络出现问题，就会导致该节点及其以下的子节点加载失败。而采取数据一次加载的模式只要一次加载成功，服务器就可以不用管它了，服务器压力减轻，脚本设计则完全独立，对整棵树节点的检索可以在客户端完成，节点展开响应速度快等等优势，

不知道为什么，我的看法正好完全相反，呵呵。

首先这个接口的实现似乎并不困难，反倒使程序结构（从接口到逻辑都）更加简洁，
因为（相对于一次全Load的方案）他把递归（或循环）的责任完全放到了程序外部（由用户手工的点击）实现。

第二个担心网络的问题，似否有点过分忧虑了？一次加载不成功，用户完全可以再试。。。
如果网络真的有问题，你怎么能保证在一个大数据量的传输过程中，不会出错呢？如果传了一半断掉了（数据已经不完整）岂不更难处理？？？ 而分成多次少量数据传输的话，失败的可能性只会减少，且程序受影响也小很多。

最后，关于server的压力问题，不针对具体情况，没法说哪个方法是绝对优秀，想象这个情况：
大多数情况下，用户只是会进入自己关心的那个叶子节点，此时，如果分步按需传输的话，服务器几次下来的数据运算量之和，肯定远远小于一次性全部load的运算量；在tree不能有效缓存的情况下（比如经常发生变化）一次性全部load可能会造成单cpu100％几秒种，而分步按需则不会。
哪个更省，恐怕必须实际测试才能知道。

28 楼 huangyh 2008-03-19  

mztree的方式我清楚，数据量太大了，还是有问题，毕竟他是一次性把所有节点信息给弄出来。

27 楼 playfish 2008-03-19  

huangyh 写道

原理很简单，分层装载节点。
第一次展开节点时，发送ajax请求到后台获取当前节点的子节点数据，使用js构造出儿子节点。因为每次都只展开一层（兄弟节点的个数不可能非常大,所以不会存在什么性能问题)

mztree的原理不是这个样子的。。。他没有通过ajax，我之前有提到，它是一次性加载，也就是将所有信息都取出来，但是仅仅是节点的信息，不是html。这里引用一下作者自己的描述

引用：http://www.meizz.com/Web/Web.asp
设计模式
    为了达到能够在浏览器中快速打开多节点树的页面，我做了很多的优化与创新，下面我将详细解说几项最重要的部分：

        * 数据一次性加载 首先我要说的就是数据的一次性加载。在目前的 B/S 架构开发中对于多节点多层次的树，特别是树节点量超过两千的情况下，几乎都是采取数据异步加载来达到目的，即用户需要展开某个节点时，再从服务器端加载下级子节点的数据，数据异步加载最为经典的例子就是 MSDN 网站左边的目录树了。异步加载的优点在于可以扩充到无限级无限节点树，树的数据来源可以多样化（数据库或XML文件）等，但是它的缺点也是非常多的：设计模式比数据一次性加载要复杂得多，要考虑到 Browser/Server 之间的应答，要判断子节点是否含有孙节点，后台数据源的层级关系模型等。对网络传输的信赖性太大，每个节点的展开都需要连一次 Server，只要在取某节点数据时网络出现问题，就会导致该节点及其以下的子节点加载失败。而采取数据一次加载的模式只要一次加载成功，服务器就可以不用管它了，服务器压力减轻，脚本设计则完全独立，对整棵树节点的检索可以在客户端完成，节点展开响应速度快等等优势，因此在节点数不多的情况下数据一次性加载更有优势，那么这个节点数不多不多到底多少节点量为平衡点呢？就 ASP.net 里带的那个 TreeView 来说，在一两千节点以下一次性加载比较具有优势，而　MzTreeView 1.0 在节点量三万至五万以非常具有优势。

        * 节点信息的压缩传输 在浏览器里显示的树结构其实都是一个个 HTML 元素组合起来的，在 WEB 页面里的树都是根据树节点的信息组合成一串的 HTML 元素列来显示，这一步从节点信息到 HTML 的转化可以在两个地方生成：一个是在服务器端，一个是在客户端。在服务器端生成的优点在于不须考虑客户端的浏览器的兼容性，节点信息的可控性非常强，但是它的缺点也是非常大的：加重服务器的负担，增加网络传输量。在服务器端直接生成树节点的 HTML 给服务器带来的压力是显而易见的，也是非常巨大的，估计只要有几十个并发连接就能让服务器暂时停止响应了。这种直接在服务器生成树的做法在实际运用环境中也有人使用，不过本人非常不赞成这种做法。当然也有人直接将树生成为一个静态文件放在服务器端，这种做法对于树节点相对固定不变的情况还是非常有利的，只需要生成一次，以后就不需要再生成了，服务器的压力也非常小，但它的弊病在于可变化性太小，比如说不同的权限能看到的树节点的不同这种情况，用这种生成静态树放在服务器端的做就没有办法解决，且不管是服务器端动态计算还是直接生成静态树文件放在服务器端都有一个避免不了的问题就是网络传输量巨大。可以计算一下，一个树点所需要的HTML字符量大约300到600字节之间。即含有一千节点的树的网页大小就有300K到600K，给网络造成的压力是非常巨大的，所以MzTreeView 1.0采用了节点信息的压缩传输，大至一千节点的总传输量在30K左右，这可以差了一个数量级呀。本树将每个节点所必要的信息组合成一个字符串序列，传递到客户端，然后在客户端再用客户端脚本对这些信息进行分析，再生成一个个的节点HTML，这也符合了WEB的分散计算的原理，当然服务器端可以有选择性输出部分节点，这样又做到节点的灵活多变性。

        * 传输的节点信息的可扩展性 服务器端将节点的必要信息组合成一个字符串序列传递到客户端，然后客户端再用脚本对这个字符串序列进行分析，生成树的节点，那么这个字符串序列对整个树的生成的效率就有重要的影响了。我也参照过很多组串传输的例子，在一般的做法当中大多采用函数的参数方式传递。比如说定义一个函数 funName(p1, p2, p3, ...)，然后服务器组串的时候就按位置给定数据。这种组串的弊病是非常大的，首先就是位置绝对错不得，只要有一个位置数据出错，这个节点的信息就乱了，对于那些在函数里已经定义的但节点里没有的信息也得用空字符串补上，诸如：(p1, "", p3, p4, "", "", "")，且万一这种组串的对应分析函数发生了变化，那么这种串就算是废了，得重新定义服务器端的字符串位置序列了，可以说这种组串的方式可扩展性极差。
              节点信息组串传输的另一种常用模式就是XML。XML以它的无限可扩展性已惭有代替HTML称霸WEB的味道了。XML最大的优点就在于它的无限可扩展性，可以用任意的TagName名，可以有任意的Attribute名，节点与子节点已经有层级的关系，用XML来做WEB树的数据源其实是最理想的， MSDN的资源目录树就是采用XML作为传递的字符串，它唯一的不足之处就是不是所有浏览器都能很好地支持它，特别是在一些低版本的浏览器中，所以我只好忍痛割爱没有启用XML作为中间的传媒。那么是不是有可能结合XML的扩展性对第一种组串的方式进行改进呢？当我愁眉不展的时候，HTML里的STYLE 样式表写法跳入我眼，样式的写法是"param1: value1; param2: value3; ..."，哈哈，这不是现成地给我指明了路吗？这种写法拥有XML的可扩展性，位置顺序的随意性，又是传统的长字符串，正合我意也！服务器给定这种数据源字符串，我不光可以在TreeView里用它，还可以直接做Outlook Bar，下拉式层级菜单，右键层级菜单的数据源，豁然开朗也！我写了一个函数专门解析这种文本：getAttribute()。

        * 客户端节点数据的存储方式及快速检索 现在数据源准备好了，数据传输也已做到最大优化了，下面就是客户端的脚本解析了，而这一步也正是树生成的效率瓶颈所在。由于我没有采用XML做为数据源，所以我这里就不讨论XML+XSL和XMLDOM的模式，而只考虑HTML+DOM模式了。在HTML+DOM模式下客户端存储的方式有很多种，我就曾经看到过一种直接将字符串输出在多行文本框<textarea>里的，但归究起来最常用的方式就是用一个数组来存放节点信息，不过就算是用数组也是种类多多，比如说数组里套数组，节点通过记录父节点在数组里的索引号表示层级的等等，说到数组存放树节点模式，我推荐阿信写的那棵树。在服务器端组织好脚本及节点字符串，客户端浏览器加载这个页面的时候顺序执行其里面的脚本，将一个个节点做最初步的解析，然后再一个个地ADD到数组中去。这种流程看起来似乎没有什么问题，在很多的传统C/S结构编程中也就这种模式，但是随着节点数的增多，这种流程在B/S里的缺点就出现了：脚本的执行效率不如强语言高！我做过测试，在5000节点的数据量时这一步操作将耗时１秒钟，也许你认为这１秒钟不算长，哪里有5000这么多节点的树？但对于一个程序员来说，严谨是第一位的，若存在优化的可能性，情况出现的可能性，我们就得将它考虑到。那么有没有可能再进一步优化呢？当然有，否则我就用不着这么大费口舌在这里讲了。既然在脚本里执行 for 循环插入数组效率不高那我不用循环，且考虑到在数组里这么多节点中搜索我想要的某几个节点，还得用循环，所以我干脆就不再用数组来存放树节点了，那用什么呢？说到这里我得插几句题外话，客户端脚本也可以写一些类，虽说写出来的类没有强语言那么好，继承性不好等，但脚本终究还是可以写出一些简单的类的。类可以定义属性，也可以定义方法，并且访问属性的时候可以通过属性名下标直接访问到属性值，关于脚本里如何写类，大家可以参考我在JavaScript和 VBScript里对这方面的详细说明。呵呵，说了这么多的题外话，不过相信大家也猜到了，新的节点存储方式就是类的属性自定义扩展方式。这种存储方式随着页面的打开，页面里的脚本被执行，类的属性值不需要做任何添加的动作就直接写到内存当中，比数组模式少去了ADD操作，这一步从字符串到内存的时间就是页面打开的时间，我测试了一下，5000节点的树用这种方式打开，只需0.1秒呀，与数组模式速度整整差了一个数量级呀！且这种模式还有一种好处，在几千个节点里要找到目标节点，只需要知道节点对应的属性名，一步就可以直接找到。
              客户端树节点存储模式说清楚了，那节点的快速检索也就清楚了。已知节点名即在类里的属性名的话，一步就找到了该节点，不过为了配合下一节的异步展示，我的检索就没有这么简单了。试想在几千或者几万个节点里要快速地找出符合条件的几十个节点，这一步的耗时可想而知了，首先就得排除for循环法，for循环的效率在数组模式里大家就看到了，这一步操作特别在总节点数多的情况下就能让使用者等疯掉，显然得另想办法。于是我想到了正则表达式里的字符串模式匹配match()，我将所有的节点名（即类的属性名）join()成一个大字符串，然后再用正则表达式匹配，一步就找出了想要的节点了。经测试，在三万节点里找30个节点对象耗时小于0.1秒！

        * 异步展示 再来讲一下节点字符串被解析之后转化成HTML元素的这一步操作。上面已经有过一个计算，表达1000节点的树的HTML字符量就有300K-600K之多，且这一步只能一个节点一个节点慢慢地生成，没有什么取巧的办法，想快点也只能是减小单个节点的HTML元素量罢，不过最快也得1-3秒每千节点呀，这也是没有法子的事，谁叫DOM的效率不高呢！总得想个什么法子吧，否则象5000节点量的树让使用者等上个半分钟一分钟的，谁也受不了呀！因此我想出异步展示这招：页面加载时并不立即生成所有节点的HTML元素，而是用户展开多少节点就生成多少节点，节点的生成发生在用户展开这个节点的时候。使用者在页面打开的时候并不会立即把所有的节点都一次全部展开，而是一级级地往下展开的，就象你查看windows注册表一样，想看哪级才会去展开哪一级，这样我就只需要在你展开那级的时候把这一级的节点转化成HTML即可，每次转化的节点只有几十分甚至只有几个而已，消除了使用者的等待时间。经过上面这几个环节，终于一棵实用性，效率，扩展性俱佳的WEB TreeView出世了。

        * 采用文字竖线 每个浏览器随着使用客户的不同，而总会产生不同的设置，其中有一项就是客户端设置每次访问都检查网页新版本，即客户端不缓存。这个设置对一般的应用来说问题不会很大，但是对于使用图片作为竖线的树来说随着节点总数的增多，图片的使用量也就跟着巨量增加，可能会使用几千甚至几万个小图片，每张图片是都很小，但量一大的话，将会严重影响树的快速展示，因此针对这种情况就得换一种模式来展现了，那就是文字竖线，用文字加样式就可以解决这个问题。我加了一个变量： MzTreeView.wordLine（布尔型，默认值为false），当网速过慢或者没有使用本地缓存时这个属性会自动设置成 true 而以文字代替图片完成竖线（注：Opera 浏览器不支持文字竖线模式），当然你也可以一开始就强行设置值为 true，这样树就会始终用文字竖线了。

26 楼 huangyh 2008-03-19  

原理很简单，分层装载节点。
第一次展开节点时，发送ajax请求到后台获取当前节点的子节点数据，使用js构造出儿子节点。因为每次都只展开一层（兄弟节点的个数不可能非常大,所以不会存在什么性能问题)

25 楼 javanewlife 2008-03-18  

huangyh 写道

强烈推荐用E3.Tree，可以分层显示，使用非常简单. 下载： http://ie3.googlecode.com/

没用过,下了个MZTREE,能简单介绍下它的实现原理吗?

24 楼 huangyh 2008-03-18  

强烈推荐用E3.Tree，可以分层显示，使用非常简单. 下载： http://ie3.googlecode.com/

23 楼 playfish 2008-03-17  

Lucas Lee 写道

我碰巧也做过同样的东西。
树里共100－200节点；
第一次，用递归查询数据，就是每个节点一个SQL，>2分钟；
第二次，用一个SQL查出所有纪录，用java在内存里按数据关系整理出树形结构，<10秒。
（具体数字记得不是很清楚，仅供参考）

关于树。。刚好前段时间也做过一个树组件的优化，大概思路也是这样的。主要还是参考mztree的一些设计概念，mztree你可以搜索一下。
具体数据结构还是id,parentid是关键。
用java将所有纪录生成javascript的数组，一次性加载。
首次只生成1级节点，点击的时候调用javascript函数方法，js将纪录数组组装成html语句，添加到这个节点下面。也就是异步加载子节点。
重点是：服务器端只生成记录数组，而不是html语句。客户端通过js将数据结构封装成html。
测试在500个节点情况下原本要8秒，后来改成这种方法，500个节点加载完成到显示小于3秒。全部展开小于3秒。另外，节点数多的情况下还要考虑做一些优化。主要是IE的执行效率低，字符串拼接上做点优化

22 楼 wondery 2008-03-15  

前些时间做了个树，有不少于600个节点，放到了Map里，速度虽说不快但能正常用。

21 楼 pickerel 2008-03-15  

dualface 写道

汗。。。。。。。。。。。。。。

用下面的表结构：

id
parent_id
left_value
right_value
name

一条语句就可以读取任意节点到根的完整路径

那我列出所有指定目录下的所有子目录，子子目录呢？现在很多应用目录都是异步加载的，用这种方法要实现点击某个目录，其下的所有子目录，子子目录全部打开还是效率不高吧。

一般数数据量不是超级大，全部载入内存中并缓存之处理比较方便，如果一定要从数据库上来使这个问题更方便解决,
我建议建一个路径字段，这样抽出任何一个记录都会找出他所有的上级目录信息，也能在用一个请求在数据库中找出他的所有下级，下下级信息。

目录表
id   name     parent_id       path        order
1             0              
2             1               1           0
3             1               1           1
4             2               1,2         0 
5             2               1,2         1
6             3               1,3         0
7             5               1,2,5       0

当然由于这个path是个字符串，所以在某些数据库索引方面可能有效率问题，特别是无限级可能要用blob或者text字段了。

20 楼 dualface 2008-03-14  

汗。。。。。。。。。。。。。。

用下面的表结构：

id
parent_id
left_value
right_value
name

一条语句就可以读取任意节点到根的完整路径

19 楼 laiseeme 2008-03-14  

id
name
parentid
isLeaf(是否是叶子)
不用递归,点击节点时加载子节点

18 楼 zrwlc2008 2008-03-14  

qianlei007 写道

关于这样的树加载， 都是一级一级加载。效率高点把。。。
    一次递归，数据量大的话，基本要死掉。。

对,如果不要求大大小小一下全部摆出来, 就可以先显示最大的类 , 然后客户选择哪个大类再去取再动态加入,
这时候ajax最好用了.

17 楼 lsk 2008-03-14  

我们项目的做法是利用XML.
如下:

<RECORD>
	<id>10010</id>
	<parent>0</parent>
	<name>试剂</name>
	<pos>1</pos>
	<level>1</level>
</RECORD>

level为等级.1是父级. id是有规则的一组int数字.比如 100 ,100100 ,100102
针对XML写一个实体Bean,在容器启动的时候加载到内存中..不需要数据库处理.在要的产品类别当中就一个type字段.
可以无限级分类.

16 楼 williamy 2008-03-14  

表结构为:
int id   //id
int parentid  //父菜单的id  顶级为null  或者0
int level  //级别
char name//名字

开始 找出max level

1st，找出level为0的，就是顶级的

2，找出level为1的，根据parentid组装到树上去

3，找出level为2的。。。。。

4。找出level为3的 。。。。

5。找出level为4的 。。。。

6。找出level为5的 。。。。

7。找出level为6的 。。。。

继续 因为忘记判断level大小了

15 楼 ak_2005 2008-03-14  

晕，居然重复提交了。
多级分类的设计。。。

14 楼 ak_2005 2008-03-14  

表设计的问题，搞这么复杂。。。
现在的设计，统计够呛的。

13 楼 抛出异常的爱 2008-03-14  

Lucas Lee 写道

我碰巧也做过同样的东西。
树里共100－200节点；
第一次，用递归查询数据，就是每个节点一个SQL，>2分钟；
第二次，用一个SQL查出所有纪录，用java在内存里按数据关系整理出树形结构，<10秒。
（具体数字记得不是很清楚，仅供参考）

放在静态map中

12 楼 pig345 2008-03-14  

tree的显示，一般的都是由用户的点击触发下级菜单的显示，没见过一次性load整棵tree的。。。

另外：因为是无限级的tree，所以一般不在id上体现tree关系（id再长也是有限级的），而是使用自关联（表中添加 id, parent_id 字段）；
这时，如果是要判定某个node是否属于某个tree（常用于权限范围等的判定），db2/oracle/sqlserver都有相关的SQL扩展，可以一条sql做到。
postgresql/mysql（高版本）虽然没有直接支持，但是可以自己写个存储过程在数据库里面递归实现，效率也要比load出来再判定高很多。

11 楼 aninfeel 2008-03-14  

在服务器启动时全部加载到一个全局变量里，要是后台对分类有所修改的话也随便改改这个变量。