 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Wound of treelike structures in Databases (Nested Sets)
I think with a problem of storage of trees in MySQL many collided{faced} and I do not need to explain how much thus arises problems. In given clause{article} I want to tell about one of methods of storage of trees under the name " the Enclosed sets " (Nested Sets). For the beginning the description of a method. Look at figure below (I draw poorly):
On him the tree described duly of a method of " the Enclosed sets " is submitted.
Squares designate sites of a tree, red figures in the center of sites - simply unique identifiers of the site, and figures in corners is left and right displacement. In these two figures - the left and right displacement the information on a tree is incorporated. And if the information on displacement to bring in a database job with a tree much more becomes simpler.
Pay attention to in what order prostavleny these displacement. If mentally to pass under the order from 1 up to 22 you will bypass all sites of a tree from left to right. Actually it is a way of detour of all sites of a tree from left to right. I shall describe rules on which these displacement are placed:
* To begin detour of a tree it is necessary from the root site and in him to stop.
* At the very first input{entrance} in the site it is necessary "to leave" figure in his left corner and at last output{exit} from the site it is necessary to leave figure in a right corner.
* All figures are placed, since 1.
* Last figure should be in 2 times of more quantity of sites of a tree (because in each site it is left on 2 by the mentioned above rules)
Given clause{article} is intended first of all for PHP-programmers. Therefore I shall not go into details as "manually" to organize such tree in the mysql-table as for this purpose there is a ready class - CDBTree. To download it it is possible with http://dev.e-taller.net/dbtree/ <http: // www.internet-technologies.ru/? url=http%3A%2F%2Fdev.e-taller.net%2Fdbtree%2F>
On it the theory practice comes to an end and begins. We shall assume it is necessary to make the catalogue of resources with categories neogranichenoj enclosure. Thus before the programmer there are some micro-problems:
* It is necessary to draw a conclusion of a tree of categories
* It is necessary to receive the list of ALL subcategories for the specified category
* It is necessary to receive the list of subcategories which level of an enclosure on unit is more a than level of an enclosure of the specified category
* It is necessary to receive the list of all parental categories for the specified category (for postorenija ways to the current category)
I shall notice, that class CDBTree still stores{keeps} in the table a level of an enclosure for the given site. It is the fact will facilitate to us the decision of a problem number{room} 3 For the beginning create the 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;
The given table is submitted only for examples. At the end of clause{article} I shall result words of the author of a class concerning the organization of tables for storage of trees. And now execute the following script:
<?
/*
Job with a tree on algorithm Nested Sets.
Preparation of the table for job.
The class dbtree.php is used
To take it it is possible: http://dev.e-taller.net/dbtree/
---------------------
Author: Maxim Matykhin.
mailto: max@webscript.ru
*/
$table = "categories"; // the table of categories
$id_name = "cid"; // a name of a field of a primary key
$field_names = array (// names of fields of the table
' 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);
// We create "root" recording (see explanatories to clause{article})
$id = $ Tree-> clear (array ("title" => " the Catalogue 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" => "Soprt"));
$level_2 [3] = $Tree-> insert ($id, array ("title" => "Miscellaneous"));
// Now we shall create some recordings 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" => "is criminal"));
$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"));
// And for the some people we shall make the fourth level
$Tree-> insert ($level_3 [0], array ("title" => "PEAR"));
$Tree-> insert ($level_3 [8], array ("title" => "Metallurgy"));
$Tree-> insert ($level_3 [6], array ("title" => "Mortuaries"));
echo " the Table is filled. ";
?>
The given example simply fills in the table (simply that the following examples potestit` on her).
I think a code here it is clear. Probably it is necessary to explain a line only:
<? $id = $ Tree-> clear (array ("title" => " the Catalogue of resources "));?>
The given line inserts the root site into the table. The root site should be one. Also it is necessary to notice, that this method clears the table, before an insert so be cautious.
Now let's deduce{remove} a tree. For this purpose simply enough to deduce{remove} all elements, having sorted them on cleft:
<?
$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> ";
}
?>
In this case for calculation of size of a space value clevel is used. Now we shall see how to receive all subcategories. It can be made or with the help of a method enumChildrenAll ($cid); or having written correct SQL-search. We shall assume there is a category which parameters $cleft, $cright and $clevel. Then the search receiving all affiliated sites, looks so:
SELECT
cid,
title,
clevel
FROM
categories
WHERE
cleft BETWEEN $cleft AND $cright
ORDER BY cleft
Having executed this search, you receive all subcategories for the specified category the Method enumChildrenAll ($cid); also returns subcategories, but he returns only their identifiers, and there are no built - in methods that he returned additional fields (certainly you can make changes to a class).
For reception of the list of subcategories which level of an enclosure on unit is more a than level of an enclosure of the specified category occurs.
SELECT
cid,
title,
clevel
FROM
categories
WHERE
cleft BETWEEN $cleft AND $cright AND
clevel = $clevel+1
ORDER BY cleft
And the last - definition of parental categories.
The search should look so:
SELECT
cid,
title,
clevel
FROM
categories
WHERE
cleft <$cleft AND
cright> $cright
ORDER BY cleft
In class CDBTree for this purpose there is a method enumPath ($cid).
Now about recommendations of the author of a class:
Experience shows, that the structure with detour of a tree is better for storing{keeping} separately from
The data since in this case at updating the table are very for a long time updated
Indexes, and the data can make impossible a format of recording fixed
Lengths, that too will cardinally have an effect on speed.
The most optimum structure in my opinion will be:
CREATE TABLE categories (
cat_id INT UNSIGNED NOT NULL AUTO_INCREMENT,
cat_left INT UNSIGNED NOT NULL,
cat_right INT UNSIGNED NOT NULL,
cat_level INT UNSIGNED NOT NULL,
PRIMARY KEY (cat_id)
KEY (cat_left, cat_right, cat_level)
);
In result MySQL for many searches will not address at all to a file with the data.
The file with indexes will suffice him. And when will already pass all filtering in
To the table with a tree, on primari-keju quickly will take place linkovanie with the others
The data.
Also I shall add, that the author of a class recommends to use his (class) only for addition / removal of sites in a tree, and for reception of sites to write SELECT-searches most.
The description of methods of class CDBTree
CDBTree (and $DB, $tableName, $itemId, $fieldNames=array ())
The designer
Parameters:
* And $DB - the link to object of class CDatabase (this class lays in archive with dbtree.php);
* $tableName - a name of the table in which "tree" lays;
* $itemID - the name of a primary key of the table in which lays "tree";
* $fieldNames - a file with names of fields of the table
function getElementInfo ($ID)
Returns a file with the information about about an element with specified $ID (parameters left, right, level).
function clear ($data=array ())
The given function clears the table and inserts into it{her} the root site of a tree.
In a file $data there should be an information as array ("db_field" => "value"...)
Fields left, right and level will be automatically inserted.
function update ($ID, $data)
This method is used for change of the information on the specified element. Parameters:
* $ID - the identifier of the site
* $data - a file with the updated data. (parameters left, right and level to insert it is not necessary)
function insert ($ID, $data)
Method for an insert of the site in a tree. Parameters:
* $ID - the identifier of the parental site
* $data - a file with the updated data. (parameters left, right and level to insert it is not necessary)
function delete ($ID)
Deletes the specified site not deleting his "descendants";
function deleteAll ($ID)
Deletes the specified site together with his "descendants";
function enumChildrenAll ($ID)
Defines{Determines} all "descendants" for the specified site
function enumChildren ($ID, $start_level=1, $end_level=1)
Defines{Determines} descendants for the specified site
* $start_level - with which it is necessary to search for an initial level of an enclosure of the site of "descendants";
* $end_level - up to which it is necessary to search for a final level of an enclosure of the site of "descendants";
If $end_level it is not specified, (it is equal 0) that all sites "more deeply" $start_level are searched
function enumPath ($ID, $showRoot=false)
Defines{Determines} all parents for the specified site.
* $showRoot - true if it is necessary to deduce{remove} a root element.
Last three described functions form SQL-search in such a manner that identifiers of the site are deduced only.
Other methods to me to use it was not necessary. I shall not describe therefore them. In last version of a class method MoveAll for moving sites to a tree but while he works with bugs has appeared.
