带选择框的JS树控件2 （为JSTree再次提速）

以前写过一个带选择框的JS树控件
但是当时发现一个问题，第一次选中根节点会明显感觉卡一下。
那是因为子节点的数据还没有生成，选中根节点的话需要初始化全部数据。(那个tree有5000个节点)

于是我思考一个问题，如何让多节点树的页面达到更快的效率。

经过测试发现，JSTree的主要效率瓶颈在两个地方。
1.页面HTMLElement的创建
2.树子节点的检索

页面创建一个HTMLElement是很耗时的，无论使用createElement或者是是innerHTML都一样。
而且这一步只能一个节点一个节点慢慢地生成，虽然可以通过减小单个节点的HTML元素量的方法提高一些速度，但是对于对于上千个节点来说仍然需要等上几十秒。
(1个节点如果有5个HTMLElement，生成1000个节点大概3秒左右)

所以只有通过异步展示的方法来进一步减少一次生成的节点数。
页面加载时并不立即生成所有节点的HTML元素，而是用户展开多少节点就生成多少节点，节点的生成发生在用户展开这个节点的时候。 这样减少了每次生成的节点数，消除了使用者的等待时间。

而对于节点的检索，这和数据的组织方式有关。
一般的组织方式是使用数组。(解析XML的话太慢，不考虑。只考虑使用json的情况)
但是在数组中检索一个节点的效率实在不敢恭维，如果节点是N个，那么全部节点数据组装起来的效率就是N*N
在节点少的时候不明显，但是如果有1000个节点，那么明显会发觉延迟了10多秒。延迟速度按指数增加。

MzTree(梅花雪)使用了另外一种方式，他没有使用数组而是使用一个简单对象来存放数组。
并且用一个字符串存放节点的索引关系（将所有的节点名（即类的属性名）join()成一个大字符串）
当需要获得子节点的时候使用正则匹配一步获得子节点ID，从而获得子节点。
经过测试发现，使用正则匹配的算法检索节点效率比使用for循环要高出很多。

这个效率已经满足一般大数据jstree的需要。
(具体算法，去参考MzTree梅花雪)



对于一般的Tree可以通过异步初始化节点数据(不是初始化节点HTML)的方法来解决延迟。
但是如果是checkbox-tree(带选择框的树)，却不能使用这个方法。因为对于带选择框的JS树，选中根节点的话，子节点应给也被选中。所以选中根节点，子节点必须存在。 所以节点数据需要一次生成。

但问题是即使使用正则匹配的算法提高了效率，仍然会需要一段初始化的时间。
（5000个节点数据全部初始化 使用for需要20-30秒，使用正则匹配算法需要6秒）

那么有没有办法进一步提高效率呢？
按照一般Tree的做法初始化一个节点数据需要初始化这个节点的子节点数据，那么也就需要检索节点的子节点数据。(有点绕口)
这个检索子节点数据看来是比较耗费时间的，而且没有更好的提高检索效率的方法。
既然检索没有办法提速，那么有没有不使用检索获得子节点的方法呢？

答案当然是有的，只要我们更改传递过去的数据结构问题迎刃而解。

于是我们直接传递一个拼装好的树结构JSON(节点包含了子节点的数据，子节点的数据中又包含了子子节点的数据....)

数据结构如下：
{
id : 0
childrean : [
  {
   id : 01
   childrean : [
    {
     id : 011
     childrean : [...]
    },
    {
     id : 012
     childrean : [...]
    }
   ]
  }
  ,
  {
   id : 02
   childrean : []
  }
]
}

对于这种结构，页面的Tree可以直接使用而无需解析，免去了子节点的检索所耗费的时间，JsTree展示速度大大提高。
一个5000节点的树，节点数据全部初始化只需要500毫秒。

(其实还有一个优点，使用这种结构的数据JSTree容易扩充，稍作修改就可以改成支持数据异步加载的Ajax-Tree) 


 
 
PS：附件中是一个演示例子，虽然不是最终版本但是可以说明问题。

 

china_2.js 和 china_2_code.js 是节点数据(UTF-8编码)

 

 

参数说明

text        显示节点内容（必须）
id           节点id
checked 选择框选中状态 0 1 2

children 子节点数据

 

创建一个新节点的方法 new TreeNode( {} );

 

 

新建节点可能存在一些问题(单选框选中等问题)，节点有checked属性的情况才会出现选择框。

 

 

 

 

 

 

感谢winner720发现的一个BUG

这部分代码要改一下(粗体部分)  TreePanel_0.5.rar

//瀑布(遍历所有子节点)
cascade : function(fn, scope, args){
  if(fn.call(scope || this, (args==null?this:args)) !== false){
    var cs = this.childNodes;
    for(var i = 0, len = cs.length; i < len; i++) {
      cs[i].cascade(fn, scope, args);
    }
  }
},

(以前是 args||this，当节点checked是0的时候可能出现返回this，虽然不影响展示结果，但是会造成一定泄露。改成(args==null?this:args)就不会出现问题了)

 

 

modify：
TreePanel_test_0.x  测试演示版本
TreePanel_all.rar      完整演示版本
TreePanel_0.5.rar    修正了一个内存泄露BUG
TreePanel_2.2.zip    增加了节点全部展开和全部折叠的方法，修正了节点显示时多余的竖线

TreePanel_2.3.zip    修复节点删除时多余的竖线

 

备注：附件请下载最新的版本。 （旧的的版本可能存在未修改BUG，没删除只是为了留作做为备份）

 

这个树最初设计目的是快速展示一颗带选择框的静态树，虽然也提供了节点增加以及删除等功能，但这些没有经过仔细测试，且不是它的长项。

评论

31 楼 langshao 2010-05-20  

很好的控件，正是我要找的——关键是出来以及选中的速度.

有一点不明白：china_2.js中的pid，是不是多余的？

30 楼 kolenxiao 2010-04-29  

为什么我下载的版本中var node = tree.focusNode;得到的node都是null?
明白原因了，你的勾选根本没用，只有选中文本才生效

29 楼 kolenxiao 2010-04-29  

到底哪个才是最新版？越看越糊涂

28 楼 gecbzsyj 2010-04-15  

1、最上级：中国，没办法收缩，
2、htm中只能引用china_2_code.js,引用china_2.js会提示JS错误（IE6）
3、建议可以设置参数，比如：自动选择子节点（只选中国，不跟选子节点），自动选择父节点（同个父节点下的子节点全选时，不自动选择父节点）。

以上希望楼主可以完善

27 楼 sd5816690 2010-02-08  

非常好用！！

现在需要打开页面时，展开所有结点
貌似可以在页面加载完成后，调用 expandAll()
但速度太慢了，例子中，4核CPU都需要10秒左右

能不能进入页面时，就把HTML代码写好
调用一个初始化方法，让 HTML 代码和 root 里的数据对应
（HTML代码和 root 都是写好的，只需要初始化就行了）

26 楼 kenee1314 2010-02-04  

如果大数据量，活着级数比较多，能否支持？？

25 楼 kenee1314 2010-02-04  

支持分级查找么

24 楼 yemen007 2010-02-04  

这个真的很好用  ，但如果我只想选中“中国”并保持所有其子结点为空应该怎么做？

23 楼 Relucent 2010-01-29  

cuixiping 写道

1、这棵树，如果能够不用jquery更好，为了棵树多用上个jquery似乎不太喜欢。
2、

引用

但是如果是checkbox-tree(带选择框的树)，却不能使用这个方法。因为对于带选择框的JS树，选中根节点的话，子节点应给也被选中。所以选中根节点，子节点必须存在。 所以节点数据需要一次生成。

非也。为什么子节点必须存在呢？完全可以不存在！只有用户展开了这个节点的时候，才必须让子节点存在。也就是目前不用看到的，都可以不画，等需要时再绘制。

第一个问题：
好吧，我承认。那个jquery.js是多余的，因为我压根没用到。你可以放心删掉。
otree_old.htm otree_old.js 是以前写的例子，可以一并删掉。



第二个问题：
我说的是数据一次生成，一次加载。

我的节点其实分成两部分，数据模型和 界面UI。这地方我是分开处理的（虽然看起来写到了一起）。
我的节点加载时一定存在的。因为存在的节点方便我注册以及处理。
但是界面上的element并不一定存在。因为浏览器生成一个页面元素是很耗时的。所以只有再需要展示(展开显示)的时候我才会去new一个页面元素。

如上，节点（指页面Element元素）可以在展开时才绘制的，而我也是这样做的。

22 楼 cuixiping 2010-01-21  

1、这棵树，如果能够不用jquery更好，为了棵树多用上个jquery似乎不太喜欢。
2、

引用

但是如果是checkbox-tree(带选择框的树)，却不能使用这个方法。因为对于带选择框的JS树，选中根节点的话，子节点应给也被选中。所以选中根节点，子节点必须存在。 所以节点数据需要一次生成。

非也。为什么子节点必须存在呢？完全可以不存在！只有用户展开了这个节点的时候，才必须让子节点存在。也就是目前不用看到的，都可以不画，等需要时再绘制。

21 楼 Relucent 2009-12-17  

没有考虑过search，因为我开始考虑的只是如何快速展现一棵树。

但是TreePanel里面有个this.nodeHash变量，记录了节点ID和节点的映射
(一个hash)。
如果是简单的搜索可以用this.nodeHash遍历所有节点。







感谢winner720发现的一个BUG

这部分代码要改一下(粗体部分)

//瀑布(遍历所有子节点)
cascade : function(fn, scope, args){
  if(fn.call(scope || this, (args==null?this:args)) !== false){
    var cs = this.childNodes;
    for(var i = 0, len = cs.length; i < len; i++) {
      cs[i].cascade(fn, scope, args);
    }
  }
},




以前是 args||this，当节点checked是0的时候可能出现返回this的BUG，改成(args==null?this:args)就不会出现问题了。

20 楼 popsoft75 2009-12-16  

楼主的tree控件很不错，但是缺了search功能。在这方面是如何考虑的？

19 楼 Relucent 2009-11-17  

liuweifeng 写道

兄弟，最后一个附件，TreePanel_all，我解压出来运行TreePanel.html，在Chrome里探出alert是108，在FireFox里弹出提示是107，好像有点问题。

= =！

你在提出问题之前难道从不自己看代码吗？

TreePanel.html 31行 alert( (new Date().getTime()-l0));

var L = new Date().getTime();
tree = new TreePanel({
 'root' : root
});
tree.render();
alert( (new Date().getTime()-L));

那个 alert 打印的是初始化Tree花费的时间。

这只能说明不同浏览器初始化Tree的速度不一样。

说Chrome刷出这个树花了108毫秒，FireFox用了107毫秒，IE6用了815毫秒。


（PS:顺便说一下这个树大约有3525个节点。）

18 楼 liuweifeng 2009-11-14  

兄弟，最后一个附件，TreePanel_all，我解压出来运行TreePanel.html，在Chrome里探出alert是108，在FireFox里弹出提示是107，好像有点问题。

17 楼 ryanwangprc 2009-11-13  

楼主能不能提供一个终极版的 谢啦

16 楼 ycmag 2009-10-29  

兄弟，附件的链接失效了，点击编程无法访问的网页了

15 楼 萧十一狼 2009-10-25  

在后台构造那个JSON结构字符串很慢啊， 我用的是穷举遍历，每个节点一层一层遍历构造的。 你们怎么做的，怎么做才能快。  这个树确实很快，  但是后台构造那个符合条件的结构字符串很慢， 新手求解。

14 楼 cn-done 2009-10-24  

新添加的节点貌似前面没的checkbox 不支持选择哦 

13 楼 lqixv 2009-10-20  

希望能完善一下

12 楼 zhongxuchen 2009-10-16  

能不能再强化一下，提供动态树正在加载效果？（即像extjs中的树一样，从后台获取时提供一个正在loading的效果），完善一下，打算用你的树在项目中使用