Has anyone extended Rails's acts_as_tree to use the Modified Preorder Traversal algorithm? This is a really clever trick for optimizing access to trees stored in databases, as described lucidly in this article: http://www.sitepoint.com/article/hierarchical-data... It adds two integer fields, a "left counter" and "right counter", to each row. By updating these in the right way as rows are inserted and deleted in the tree, you can use them to reduce a lot of common tree operations -- like getting the path to a node or finding all the descendends of a node -- to a single query. I used this in the original PHP implementation of my app. I'm sure it can be done easily in Rails, but I'm not comfortable yet doing direct SQL munging on ActiveRecord, so I'd appreciate any tips or pointers to existing code. --Jens Alfke
on 2006-01-16 18:16
on 2006-01-16 19:01
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Jan 16, 2006, at 9:15 AM, Jens Alfke wrote: > Has anyone extended Rails's acts_as_tree to use the Modified > Preorder Traversal algorithm? This is a really clever trick for > optimizing access to trees stored in databases, as described > lucidly in this article: See acts_as_nested_set http://api.rubyonrails.org/classes/ActiveRecord/Ac... ClassMethods.html It'd be cool if acts_as_tree swallowed acts_as_nested_set and automatically chose the tree implementation appropriate for the database columns present. jeremy -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2 (Darwin) iD8DBQFDy98wAQHALep9HFYRAj7NAKDTeA5jmY4VgNQI/NuckiQp42jGyACgg8M2 jziP6enMn/i6mzuNzEECIW0= =x6x0 -----END PGP SIGNATURE-----
on 2006-01-16 19:20
It seems that acts_as_tree is not what you want. acts_as_tree is an implementation of the Adjacency List Model, which as this article points out: http://dev.mysql.com/tech-resources/articles/hiera... Degrades in performance as you add levels to the tree. The Modified Preorder Tree Traversal method, as known as Nested Set Model, is implemented in rails as acts_as_nested_set. But it seems that acts_as_nested_set might not be ready for production use. Agile Web Dev with Rails mentions that: "Rails ships with three acts as extensions: acts_as_list, acts_as_tree, and acts_as_nested_set. I've chosen to document just the first two of these; as this book was being finalized, the nested set variant had some serious problems that prevent us from verifying its use with working code." Can anyone comment on that? What issues specifically is he talking about? Have these issues been addressed?