Rails 如何实现一个层级有限的,支持精确插入 / 修改的树形目录?

Insub · 发布于 2017年1月18日 · 最后由 mizuhashi 回复于 2017年4月16日 · 832 次阅读
96

先说下需求

四个模型:Project / Folder / Article / Report

需要实现类似这样的一个MENU:

Project_id1

  • Folder_id1
    • ---- Article_id3
    • ---- Report_id1
    • ---- Article_id1
  • Folder_id3
    • ---- Report_id3
  • Report_id2
  • Article_id4

说明:

  • Folder / Article / Report 肯定属于某一个Project,层级简单,最多只有三层,Project -> Folder -> Article / Report

然后需要:

  • 可以移动某一个node插入到tree中特定的一个位置,比如将Report_id3插入到Article_id3和Report_id1之间....
  • 移动某个Folder的时候,子级的 Article / Report 全部跟随移动
  • 某一个Project下只会有100个子级左右,但Project数是无限的,所以性能上需要能够支持大概百万级的数据
  • 最好是2到3次SQL就可以查询/插入/修改 节点.......

Rails项目,SQL数据库,看了几个相关的GEM,貌似都不能覆盖需求: awesome_nested_set / ancestry / closure_tree / acts_as_list / acts_as_tree

想请教一下,比较合理的实现应该是怎么样?有什么GEM可用么?

共收到 22 条回复
9442

awesome_nested_set就可以,但100万级有点儿崩。

9695

都百万级了还为啥要用Rails?

20

推荐使用 closure_tree, 我们之前也有类似需求。节点用多态指向你的 Folder / Article / Report

17671

awesome_nested_set

983

如果都不符合要求,建议自己重复造一个轮子。 能具体解释一下,为啥这些gem不符合要求吗?

15915

之前做过一个类似的项目,用的jquery的插件zTree ,树形节点太多,肯定不能一次加载,异步加载

15815

#4楼 @gonglexin 其实了解了closure_tree跟其他gem的实现区别后,我依然比较喜欢ancestry和awesome_nested_set . closure_tree可能假设树形结构的层次会很深,然而一般情况下并不会那么深。再者存储那么深的树形层次感觉也很复杂 ,越复杂的实现就越难evolve http://www.hilman.io/blog/2015/09/comparing-ancestry-and-closure_tree/

26232

用ancestry的路过,很好用

8

ancestry就够了,如果是pg的话还可以在基础上优化一下,比如用ltree或array存储和索引path

这里有一个对比:https://evilmartians.com/chronicles/postgresql-and-rails-sitting-in-a-tree

awesome nest set是最差的。

15815

#10楼 @hooopo 我最喜欢看你的分享 👏

De6df3

awesome_nested_set 每次调整节点会把子级全部更新一遍

但在明显量少的场景很好用

96

早上本来想回的,访问ruby-china一直有问题 我另外开了个帖子反馈,https://ruby-china.org/topics/32167 @huacnlee

@chucai @novtopro @hooopo @huacnlee

需求描述可能有点问题,我修改了一下题目,应该是 “如何实现一个层级有限的,支持精确插入 / 修改的树形目录? ”

一开始的选择也是 ancestry ,但需求上要求能够精确插入并记录每一个节点的位置,看了下文档,貌似ancestry并不好实现,因为看文档ancestry只记录层级,并不记录position

“◾可以移动某一个node插入到tree中特定的一个位置,比如将Report_id3插入到Article_id3和Report_id1之间....”

“◾移动某个Folder的时候,子级的 Article / Report 全部跟随移动”

现在需求可以做一个妥协,就是一共最多三级,Project一定是第一级,Folder一定是第二级,然后Article和Report必须在某一Folder下,这样的话,那种方案又更合适呢? 我感觉是不是都不用使用tree的解决方案,使用一个sort相关的方案就可以了...

另外,我设想的“百万级”数据是这样的:一万个Project,每个Project下有100个节点,然后每个Project之间互无关联,这样的话,awesome_nested_set 的性能还会有问题不?

找资料的时候找到一个挺好的几种递归数据方案的对比文章,推荐一下给其它有需要的同学 http://www.gmarik.info/blog/2012/recursive-data-structures-with-rails/

另外....这个编辑器的换行必须是一个段落么?不能挨着换行?

96

我现在初步构想是两个方案:

A. 是建一个多态的MENU类,PROJECT,FOLDER,ARTICLE,REPORT都关联这个MENU类,然后用awesome_nested_set

B. 是在PROJECT加一个MENU字段,存一个树形结构的FOLDER,ARTICLE,REPORT的JSON结构,每次前端修改之后,由前端将整个MENU的JSON结构发给后台存起来

96

@gonglexin glexin

可否简单介绍一下你的方案? 能实现精确插入么?

4375

无论projectX是否有关系,在 awesome_nested_set 眼里就是一颗二叉树,只要增加一个节点都会触发两段sql:

update tree set lft=lft+2 where lft>n
update tree set rgt=rgt+2 where rgt>n

所以,即使你在 project1 里面加一个 article,后面无限多个 projectX,folderX... 都需要 update,这个gem只适用于极少改动的小规模数据表,数据一多就GG了

96

@saiga project和project之间是独立的,不过你说的意思我明白了,意思是,假设这个project下面有100个node,然后如果我将第10个node移到了第1位,那么会触发将近100条SQL查询?

4375

#17楼 @Insub 你可以参考一下这篇 文章,不过我不建议你在这个gem上面浪费时间了。。

96

@saiga 感谢

但问题是现在不用awesome_nested_set的话,其它GEM无法实现“移动或插入某节点到精确位置”这个需求,这个需求也没法砍,纠结

20

#15楼 @Insub 我们之前的做法是增加了一个 position 字段,每次插入新的节点或者移动位置的时候都会计算出一个合理的 position 出来。以下代码仅供参考:

module Positionable
  extend ActiveSupport::Concern

  DEFAULT_POSITION = 65536
  DEFAULT_POSITION_STEP = 128

  included do
    def update_position(params)
      if params[:parent_id].present? && params[:parent_type].present?
        return init_position
      end
      if params[:previous_id].present? && params[:previous_type].present?
        return reposition(params[:previous_id], params[:previous_type])
      end
    end

    def init_position
      a = sibling_activities.minimum(:position)
      b = sibling_wbs_elements.minimum(:position)

      min_position = [a, b].compact.min
      position = min_position ? min_position/2 : DEFAULT_POSITION

      update(position: position)
    end

    def reposition(previous_id, previous_type)
      previous_position =
        case previous_type
        when WbsElement::TYPE
          WbsElement.find(previous_id).position
        when Activity::TYPE
          Activity.find(previous_id).position
        end

      update(position: new_position(previous_position)) if previous_position.present?
    end

    def new_position(position)
      wbs_element_positions = sibling_wbs_elements.pluck(:position)
      activity_positions = sibling_activities.pluck(:position)

      positions = wbs_element_positions.concat(activity_positions).sort
      next_position = positions.bsearch { |p| p > position }

      next_position ? (position + next_position)/2 : position + DEFAULT_POSITION_STEP
    end
  end

end

因为我们当初实现这颗树的时候挂的是两种不同类型的 model, 所以代码优点复杂,实际上使用多态用一种 model 来表示你的节点( Project, Folder, Article) 会要简单很多。 另外,单纯的往树上特定位置增加节点,这些 gem 都很方便吧。我们之所以要计算 position 是因为这个树会需要频繁调整,任意一个节点和子节点都可以调整到任意位置,同时又有严格的顺序要求。closure_tree 的好处是树形关系是由 gem 维护在另外的表中。移动位置不会造成大量 SQL。

96

@gonglexin

我们的需求正好跟你们是一样的,Project下挂的Article和Report,Folder实际上是一个用户自定义的menu目录,用户完全有可能频繁调整,而且“任意一个节点和子节点都可以调整到任意位置,同时又有严格的顺序要求”

我好好学习一下,谢谢!

23529
15815novtopro 回复

ancestry不能includes和eager_load,会多很多n+1查询的。。closure_tree可以把grandparent之类的实现成真正的关联,用起来方便很多

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册