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

Insub · 2017年01月18日 · 最后由 mizuhashi 回复于 2017年04月16日 · 2668 次阅读

先说下需求

四个模型: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 可用么?

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

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

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

awesome_nested_set

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

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

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

用 ancestry 的路过,很好用

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

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

awesome nest set 是最差的。

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

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

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

早上本来想回的,访问 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/

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

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

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

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

@gonglexin glexin

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

无论 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 了

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

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

@saiga 感谢

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

#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。

@gonglexin

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

我好好学习一下,谢谢!

novtopro 回复

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

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