Forum: Ruby on Rails acts_as_tree with Modified Preorder Traversal?

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.
Jens Alfke (Guest)
on 2006-01-16 18:16
(Received via mailing list)
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
Jeremy Kemper (Guest)
on 2006-01-16 19:01
(Received via mailing list)
-----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-----
Paul Barry (Guest)
on 2006-01-16 19:20
(Received via mailing list)
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?
This topic is locked and can not be replied to.