[drupal-devel] menu memory usage

Konstantin Käfer kkaefer at gmail.com
Mon Oct 24 10:29:54 UTC 2005


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 

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

More information about the drupal-devel mailing list