Acts_as_tree with Modified Preorder Traversal?

Rails
1

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 A.

2

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Jan 16, 2006, at 9:15 AM, Jens A. 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-----

3

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?