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
[email protected]
http://www.marnen.org