Creating a nested list based on mysql data
Moderator: General Moderators
Creating a nested list based on mysql data
HI all,
Can anyone help me pull this off....
Imagine a knowledge base, for example, which contains many categories and a never-ending number of subcategories. In MySQL, we have a table called "Categories" in which each category has a CategoryID as well as a ParentCategoryID.
How could I use that information to create a tree view of all the categories?
I hope the question's clear. Many thanks in advance.
Can anyone help me pull this off....
Imagine a knowledge base, for example, which contains many categories and a never-ending number of subcategories. In MySQL, we have a table called "Categories" in which each category has a CategoryID as well as a ParentCategoryID.
How could I use that information to create a tree view of all the categories?
I hope the question's clear. Many thanks in advance.
Re: Creating a nested list based on mysql data
Building a tree structure from a flat set with no other parameters than the parent ID is a non-trivial problem. I did get to work on a similar requirement to yours some time ago (I was working on emulating file folders structure in the same way), and I came up with a not very elegant solution, but it works:
It works by reorganizing a two dimensional array (ie, the result set of a MySQL query) into array that lists all the categories, with each being an array of subcategories ID's. The first index of every category array is the name of the category, and the first array of the entire tree lists the categories without a parent ID (ie, the main categories). It will look something like this:
Hope this helps.
Code: Select all
class TreeSet {
/**
* Build tree structure from array
*
* Reorganizes flat array into a tree like structure
*
* @param array $categories
* @return array
*/
public function buildTree($categories) {
$tree = array(0 => array());
foreach($categories as $category){
$tree[$category['id']][0] = $category['name'];
if(!is_null($category['parent_id'])){
if(!isset($tree[$category['parent_id']])){
$tree[$category['parent_id']] = array();
}
$tree[$category['parent_id']][$this -> findFreeIndex($tree[$category['parent_id']],1)] = $category['id'];
} else {
$tree[0][$this -> findFreeIndex($tree[0],1)] = $category['id'];
}
}
ksort($tree,SORT_ASC);
return $tree;
}
/**
* Determine next un-used array index
*
* @param array $array
* @param int $startInd
* @return int
*/
protected function findFreeIndex($array,$startInd = 0) {
return (isset($array[$startInd]) ? $this -> findFreeIndex($array,$startInd + 1) : $startInd);
}
}
Code: Select all
array(
0 => array(
1,
3
),
1 => array(
'cat1',
23,
34
),
3 => array(
'cat3',
6
),
6 => array(
'cat6'
10
),
10 => array(
'cat10'
),
23 => array(
'cat23'
),
34 => array(
'cat34'
)
);
Re: Creating a nested list based on mysql data
Hi,
for this purpose you can use recursion:
for this purpose you can use recursion:
Code: Select all
<?php
function path($id, $depth) {
$sql = "SELECT * FROM Categories WHERE ParentCategoryID = $id";
//...
while(...) {
path($row['id'], $depth+2);
echo str_pad($row['name'], $depth, " ", STR_PAD_LEFT);
}
}
//maybe: echo "<pre>";
path(0, 0); //if the main categories have as ParentCategoryID = 0
?>
Re: Creating a nested list based on mysql data
You do realize that every path() call is a new mysql query..
Re: Creating a nested list based on mysql data
pytrin - Thanks. But how do you turn that into a nested list, like
<ul>
<li>Category 1</li>
<li>Category 2
<ul>
<li>Category X which is a child of cateogy 2</li>
<li>Category Y which is a child of category 3
<ul>
<li>Category Z which is a child of Category Y
etc.
Hannes2k - Thanks, but you've lost me!
<ul>
<li>Category 1</li>
<li>Category 2
<ul>
<li>Category X which is a child of cateogy 2</li>
<li>Category Y which is a child of category 3
<ul>
<li>Category Z which is a child of Category Y
etc.
Hannes2k - Thanks, but you've lost me!
Re: Creating a nested list based on mysql data
You iterate recursively over the reorganized array. I had a couple more methods in the original class which looked something like this:
Then you can run:
Code: Select all
class TreeSet {
/**
* Draw folder tree structure
*
* First step in a recursive drawing operation
*
* @param array $tree
* @return string
*/
public function drawTree($tree) {
$html = '<ul>';
foreach($tree[0] as $id){
$html .= $this -> drawBranch($id,$tree,true);
}
$html .= '</ul>';
return $html;
}
/**
* Recursively draw tree branches
*
* @param int $id
* @param array $tree
* @param boolean $isRoot
* @return string
*/
public function drawBranch($id,$tree,$isRoot = false) {
$branch = $tree[$id];
$name = $branch[0];
unset($branch[0]);
$html = '<li>' . $name;
if(count($branch) > 0){
$html .= '<ul>';
foreach($branch as $id){
$html .= $this -> drawBranch($id,$tree);
}
$html .= '</ul>';
}
$html .= '</li>';
return $html;
}
public function buildTree($tree) {...}
protected function findFreeIndex() {...}
}
Code: Select all
//$result is a mysql query result on the categories table
$treeset = new TreeSet();
$html = $treeset -> drawTree($treeset -> buildTree($result));
echo $html;
Re: Creating a nested list based on mysql data
I would love to get hold of that class. Any chance?
Re: Creating a nested list based on mysql data
Well, as I said in the beginning it was for a slightly different purpose - emulating file folders with no limit on sub folders, and it has some file handling methods etc. The relevant methods I put here in the post.
Re: Creating a nested list based on mysql data
Thanks for the help. I'll try and put something together tomorrow.
Re: Creating a nested list based on mysql data
Hi,

but that's the easiest way and if you have ~20 categories this won't be any problem. You can also read the whole table and then create a tree, but, it's sometimes realy hard to realize simple data structures in php. And I even think this won't be faster.
You can speed up this by e.g. collecting the parantId first and then do one SQL statement, so you have just 1 sql statement per depth (or?). But it's a lot of work.
I recommend to read this articel, if the recursion version is to slow:
Managing Hierarchical Data in MySQL
If you change your database design, you can use the nested set model. This would be the fastest & best solution, because you just need one query to get the full tree:
But for this you have to change the table structure and the new structure of the table is a bit more complex.
surepytrin wrote:You do realize that every path() call is a new mysql query..
but that's the easiest way and if you have ~20 categories this won't be any problem. You can also read the whole table and then create a tree, but, it's sometimes realy hard to realize simple data structures in php. And I even think this won't be faster.
You can speed up this by e.g. collecting the parantId first and then do one SQL statement, so you have just 1 sql statement per depth (or?). But it's a lot of work.
I recommend to read this articel, if the recursion version is to slow:
Managing Hierarchical Data in MySQL
If you change your database design, you can use the nested set model. This would be the fastest & best solution, because you just need one query to get the full tree:
Code: Select all
SELECT n.name, COUNT(*)-1 AS depth
FROM table AS n,table AS p
WHERE n.lft BETWEEN p.lft AND p.rgt
GROUP BY n.lft
ORDER BY n.lft;
Last edited by Hannes2k on Fri Nov 14, 2008 12:42 pm, edited 1 time in total.
Re: Creating a nested list based on mysql data
20 queries just to render a category tree is pretty much unacceptable in my opinion. And the solution isn't that hard, it's just not trivial. Regarding performance, I guess performing 20+ queries if you have only one user using the application might be comparable to sorting the array in php. But it will cripple the mysql server as both user count and category count goes up.but that's the easiest way and if you have ~20 categories this won't be any problem. You can also read the whole table and then create a tree, but, it's sometimes realy hard to realize simple data structures in php. And I even think this won't be faster.
A nested set is a good solution for reading tree structures. However for dynamic data, it is a pain to maintain (as you can tell from the article you posted).
Re: Creating a nested list based on mysql data
Just to let you know, this is what I came up with:
Thanks for your help.
Code: Select all
$Categories[] = array("Category A", 1, 0);
$Categories[] = array("Category B", 19, 1);
$Categories[] = array("Category C", 20, 19);
$Categories[] = array("Category D", 2, 1);
$Categories[] = array("Category E", 3, 1);
$Categories[] = array("Category F", 4, 3);
$Categories[] = array("Category G", 5, 4);
$Categories[] = array("Category H", 9, 4);
$Categories[] = array("Category I", 10, 3);
$Categories[] = array("Category J", 11, 3);
$Categories[] = array("Category K" , 12, 1);
$Categories[] = array("Category L", 25, 0);
$Categories[] = array("Category M", 26, 0);
//Go through each one and created arrays of children for each on
foreach($Categories as $Category)
{
list($CategoryName, $CategoryID, $ParentCategoryID) = $Category;
$Children[$ParentCategoryID][] = $CategoryID;
$CategoryNames[$CategoryID] = $CategoryName;
}
function PrintBranch($BranchID)
{
echo "\n<ul>";
foreach($GLOBALS[Children][$BranchID] as $ChildID)
{
echo "\n<li>$ChildID";
if(is_array($GLOBALS[Children][$ChildID])) PrintBranch($ChildID);
echo "\n</li>";
}
echo "\n</ul>";
}
PrintBranch(0);
Re: Creating a nested list based on mysql data
Hi this is a fantastic answer.
And works really well.
However I am totally lost as to how this is actually operating.
Can you provide some comments please as to how the children are being assigned and why are only the $id's displaying how do you display the $names.
Apologize in advance, still learning much of this technology.
thanking you
Joe
And works really well.
However I am totally lost as to how this is actually operating.
Can you provide some comments please as to how the children are being assigned and why are only the $id's displaying how do you display the $names.
Apologize in advance, still learning much of this technology.
thanking you
Joe