Forum: Ruby on Rails Nested sets, threads, and trees

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Dd2d775dea75b381edb1bbf0600a0907?d=identicon&s=25 Marnen Laibow-Koser (marnen)
on 2009-01-26 19:05
(Received via mailing list)
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
marnen@marnen.org
http://www.marnen.org
Dd2d775dea75b381edb1bbf0600a0907?d=identicon&s=25 Marnen Laibow-Koser (marnen)
on 2009-01-29 20:50
(Received via mailing list)
On Jan 26, 1:04 pm, Marnen Laibow-Koser <mar...@marnen.org> 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
marnen@marnen.org
http://www.marnen.org
This topic is locked and can not be replied to.