homepage Welcome to WebmasterWorld Guest from 174.129.74.186
register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts,
Become a Pro Member

Home / Forums Index / Code, Content, and Presentation / Databases
Forum Library, Charter, Moderator: open

Databases Forum

    
More efficient menu setup?
yumigator




msg:3564553
 3:24 am on Feb 2, 2008 (gmt 0)

I've currently got a MySQL that contains information to create a menu. Each entry has information about the link's target, title, unique id, and it's parent in the menu hierarchy.

The PHP function to process this runs as follows:
1. Each link at the top of the menu hierarchy is selected from the database (SELECT * FROM menus WHERE parent='top')
2. Each link that is a child of each result from step 1 is selected (SELECT * FROM menus WHERE parent='whatever')
3. This keeps repeating until the entire menu tree is covered. (top to bottom)

This is of course inefficient. If I had 9 links, each with no children, I would still need 10 queries to get the job done (one to find the 9 at the top, and 9 to check each of those for children).

My site's just starting out, so I won't have much trouble with it, but I can see this causing a lot of problems.

Does anyone have any general ideas? I don't need anythings specific, only advice on how to reorganize my table and make the code more efficient.

Thanks in advance

 

eelixduppy




msg:3565362
 7:44 pm on Feb 3, 2008 (gmt 0)

How often does the information in the menu change? If its not very frequent, then you should use cache to your advantage as it will greatly reduce the amount of database calls that you need to make.

ceestand




msg:3565368
 8:05 pm on Feb 3, 2008 (gmt 0)

I do the same thing, but use a cached XML file to populate the menu. The hierarchical nature of XML make things easier.

The other thing you could do is return all the menu results in one data set, then loop through in your menu:

while(ds.parent == "top")
{
create menu item
}

You can make it a recursive function...

yumigator




msg:3568084
 11:29 pm on Feb 6, 2008 (gmt 0)

Thanks for the replies. I am trying to stick with MySQL, and recursive functions can create a high load. I will consider caching.

Right now, I'm trying the method described here: [sitepoint.com...] . If anyone has experience with the Modified Preorder Tree Traversal method, is there any was to generate output with <ul> and <li> tags?

thanks

jerome




msg:3569976
 7:56 pm on Feb 8, 2008 (gmt 0)

I used exactly the same ressource at Sitepoint when I was designing my CMS. i was worried about nested menus getting out of hands and using too much ressource if a user was to add lots of sub-sections or sub-pages.

Modified Preorder is very, very, efficient when you want to reduce database calls. I'm able to get the full "breadcrumb" of a page or section with just one call.

The trade-off is that inserts are a bit heavier since you have to compute the new left and right values, but for a CMS it's not a problem since you don't add new pages or new sections every second! Reads on the other hand are much more efficient which is what matters here.

No problem to output the menu with UL and LI as i recall.

yumigator




msg:3570101
 10:48 pm on Feb 8, 2008 (gmt 0)

Do you mind sharing some code snippets? I've been trying different things, but I really don't actually know where to start.

jerome




msg:3570311
 10:07 am on Feb 9, 2008 (gmt 0)

Sure. Not sure if that's the cleanest or more efficient code around though!

I start from the new section (or page) being added to the database. The SQL writes everything in the database except the left and right values, which get temporary values (0,0).
Note that while it's not shown here, I *also* keep the value of that section's parent in a traditional way.

Then right after the insert, I call a function to rebuild the tree by computing new left & right values for all the sections. This is a recursive function. Its initial arguments are the left and right+1 values of the meta-section (the one that contains everything else). So to start the iteration, we call it with 0,1.


rebuild_tree(0,1);

Now, in the rebuild_tree function. It's pretty much the function from the Sitepoint ressource.


function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;
// get all children of this node
$request = "SELECT id FROM my.table WHERE parent=$parent;";
$result =doquery($request); // doquery is a user-defined function that does just that ;-)
while ($row = db_fetch_array($resultat)) {
// recursive execution of this function for each
// child of this node.
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row['id'], $right);
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
// it's time to update those values in the database for that section
$request = "UPDATE my.table SET lft='$left', rgt='$right' WHERE id='$parent';";
$result=doquery($request);
// return the right value of this node + 1
return $right+1;
}

Now your table is up-to-date. To use it :

- To get the breadcrumb for a section. Parameter is the section ID, returns an array with each parent sections ID, going back to itself :


function get_breadcrumb {
$request = "SELECT lft,rgt FROM my.table WHERE id=$id LIMIT 1;";
$result =doquery($request);
$line=db_fetch_array($result);
$left = $line['lft']; // just to make the code easier to read, could use the $line['xx'] variables directly.
$right = $line['rgt'];
// Parents for that section are the ones whose left and right boundaries encompass both its own left & right boundaries.
$request = "SELECT id FROM my.table WHERE lft < $left AND rgt > $right;";
$result =doquery($request);
while ($parent=db_fetch_row($resultat)) {
$path[] = $parent[0];
}
$path[] = $id; // we add the initial section's ID to have a full breadcrumb starting with it.
return $path;
}

And the opposite function, to get a section's children (for a menu for example). Parameter is the section ID, and it returns an array with all the section's ID that are children of the one passed in parameter.


function get_section_children_by_id ($id) {
// we get the left & right values of the section we process
$request = "SELECT lft,rgt FROM my.table WHERE id=$id LIMIT 1;";
$result=doquery($request);
$line=db_fetch_array($result);
$left = $ligne['lft']; // to make the code easier to read.
$right = $ligne['rgt'];
$children=array();
// its children are sections whose left & right values are included by those of the section we process
$request = "SELECT id FROM my.table WHERE lft > $left AND rgt < $right;";
$result=doquery($request);
while ($child=db_fetch_row($result)) {
$children[] = $child[0];
}
return $children;
}

Now to display a menu, you have several possibilities. I don't think I have nailed the most efficient one, but maybe someone here will have better advice.

As for me, I display all top-level menus using the parent value (no preorder magic there). Then, when an item is clicked to show a section's content, the menu script will get all its children with one call to get_section_children_by_id when it gets to display that section in the menu, and iterate over the array with UL / LI to display its children just one-level down.
If such a children is clicked, then same operation is repeated. This allows to have a menu that does not get all the possible values at once (and possibly for nothing), but only what the user actually requests.

Hope that helps.

Global Options:
 top home search open messages active posts  
 

Home / Forums Index / Code, Content, and Presentation / Databases
rss feed

All trademarks and copyrights held by respective owners. Member comments are owned by the poster.
Home ¦ Free Tools ¦ Terms of Service ¦ Privacy Policy ¦ Report Problem ¦ About ¦ Library ¦ Newsletter
WebmasterWorld is a Developer Shed Community owned by Jim Boykin.
© Webmaster World 1996-2014 all rights reserved