# Acts\_as\_tree with Modified Preorder Traversal?

**URL:** <https://www.ruby-forum.com/t/acts-as-tree-with-modified-preorder-traversal/61756>\
**Category:** Rails\
**Created:** [January 16, 2006, 6:16pm UTC](https://www.ruby-forum.com/t/acts-as-tree-with-modified-preorder-traversal/61756 "2006-01-16T18:16:44Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![snej](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ecc23a/32.png) [@snej](https://www.ruby-forum.com/u/snej)\
**Post date:** [January 16, 2006, 6:16pm UTC](https://www.ruby-forum.com/t/acts-as-tree-with-modified-preorder-traversal/61756/1 "2006-01-16T18:16:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![snej](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ecc23a/32.png) [@snej](https://www.ruby-forum.com/u/snej)\
**Post date:** [January 16, 2006, 7:01pm UTC](https://www.ruby-forum.com/t/acts-as-tree-with-modified-preorder-traversal/61756/2 "2006-01-16T19:01:59Z")

</div>

-----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/](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-----

---

<div class="post-metadata">

**Author:** ![snej](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ecc23a/32.png) [@snej](https://www.ruby-forum.com/u/snej)\
**Post date:** [January 16, 2006, 7:20pm UTC](https://www.ruby-forum.com/t/acts-as-tree-with-modified-preorder-traversal/61756/3 "2006-01-16T19:20:05Z")

</div>

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](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?