Rails - Jan 2006 - acts_as_tree with Modified Preorder Traversal?

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-database/2

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

-----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/Acts/NestedSet/ 
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-----

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/hierarchical-data.html

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?

On 1/16/06, Jens Alfke <jens@mooseyard.com> 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:
>
>         http://www.sitepoint.com/article/hierarchical-data-database/2
>
> 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
> _______________________________________________
> Rails mailing list
> Rails@lists.rubyonrails.org
> http://lists.rubyonrails.org/mailman/listinfo/rails
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://wrath.rubyonrails.org/pipermail/rails/attachments/20060116/0bd14519/attachment-0001.html