To be completely honest I’ve tried this approach myself way back when, in my Erlang days. That’s why I’m confident it’s not a good approach

It’s hard to say, because the problem is vaguely described, but I think concurrent processing should be possible with a flat huge map (though can’t say if it’s worth it for your case). However, if you need to process from bottom to top, it might be better to organize the map as child to parent relationships and the list of leaves.

You also suggest that the amount of data is huge. That might lead to a large active heap, and cause some larger GC pauses in the owner process, as I briefly discussed here. If that’s the case, :digraph might be a good fit, because it’s based on ETS. Or otherwise, your hand-rolled ETS table. This might also simplify concurrent processing.

I definitely don’t advise agents (or processes). It’s going to be 2kb overhead per node (and you suggest there are a lot of them). It’s also going to involve a lot of extra message passing and scheduler overhead. With some careful work, you should be able to achieve whatever you want without agents. A large map or a nested data structure would be functional solutions, while ETS is an optimization for the cases when you have a frequently changing large active working set.

Is it a directed acyclic graph or a tree? That is, does any node ever have more than one parent? If it’s a true tree then my recommendation is to just have a big nested structure of maps, it ends up working pretty well.

If it’s actually a DAG then something like :digraph is likely to work best. Going the agent route would be a great example of something that http://theerlangelist.com/article/spawn_or_not argues against.

The way your database is set up, there is nothing preventing cycles from happening. Also, when you want to query all nodes back up the tree, or the subtree starting at a certain node, you will require N database queries (I think? Maybe there is some archaic black magic to follow all the parent IDs in SQL directly, but it isn’t going to be pretty).

What I have seen other libraries, most notably the Ruby gem ‘Ancestry’, do, is to store a list of IDs of the path back up the tree. This way, cycles are prevented, and you can also select a subtree at once.

As for how to represent them in memory: Hex.PM contains Arbor, zipper_tree, Garph, and quite possibly some more packages that can help with this (disclaimer: I have not inspected them in detail). The basic idea of a ‘rose tree’ like the one you are attempting to build, is to have a node, which has a list of children (each of these being a node again). In Haskell parlance:

data Tree a = Node a [Tree a]
In Elixir, this would be something like

defmodule Tree do
 defstruct val: nil, children: []
end

Traversing these kind of trees is simple: Given a node, do something with the value, and then call it recursively for all the children (this is pre-order traversal, post-order traversal would be to first go to the children, and then the current node). An implementation of this can be seen in Macro.prewalk and Macro.postwalk: Yes, quoted elixir code is also a tree: an Abstract Syntax Tree (Although it is of course not wrapped in a stuct).

I’m not sure if everyone else is over-thinking it or if I’m just lazy, but I would in no way try to build up a graph there for a few reasons:

First, no cycles are possible in a baked structure in an immutable language, this is a ‘good’ thing.

Second, you are pulling them from a database and everything has an id key as well as a parent_id key, what happens if you have a cycle (database will not catch that)?

I’d just grab the things, stuff them into a map with the key being the id then anytime I need the parent I just do all_of_them[this_thing.id] as I need. It is fast, no duplicating of memory, no giant trees in memory, cycles are represented (your job to break out of cycles if so), etc… etc…