[Dbix-class] DBIx::Class::Tree::Fast

[vdg]

On Tue, Aug 3, 2010 at 10:17 PM, Ian <dbix-class at iandocherty.com> wrote:

> Nice one v. Always good to see different implementations. My first
> impressions below.
>
> As the author of DBIx::Class::Tree::NestedSet I tried to ensure that it
> contained the same method names where possible as other similar modules
> (such as DBIx::Class::Tree::AjacencyList).
>

Well, I agree with this general goal. :-)

I note you use the term 'ascendants' which is not a real word and so would
> be confusing. Is this the same as 'ancestors'? If so then it would be best
> to use ancestors since that is a word know by other people and it keeps it
> consistent with other similar modules.
>

Are you sure? I  found ascendant in Webster. Though i'm not a native English
speaker, I was thinking it was more coherent to oppose with descendant. But
it would be easy to fix that anyway.


> I have not had the chance to read the article or the code in detail, but
> does this method allow the children to be ordered?
>
>
No it doesn't because i wanted to make encoding non volatible when inserting
or removing a child. Not everyone needs position, so not tracking position
can be a
performance gain in that case.

But I think i could make a subcomponent with a distinct column to encode
position and add these methods below...


> If so then you should also provide methods
> left_siblings
> right_siblings
> left_sibling
> right_sibling
> leftmost_sibling
> rightmost_sibling
> etc. (see DBIx::Class::Tree::NestedSet for a full list)
>
> Think about people who may want to port from one tree implementation to
> another. Having the same methods makes it much easier for someone to do t=
his
> if they find they don't have exactly the right algorithm.
>
> Regards
> Ian
>
>
>
>
> On 03/08/2010 17:26, vdg wrote:
>
>> Hello all,
>>
>> I have implemented a new dbic component to manage trees.
>>
>> It's an alternative method to DBIx::Class::Tree::AdjacencyList and
>> DBIx::Class::Tree::NestedSet.
>>
>> Basically it's the implementation of the general method describe in this
>> paper :
>>
>> http://arxiv.org/pdf/cs.DB/0402051
>>
>> with this model, you keep the advantage of NestedSet to query
>> descendants without difficulties querying ancestors.
>> Plus the encoding is not volatile (no need to recalculate half of the
>> tree encoding after an insert) and there is
>> a direct correspondence between the materialized path of a node and its
>> encoding. The model is described in the paper
>> are more scalable, but i've yet to make some tests to get an idea how
>> deep you can build down in a tree.
>>
>> This implementation don't use at all the primary key of the table (if
>> any) and don't try to order children.
>> Ordered tree could be a sub component i guess.
>>
>> The only trade-off is that i use 7 (!) columns to do the encoding.
>>
>> github : http://github.com/vdg/DBIx-Class-Tree-Fast
>>
>>
>> Comments and ideas very welcome off course.
>>
>> v.
>>
>>
>>
>> _______________________________________________
>> List: http://lists.scsys.co.uk/cgi-bin/mailman/listinfo/dbix-class
>> IRC: irc.perl.org#dbix-class
>> SVN: http://dev.catalyst.perl.org/repos/bast/DBIx-Class/
>> Searchable Archive:
>> http://www.grokbase.com/group/dbix-class@lists.scsys.co.uk
>>
>
>
> _______________________________________________
> List: http://lists.scsys.co.uk/cgi-bin/mailman/listinfo/dbix-class
> IRC: irc.perl.org#dbix-class
> SVN: http://dev.catalyst.perl.org/repos/bast/DBIx-Class/
> Searchable Archive:
> http://www.grokbase.com/group/dbix-class@lists.scsys.co.uk
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.scsys.co.uk/pipermail/dbix-class/attachments/20100804/ed5=
4afa7/attachment.htm