Nested sets, threads, and trees


#1

Hi everyone!

This may be more a database question than a Rails question, but here
goes. I have a few questions about implementing tree structures in my
Rails app. It looks like I’ll run into performance issues any way I
slice it, so I’d love to kick around options with people who have
actually done this before.

The situation is this: I have an application where users can create
items. Each item has a record in the items table. Although users
cannot edit items created by others, they can create a variant of
another user’s item (kind of like forks on GitHub) and edit that. And
variants can spawn their own variants. This means that there is a
tree structure of items and their variants:

Item 1 (by Joe)
|- Item 1 variant A (by Bob)
| '- Item 1 variant A1 (by Alice)
'- Item 1 variant B (by Mary)

Item 2 (by Alice)
'- Item 2 variant (also by Alice)

If the app takes off, there could potentially be thousands of nodes,
and I can expect both node creation and tree retrieval to be quite
frequent. Therefore, I am trying to find a structure where it is not
too expensive to show an item and all its descendants, but where it’s
also not too expensive to create a new item.

Right now, I’m using acts_as_tree, which makes it very cheap to add a
new node to the tree, but appears to also make it expensive to get a
list of an item’s descendants. I’m considering switching to a nested-
set-based approach (probably BetterNestedSet at
http://opensource.symetrie.com/api/better_nested_set/ ), but while
this would make tree retrieval extremely cheap, I am worried about
having to change all records in the database each time a node is
added. Does anyone have any thoughts on which way to go here? It
looks a bit like I’m damned if I do and damned if I don’t.

Thanks,

Marnen Laibow-Koser
removed_email_address@domain.invalid
http://www.marnen.org


#2

On Jan 26, 1:04 pm, Marnen Laibow-Koser removed_email_address@domain.invalid wrote:

Hi everyone!

This may be more a database question than a Rails question, but here
goes. I have a few questions about implementing tree structures in my
Rails app. It looks like I’ll run into performance issues any way I
slice it, so I’d love to kick around options with people who have
actually done this before.
[…]

Update: I am now using awesome_nested_set . It works fine for the
moment, but I’d really like to get a nested-interval system working so
that writes won’t be so expensive. Unfortunately,
acts_as_nested_interval doesn’t work properly at the moment, and I
don’t really want to take the time to patch it at this point (although
I certainly might in future…if nothing else, it would be a very
interesting exercise). Does anyone know of any other nested-interval
plugins for Rails? Or should I just wait and patch
acts_as_nested_interval when the time comes?

Best,

Marnen Laibow-Koser
removed_email_address@domain.invalid
http://www.marnen.org