邻接数据结构转嵌套哈希表

Question

我在 rails 中有以下模型:

class Model < ActiveRecord::Base
  # id — integer
  # name — string
  # model_id — integer

  belongs_to :parent, class_name: 'Model', foreign_key: 'model_id'
  has_many :children, class_name: 'Model', foreign_key: 'model_id'
end

我正在使用邻接结构，它可以具有无限的深度。我正在使用递归查询在Postgres数据库上。

获取嵌套对象哈希表的最合理方法是什么？我尝试选择Model的实例并对它们进行排序，但无法得到任何可用的结果。

假设我在数据库中保存了四个Model实例：Model_1、Model_2、Model_3和Model_4。 Model_3是Model_2的子代，而Model_4是Model_3的子代。

这是我正在尝试实现的输出（Model实例的嵌套哈希表）：

{
  #<Model_1...> => {},
  #<Model_2...> => {
    #<Model_3...> => {
      #<Model_4...> => {}
    }
  }
}

有什么想法吗？

更新：树已经恢复——作为CollectionProxy、Relation或任何其他类似数组的数据结构。我想将该树排序成嵌套哈希的哈希表。

- Ruslan

---

使用祖先宝石，可以避免一些麻烦。 - Damien Roche

在这种情况下，MPP不是一个选择 - 我需要廉价的读/写并具有无限深度（因此闭包表和嵌套树也不是一个选择）。 - Ruslan

你想做什么？以尽可能少的查询次数恢复一个元素树吗？每次加载父级时，你会使用所有子项吗，还是使用延迟加载更好？ - Alex Siri

假设树已经被恢复了，无论是作为CollectionProxy、Relation还是任何其他类似数组的数据结构。我想将该树排序成嵌套哈希的哈希结构。 - Ruslan

你使用的是哪个数据库？ - Kombajn zbożowy

Answer 1

我会将其命名为parent_id字段。

  belongs_to :parent, class_name: "Model"
  has_many :children, class_name: "Model", foreign_key: "parent_id"

当您拥有哈希值时，您将使用sort或sort_by:

http://www.ruby-doc.org/core-2.1.0/Enumerable.html#method-i-sort_by

def sort(hash)
  hash.sort { |m1, m2| m1.id <=> m2.id }
  sort(hash.children)
end

- Chloe

---

树（已被展平）被恢复为类似于数组（或枚举）的数据结构 - 即 [#<Model_1...>, #<Model_2...>]。我无法直接调用其上的 children 方法；为了做到这一点，我首先需要将其排序为嵌套结构；这也是我一开始的目标。此外，排序只会对数组/枚举中的对象进行排序，但我需要将它们嵌套。 - Ruslan

Answer 2

首先，在您的模型类中定义ff方法：

def to_hash
  if children.empty?
    {self => {}}
  else
    {self => children.inject({}) {|hash, model| hash.merge(model.to_hash) } }
  end
end

然后按照以下步骤获取您想要的输出：

top_level_models = #code that queries top-level models while eager-loading all nested children
hash_of_nested_models = top_level_models.inject({}) {|hash, ancestor| hash.merge(ancestor.to_hash) }

你传递给 includes 的哈希参数应该覆盖嵌套的深度。上面传递给 includes 的参数将是具有 3 个后代深度的子级的嵌套。只要在你的 where 查询中包含所有嵌套的子级，生成哈希就不会执行任何其他的数据库查询。

希望这能帮到你！

- Gjaldon

---

谢谢您的回复。它有效，但会产生N+1个查询；再加上树可能具有无限深度的事实，它很快就会成为瓶颈。 - Ruslan

你没有指定这个要求，所以我只是想出了一个可行的解决方案。也许可以使用 includes？ - Gjaldon

Rails不支持递归查询；这样includes将产生M+1个查询，其中M是树的层数。我认为保持在一个查询中的唯一方法是首先选择整个树，在我的情况下这不是问题，然后开始将其排序成嵌套哈希。 - Ruslan

我刚刚对上面的代码进行了更改，以便哈希构建代码不会再进行任何数据库查询。 - Gjaldon

谢谢您的回答，但不幸的是，正如问题本身所述，树可以具有无限深度；因此，在这种情况下，3个后代是不够的。 - Ruslan

Answer 3

在没有进行N+1查询的情况下让AR完成这个任务可能会比较困难。必须编写一些能够与内存中的数据配合工作的代码。

你需要编写一个类似于以下代码的自定义函数：

 def to_hash
  root_hash = {}
  # Load all the model into memory and into a hash to allow faster access when we have the id
  models = Hash[Model.all.collect {|m| [m.id, m]}]
  # The resultant hash for each child
  models_with_hash = Hash[map.values.collect {|m| [m.id, {}]} ]
  # Stitch them together
  models.each do |id, m| 
    if m.model_id.nil?
      root_hash.merge! m => models_with_hash[m.id]
    else
      # should name model_id to parent_id
      models_with_hash[m.model_id].merge! m => models_with_hash[m.id]
    end  
  end
  root_hash
end

- jatin