How to retrieve all item's childs? Recursion? Tricky SQL query?

Question

Items are organized in folder/tree-like structure via parent_id attribute. So it is possible to create the following hierarchies:

The problem is - I can not think of an elegant way to retrieve all subitems tree for an Item. One solution is to use recursion. My recursive solution (recursive_subitems method) does not work currently. But even if it will work - I am interested if there are any other alternatives to recursion? Maybe some tricky SQL query?

# == Schema Information
#
# Table name: items
#
#  id               :integer          not null, primary key
#  name             :string
#  parent_id        :integer

class Item < ActiveRecord::Base

  # for item with ID 1 must return items with IDs [2, 3]
  def immediate_subitems 
    Item.where(parent_id: self.id)
  end

  # My failing attempt to create a recursive function...
  def recursive_subitems(parent_id)        
    items_ids = Item.where(parent_id: parent_id).map(&:id)
    items_ids.each do |item_id|
        recursive_subitems(item_id)
    end
    items_ids
  end

  # for item with ID 1 must return items 
  # with IDs [2,3,4,5,6,7,8,9,10,11]
  def all_subitems_tree
    recursive_subitems(self.id)
  end
end

Answer 1

Here's working recursive method:

def recursive_subitems(parent_id)
    # byebug
    result = []
    items_ids = Item.where(parent_id: parent_id).map(&:id)
    return [parent_id] if items_ids.empty?

    items_ids.each do |item_id|
        result << recursive_subitems(item_id)
    end
    result << parent_id
end

def all_subitems_tree
    puts "subitems tree for #{self.id}"
    ids = recursive_subitems(self.id).flatten
    ids.pop
    Item.find(ids)
end

Answer 2

There is a simple gem called ActsAsTree. It was a part of Rails in the past

It has a few simplifiers including method .walk_tree, which does what @yaru proposed

But there are plenty of other more effective ways of dealing with hierarchical data in relational database described in this detailed post

Answer 3

There are two main patterns for effective representation of tree structures in RDMS: materialized path and nested set.

https://github.com/stefankroes/ancestry and https://github.com/ClosureTree/closure_tree both implement materialized path albeit differently. Read this great article on their relative merits - https://www.hilman.io/blog/2015/09/comparing-ancestry-and-closure_tree/

https://github.com/collectiveidea/awesome_nested_set implements nested set pattern.

The basic idea of a materialized path pattern is that each element also includes a full path to itself from the root node. Ancestry does this by adding a textual ancestry column that includes this path like this: 10/34/78/.... Finding all children of the node then reduced to a simple and efficient indexed prefixed string search (where ancestry like 'id1/id2/%).

Closure Tree keeps it in a separate table, but also make this search very efficient.

The basic idea of a nested set is that in addition to parent_id it has left and right boundaries whose values are kept so that all children ids are between them. In this case, finding them becomes a simple where id between left and right.

All three implementations allow you to reduce n+1 in most read operation. Write operations (add, change, delete, move nodes) have different costs, so make sure to check them out if you plan to update your tree often.