• Index
  •  » Articles
  •  » Tree-type structures storage in the database

Tree-type structures storage in the database

Tree-type structures storage in the database

In that article I want to tell about one of the methods of tree storage named “Nested Sets”. Look at the picture below:

At that picture you can see the tree described by all rules of “Nested Sets” method. Squares are tree nodes, red figures are unique identifiers of the nodes, figures in the corners are left and right offsets. Exactly those figures in the corners give all information about the tree. If information about offsets enter to the database working with tree becomes simpler.

Given article is written for PHP programmers, that’s why I’m not going to describe how to create such tree in MySQL table manually, because for that purpose there is a special class CDBTree.

For example we’ll create resource catalog with unlimited nesting categories.

CDBTree class stores in the table the nesting level for the given node. At first create the following table:

CREATE TABLE categories (
cid int(10) unsigned NOT NULL auto_increment,
title varchar(128) NOT NULL default "",
cleft int(10) unsigned NOT NULL default "0",
cright int(10) unsigned NOT NULL default "0",
clevel int(10) unsigned NOT NULL default "0",
PRIMARY KEY (cid),
KEY cleft (cleft, cright, clevel)
) TYPE=MyISAM;

Given table can be used only for examples. Now run the following script:

<?  
/*  
   Working with the tree using algorithm Nested Sets.   
   Class dbtree.php is used

    ---------------------  
    Author: Maxim Matykhin.  
    mailto: max@webscript.ru  
*/  

$table="categories"; // Categories table  
$id_name="cid";     
$field_names = array( // Table’s field names  
   "left" => "cleft",  
   "right"=> "cright",  
   "level"=> "clevel",  
);  

require_once "cd.php";  
require_once "dbtree.php";  

$dbh=new CDataBase("dbname", "localhost", "root", "password");  
$Tree = new CDBTree($dbh, $table, $id_name, $field_names);  
// create the “root” record  
$id=$Tree->clear(array("title"=>"Catalog of resources"));  

$level_2=array();  
$level_2[0]=$Tree->insert($id,array("title"=>"Programming"));  
$level_2[1]=$Tree->insert($id,array("title"=>"News"));  
$level_2[2]=$Tree->insert($id,array("title"=>"Sport"));  
$level_2[3]=$Tree->insert($id,array("title"=>" Miscellaneous"));  

// Now create several records of the third level  
$level_3=array();  
$level_3[0]=$Tree->insert($level_2[0],array("title"=>"PHP"));  
$level_3[1]=$Tree->insert($level_2[0],array("title"=>"Perl"));  
$level_3[2]=$Tree->insert($level_2[0],array("title"=>"Delphi"));  

$level_3[3]=$Tree->insert($level_2[1],array("title"=>"Crime"));  

$level_3[4]=$Tree->insert($level_2[2],array("title"=>"Football"));  
$level_3[5]=$Tree->insert($level_2[2],array("title"=>"Chess"));  

$level_3[6]=$Tree->insert($level_2[3],array("title"=>" medicine"));  
$level_3[7]=$Tree->insert($level_2[3],array("title"=>"Ecology"));  
$level_3[8]=$Tree->insert($level_2[3],array("title"=>" industry"));  
                                               
$Tree->insert($level_3[0],array("title"=>"PEAR"));  
$Tree->insert($level_3[8],array("title"=>" metallurgy"));  
$Tree->insert($level_3[6],array("title"=>" morgues"));  
echo "Table is filled.";  
?>

Given example fills the table. I think that code is clear. I’ll explain only one line:

<? $id=$Tree->clear(array("title"=>"Catalog of recourses")); ?>

Given line inserts the root node to the table. There must be only one root node. I have to mention that given method clears the table before insertion, so, be careful. Now let’s create the tree.

<?  
$query="SELECT * FROM ".$table." ORDER BY cleft ASC";  
$result=$dbh->query($query);  
while($row = $dbh->fetch_array($result))  
{  
   echo str_repeat("&nbsp;",6*$row["clevel"]).$row["title"]."<br>";  
}  
?>

Now let’s view how we can get subcategories. It can be done with the help of enumChildrenAll($cid) method, or by the SQL query. Let’s suppose we have a category with such parameters as $cleft, $cright and $clevel. In that case our query will look like:

SELECT
cid,
title, 
clevel
FROM
categories
WHERE
cleft BETWEEN $cleft AND $cright 
ORDER BY cleft

By means of that query you will get all subcategories for the given category. Method enumChildrenAll($cid); also returns subcategories, but it returns only their identifiers.

For getting the list of subcategories nesting level of which is greater by unit than the nesting level of the given category you have to run the following script:

SELECT
cid,
title, 
clevel
FROM
categories
WHERE
cleft BETWEEN $cleft AND $cright AND
clevel = $clevel+1
ORDER BY cleft

At last you have to define the parent categories. Query should have the following form:

SELECT
cid,
title, 
clevel
FROM
categories
WHERE
cleft < $cleft AND
cright > $cright 
ORDER BY cleft

Description of the CDBTree class methods.

CDBTree(&$DB, $tableName, $itemId, $fieldNames=array())

Constructor

Parameters:

  • &$DB is a reference to the CDatabase class object
  • $tableName is a name of the table where “tree” is situated
  • $itemID is the name of the table primary key where “tree” is situated
  • $fieldNames is an array with the table field’s names

function getElementInfo($ID)

Returns the array with information about the element with indicated $ID (parameters left, right, level).

function clear($data=array())

Given function clears the table and inserts the root node. In the $data array there should be information in the form of array("db_field"=>"value", ...). Fields left, right and level will be inserted automatically.

function update($ID, $data)

That method is used for changing the information about the element. Parameters:

  • $ID – parent node’s ID
  • $data – array with updated data (there is no use to set left, right and level parameters)

function delete($ID)

Deletes the indicated node without deleting its children

function deleteAll($ID)

Deletes the indicated node with its children

function enumChildrenAll($ID)

Defines all the children for the indicated node

function enumChildren($ID, $start_level=1, $end_level=1)

Defines children for the indicated node

  • $start_level – start nesting level of the node
  • $end_level – end nesting level of the node

function enumPath($ID, $showRoot=false)

Defines all parents for the indicated node.


 

  • Top