PHP/MySQL Best Tree Structure

php / Mysql best tree structure

You can use a Nested Set Model as it yields very efficient queries. Check out Managing Hierarchical Data in MySQL and read the section called Nested Set Model.

If you're using an ORM like Doctrine, it includes nested set capabilities.

It can be difficult for some to grasp the nested set concepts of left and right. I have found that using those numbers as an analogy for the line numbers of open/close tags in an XML document, folks find it easier to grasp.

For instance, take the data example from the MySQL link above:

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

If you take the lft, rgt fields and use them as line numbers for an XML document, you get:

1. <electronics>
2.    <televisions>
3.        <tube>
4.        </tube>
5.        <lcd>
6.        </lcd>
7.        <plasma>  
8.        </plasma> 
9.     </televisions>
10.    <portable electronics>
11.        <mp3 players>
12.            <flash>
13.            </flash>
14.        </mp3 players>
15.        <cd players>
16.        </cd players>
17.        <2 way radios>
18.        </2 way radios>
19.    </portable electronics>
20. </electronics>

Seeing it this way can make it much easier for some to visualize the resulting nested set hierarchy. It also makes it clearer why this approach improves efficiency as it makes it possible to select entire nodes without the need for multiple queries or joins.

how to php mysql draw a tree structure

<?php
function get_path($category_id) 
{
    // look up the parent of this node
    $result = mysql_query("SELECT c1.parent_id,c2.category_name AS     parent_name FROM category AS c1
LEFT JOIN category AS c2 ON c1.parent_id=c2.category_id 
WHERE c1.category_id='$category_id' ");
$row = mysql_fetch_array($result);

   // save the path in this array
    $path = array();

    //continue if this node is not the root node
    if ($row['parent_id']!=NULL) 
    {
        // the last part of the path to node

        end($path);
        $last_key = key($path);
        $key = $last_key==0 ? 0 : $last_key+1;

        $path[$key]['category_id'] = $row['parent_id'];
        $path[$key]['category_name'] = $row['parent_name'];

        $path = array_merge(get_path($row['parent_id']), $path);
    }

   return $path;
}
?>

To print the path, just do the following:

<?php
for ($i=count($path)-1;$i==0;$i--)
{
     echo $path[$i]['category_name']. '>';
}
?>

You have seen how to find the path from a leaf (node with no children) to the root node. Let's now see how to go down through the hierarchy -- i.e. start from the root element and display all nodes according to their hierarchical relations:

<?php
function display_children($category_id, $level) 
{
    // retrieve all children
    $result = mysql_query("SELECT * FROM category WHERE     parent_id='$category_id'");

    // display each child
    while ($row = mysql_fetch_array($result)) 
    {
        // indent and display the title of this child
       // if you want to save the hierarchy, replace the following line with     your code
        echo str_repeat('  ',$level) . $row['category_name'] . "<br/>";

       // call this function again to display this child's children
       display_children($row['category_id'], $level+1);
    }
}
?>

http://www.phpbuilder.com/articles/databases/mysql/handling-hierarchical-data-in-mysql-and-php.html

What is the best practice for fetching a tree of nodes from database for further rendering?

I usually recommend a design called Closure Table.

See example in my answer to What is the most efficient/elegant way to parse a flat table into a tree?

I also designed this presentation: Models for Hierarchical Data with SQL and PHP. I developed a PHP app that render a tree in 0.3 seconds, from a collection of hierarchical data with 490k nodes.

I blogged about Closure Table here: Rendering Trees with Closure Table.

I wrote a chapter about different strategies for hierarchical data in my book, SQL Antipatterns: Avoiding the Pitfalls of Database Programming.

how to draw a tree structure in php from mysql data?

Function for making an array for child-parent:

function parseTree($tree, $root = null) {
    $return = array();
    # Traverse the tree and search for direct children of the root
    foreach($tree as $child => $parent) {
        # A direct child is found
        if($parent == $root) {
            # Remove item from tree (we don't need to traverse this again)
            unset($tree[$child]);
            # Append the child into result array and parse its children
            $return[] = array(
                'name' => $child,
                'children' => parseTree($tree, $child)
            );
        }
    }
    return empty($return) ? null : $return;    
}

For output:

function printtree($tree) {
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $node) {
            echo '<li>'.$node['name'];
            printTree($node['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

Full PHP script:

<?php
$arr = array(
'216'=>103,
'217'=>216,
'88'=>216,
'102'=>NULL,
'103'=>102,
'104'=>102
);
function parseTree($tree, $root = null) {
    $return = array();
    # Traverse the tree and search for direct children of the root
    foreach($tree as $child => $parent) {
        # A direct child is found
        if($parent == $root) {
            # Remove item from tree (we don't need to traverse this again)
            unset($tree[$child]);
            # Append the child into result array and parse its children
            $return[] = array(
                'name' => $child,
                'children' => parseTree($tree, $child)
            );
        }
    }
    return empty($return) ? null : $return;    
}

function printtree($tree) {
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $b) {
            echo '<li>'.$b['name'];
            printtree($b['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

printtree(parseTree($arr));
?>

Output:

• 102
  • 103
    • 216
      • 217
      • 88
  • 104

small CSS one could use :-

li 
    { 
        position: relative; 
        margin-left: -15px;
        list-style: none;
    }

Store tree data structure in database

You could store the data in a table using nested sets.

http://en.wikipedia.org/wiki/Nested_set_model#Example

I worry that your millions of nodes may make life difficult if you intend to constantly add new items. Perhaps that concern could be mitigated by using rational numbers instead of integers as the left and right values. Add a column for depth to speed up your desire to ask for descendants. I wrote some SQL to create the table and the stored procedures you asked for. I did it in SQL Server do the syntax might be slightly different but it's all standard SQL statements being executed. Also I just manually decided the upper and lower bounds for each Node. Obviously you'd have to deal with writing the code to get these nodes inserted (and maintained) in your database.

CREATE TABLE Tree(
    Node nvarchar(10) NOT NULL,
    Value int NOT NULL,
    L int NOT NULL,
    R int NOT NULL,
    Depth int NOT NULL,
);

INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('A', 100,  1, 28, 0);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('B', 100,  2,  3, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('C', 300,  4,  5, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('D', 150,  6, 25, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('E', 200, 26, 27, 1);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('F', 400,  7,  8, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('G', 250,  9, 10, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('H', 500, 11, 12, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('I', 350, 13, 21, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('J', 100, 21, 22, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('K',  50, 23, 24, 2);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('L', 100, 14, 15, 3);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('M', 300, 16, 17, 3);
INSERT INTO Tree (Node, Value, L, R, Depth) VALUES ('N', 200, 18, 19, 3);

CREATE PROCEDURE grandValue
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    SELECT @lbound = L, @ubound = R FROM Tree WHERE Node = @Node
    SELECT SUM(Value) AS Total FROM TREE WHERE L >= @lbound AND R <= @ubound
    RETURN
END;

EXECUTE grandValue 'C';
EXECUTE grandValue 'I';
EXECUTE grandValue 'A';

CREATE PROCEDURE children
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    DECLARE @depth INT;
    SELECT @lbound = L, @ubound = R, @depth=Depth FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L > @lbound AND R < @ubound AND Depth = (@depth + 1)
    RETURN
END;

EXECUTE children 'C';
EXECUTE children 'I';
EXECUTE children 'A';

CREATE PROCEDURE family
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    SELECT @lbound = L, @ubound = R FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L > @lbound AND R < @ubound
    RETURN
END;

EXECUTE family 'C';
EXECUTE family 'I';
EXECUTE family 'A';

CREATE PROCEDURE parent
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    DECLARE @depth INT;
    SELECT @lbound = L, @ubound = R, @depth = Depth FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L < @lbound AND R > @ubound AND Depth = (@depth - 1)
    RETURN
END;

EXECUTE parent 'C';
EXECUTE parent 'I';
EXECUTE parent 'A';

CREATE PROCEDURE ancestor
    @Node NVARCHAR(10)
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @lbound INT;
    DECLARE @ubound INT;
    SELECT @lbound = L, @ubound = R FROM Tree WHERE Node = @Node
    SELECT Node FROM TREE WHERE L < @lbound AND R > @ubound
    RETURN
END;

EXECUTE ancestor 'C';
EXECUTE ancestor 'I';
EXECUTE ancestor 'A';

For creating the nested sets in the table in the first place you can run some code to generate the inserts or start with the first node and then successively add each additional node - although since each add potentially modifies many of the nodes in the set there can be a lot of thrashing of the database as you build this.

Here's a stored procedure for adding a node as a child of another node:

CREATE PROCEDURE insertNode
    @ParentNode NVARCHAR(10), @NewNodeName NVARCHAR(10), @NewNodeValue INT
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @ubound INT;
    DECLARE @depth INT;
    SELECT @ubound = R, @depth = Depth FROM Tree WHERE Node = @ParentNode
    UPDATE Tree SET L = L + 2 WHERE L >= @ubound
    UPDATE Tree SET R = R + 2 WHERE R >= @ubound
    INSERT INTO Tree (Node, Value, L, R, Depth) VALUES (@NewNodeName, @NewNodeValue,  @ubound, @ubound + 1, @depth + 1);
    RETURN
END;

I got this from http://www.evanpetersen.com/item/nested-sets.html who also shows a nice graph walking algorithm for creating the initial L and R values. You'd have to enhance this to keep track of the depth as well but that's be easy.

---

Related Topics