# Nested sets, threads, and trees **URL:** \ **Category:** Rails\ **Created:** [January 26, 2009, 7:05pm UTC](https://www.ruby-forum.com/t/nested-sets-threads-and-trees/158675 "2009-01-26T19:05:24Z")\ **Posts on this page:** 2\ **Page:** 1
**Author:** ![marnen](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/67e7ee/32.png) [@marnen](https://www.ruby-forum.com/u/marnen)\ **Post date:** [January 26, 2009, 7:05pm UTC](https://www.ruby-forum.com/t/nested-sets-threads-and-trees/158675/1 "2009-01-26T19:05:24Z")
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/](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](http://www.marnen.org) ---
**Author:** ![marnen](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/67e7ee/32.png) [@marnen](https://www.ruby-forum.com/u/marnen)\ **Post date:** [January 29, 2009, 8:50pm UTC](https://www.ruby-forum.com/t/nested-sets-threads-and-trees/158675/2 "2009-01-29T20:50:05Z")
On Jan 26, 1:04 pm, Marnen Laibow-Koser [removed\_email\_address@domain.invalid](mailto: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](http://www.marnen.org)