[drupal-devel] nested sets (was menu memory usage)

[Moshe Weitzman]

Konstantin describes a node hierarchy system powered by nested sets. Thats 
far more powerful than Ber's relations as described in those links. Nested 
sets allow you to express complex hierarchies with excellent performance. 
Thats not true with flat relations table.

Many of us in Amsterdam discussed nested sets as a promising solution to our 
  widespread neet for hierarchy. I encourage Konstantin and others to pursue 
this solution. Book.module is also excellent test case IMO.

-moshe

Bèr Kessels wrote:
> you just described the general relation system :)
> 
> read more on: 
> http://drupal.org/node/34168
> http://www.webschuur.com/relations_system
> http://drupal.org/node/28480
> 
> and have a look at the tables at 
> http://drupal.org/node/28480#comment-42850
> (and the commetn above it for some descriptions)
> 
> Ber
> 
> Op maandag 24 oktober 2005 12:30, schreef Konstantin Käfer:
>> Hello,
>>
>> recently, I have been experimenting with nested sets. Nested sets
>> provide a rather simple technology to store huge (menu) trees in a
>> database without having to loop through them using recursion. As
>> recursion eats more time as the tree grows large and if there are more
>> levels, it is not adviced to use this technology in relational databases.
>>
>> The nested set (or nested tree) works by adding two  meta values to the
>> record, one left value and one right value. Let's take the following
>> menu structure:
>>
>> root [1/24]
>> -- create content [2/7]
>>    -- page [3/4]
>>    -- story [5/6]
>> -- my account [8/9]
>> -- administer [10/23
>>    -- access control [11/12]
>>    -- settings [13/20]
>>       -- content types [14/15]
>>       -- posts [16/17]
>>       -- users [18/19]
>>    -- users [21/22]
>>
>> For an extensive example, see
>> http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/ind
>> ex.html.
>>
>> The left and right values are in the square brackets, the first is the
>> left one and the second the right one. The advantage is, that it is easy
>> to obtain all necessary leafs with one single query.
>>
>> I don't like the current taxonomy system. I just want a tree where I can
>> attach nodes to and let drupal build the complete navigation structure.
>> Another disadvantage of the taxonomy system is also that building real
>> breadcrumbs is very costly (due to recursion). Yesterday, I started a
>> module (named ouline) that uses a nested tree instead of taxonomy to
>> classify content. At the moment it is already capable of building a
>> breadcrumb with one single query:
>>
>>     SELECT node.nid as nid, node.title as title
>>       FROM outline AS selector
>> CROSS JOIN outline AS outline
>>         ON (selector.lft BETWEEN outline.lft AND outline.rgt AND
>> selector.tid = outline.tid)
>> CROSS JOIN node AS node
>>         ON (outline.nid = node.nid AND node.status > 0 AND node.moderate
>> = 0)
>>      WHERE selector.nid = <node id> AND outline.nid != selector.nid
>>   ORDER BY outline.lft
>>
>> If the outline table would be integrated within the node table, you even
>> need to JOIN one table less. Another advantage is that the nested set
>> does not mess around with "weight" propertys. There is only one single
>> allowed order (that can be changed very easly though, for example using
>> drag and drop with AJAX and regular buttons as fallback).
>>
>> Konstantin Käfer
>>
>> Karoly Negyesi schrieb:
>>> Hi!
>>>
>>> Probably most of the devels have not noticed
>>> http://drupal.org/node/34755  "when I enable all modules in core, the
>>> menu array eats over 800K of RAM".  As we now have menu-otf which will
>>> be badly abused and (almost) all nodes  will be put in the menu
>>> hierarchy instead of stuff like About Us, FAQ etc,  we can look ahead
>>> for situations where someone locks himself out of his  drupal cold
>>> after a node submission because the menu tree will grow too  large. I
>>> know this can not be solved for 4.7, it's too late, but let's  discuss
>>> it.
>>>
>>> Regards
>>>
>>> NK
>  Bèr