Деревья Nested Sets


Прислал: LSD^ [ 22.10.2003 @ 16:45 ]
Раздел:: [ Статьи по PHP ]


Для начала нужно обязательно сходить и прочесть статью http://myphp.net.ru/lessons/index.php?18 ( http://myphp.net.ru/lessons/index.php?18 ) Это введение в деревья использующие алгоритм Nested Sets и необходимая и пользовая теория. Вкратце можно сказать что деревья используются в таблицах хранящих категории товаров неограниченной вложенности или например структуру всего сайта или структуру директорий на вашем винте и т.д. Всю эту прелесть можно хранить в одной таблице и ею довольно легко манипулировать.

Для создания и работы с деревьями Nested Sets написан класс CDBTree, качать его нугено тута ( http://dev.e-taller.net/dbtree/phpDbTree.zip ). Вообщем все нужное вы найдете на http://www.e-taller.net/dbtree/ ( http://www.e-taller.net/dbtree ) Не буду вдаваться в теорию, далее будет представлен код и основные методы работы с этим типом дерева.

Итак... будем считать что теория прочитана и сейчас главное разобраться с SQL запросами. Для удобства заводим две функции: для коннекта к базе и для вывода дерева. И потом засылаем запросы к базе. Кусок IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag дает нам 1 если элемент дерева имеет потомков, иначе 0.

Для работы всех примеров используется уже готовое дерево Nested Sets - таблица molotok её дамп тута ( http://www.limout.com/tmp/ns/molotok.sql ), настройки базы в фукции connect_db(). Если вы создадите свою табицу или она у вас уже есть, то её название в переменной $tbl. Исходники всех примеров тута ( http://www.limout.com/tmp/ns/ns_doc.zip ), вы можете их скачать и погонять на своем тазике :))

Первый пример (ns_test1.php)
Основные методы работы с деревом.

<?php

function connect_db()
{
    
mysql_connect("localhost", "root", "") or die("Can`t connect");
    
mysql_select_db("bidz") or die("Can`t select");
}

function
print_rez($query, $text="")
{
    
$result = mysql_query($query);
    if (
mysql_num_rows($result) == 0) die("Empty result or Bad sql: ".$query);
    echo (!empty(
$text) ? "<P><B>".$text."</B><BR>n" : "<P>n").$query."<P>n";
    while (
$row = mysql_fetch_assoc($result))
        echo
str_repeat("&nbsp; &nbsp; &nbsp;",    $row['cat_level']).
            
" [".$row['cat_id']."] ". ((isset($row['nflag']) && $row['nflag']) ? "<b>".$row['cat_name']."</b>" : $row['cat_name']).
            
" <font color='#0033FF'>[".$row['cat_left']."]</font> ".
            
" <font color='#009900'>[".$row['cat_right']."]</font> (".$row['cat_level'].") <br>";
}

$tbl = "molotok";
connect_db();


// Выводим все дерево
//
$query = "SELECT *, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM ".$tbl." ORDER BY cat_left";
print_rez($query, "Выводим все дерево");


// Выводим всех родителей
//
$id = 65; // id нужного элемента
$query = "SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM ".$tbl." A, ".$tbl." B WHERE B.cat_id='".$id."' AND B.cat_left BETWEEN A.cat_left AND A.cat_right ORDER BY A.cat_left";
print_rez($query, "Выводим всех родителей для элемента: ".$id);


// Выводим нужную ветку
//
$id = 14; // id нужного элемента
$query = "SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM ".$tbl." A, ".$tbl." B WHERE B.cat_id='".$id."' AND A.cat_left >= B.cat_left AND A.cat_right <= B.cat_right ORDER BY A.cat_left";
print_rez($query, "Выводим ветку для элемента: ". $id);


//Выводим "приоткрытое" дерево
//
$ncat = 44; // id нужного элемента
$query = "SELECT A.* FROM ".$tbl." A, ".$tbl." B WHERE B.cat_id = '".$ncat."' AND B.cat_left BETWEEN A.cat_left AND A.cat_right ORDER BY A.cat_left";
$result = mysql_query($query);
if ((
$alen = mysql_num_rows($result)) == 0) die("Err!");
$i = 0;
$sql = "";

while (
$row = mysql_fetch_assoc($result))
{
    if ((++
$i == $alen) && ($row['cat_left']+1 == $row['cat_right'])) break;
    
$sql .= " OR (cat_level=".($row['cat_level']+1)." AND cat_left>".$row['cat_left']." AND cat_right<".$row['cat_right']. ")";
}

$sql = "SELECT *, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM ".$tbl." WHERE cat_level=1 ".$sql." ORDER BY cat_left";
print_rez($sql, "Выводим "приоткрытое" дерево для элемента: ". $ncat);

?>

Запускаем все это дело и видим нужный нам результат...

Выводим все дерево
SELECT *, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM molotok ORDER BY cat_left

[1] [1] [132] (0)
      [2] Книги, Видео, Музыка, CD [2] [63] (1)
           [3] Журналы и газеты [3] [4] (2)
           [4] Видео [5] [28] (2)
                [21] Видеодиски [6] [13] (3)
                     [33] Комедии, Мелодрамы [7] [8] (4)
                     [34] Семейное и детское кино [9] [10] (4)
                     [35] Фантастика, Мистика, Ужасы [11] [12] (4)
                [22] DVD-диски [14] [15] (3)
                [23] Видеокассеты с неигровыми записями [16] [17] (3)
                [24] Видеокассеты с зарубежными фильмами [18] [25] (3)
                     [36] Комедии, Мелодрамы [19] [20] (4)
                     [37] Семейное и детское кино [21] [22] (4)
                     [38] Фантастика, Мистика, Ужасы [23] [24] (4)
                [25] Видеокассеты с фильмами без перевода [26] [27] (3)
           [5] Книги [29] [58] (2)
                [26] Художественная литература [30] [31] (3)
                [27] Детская литература [32] [33] (3)
                [28] Дом, Семья, Досуг [34] [35] (3)
                [29] Естественные науки [36] [37] (3)
                [30] Искусство, искусствоведение [38] [39] (3)
                [31] Компьютеры, Программирование, Интернет [40] [55] (3)
                     [60] PHP [41] [48] (4)
                          [64] For Lammotz [42] [43] (5)
                          [65] For Coders [44] [45] (5)
                          [66] RTFM etc. [46] [47] (5)
                     [61] C/C++/C# [49] [50] (4)
                     [62] Delphi [51] [52] (4)
                     [63] Other shit [53] [54] (4)
                [32] На иностранных языках [56] [57] (3)
           [6] Мультимедийные издания [59] [60] (2)
           [7] Музыка [61] [62] (2)
      [8] Коллекционирование [64] [129] (1)
           [9] Вещи знаменитостей, Автографы [65] [66] (2)
           [10] Военные вещи [67] [68] (2)
           [11] Игры: MtG, Pokemon и другие [69] [70] (2)
           [12] Киндер Сюрприз [71] [72] (2)
           [13] Коллекционное оружие [73] [74] (2)
           [14] Банкноты [75] [100] (2)
                [39] Австралия и Океания [76] [77] (3)
                [40] Азия [78] [79] (3)
                [41] Америка [80] [81] (3)
                [42] Россия и СССР [82] [93] (3)
                     [54] Госвыпуски до 1917 [83] [84] (4)
                     [55] Госвыпуски после 1917 [85] [86] (4)
                     [56] Лотереи, акции, облигации [87] [88] (4)
                     [57] Частные выпуски до 1922 [89] [90] (4)
                     [58] Частные выпуски после [91] [92] (4)
                [43] Африка [94] [95] (3)
                [44] Европа [96] [97] (3)
                [45] Страны СНГ [98] [99] (3)
           [15] Модели [101] [102] (2)
           [16] Открытки [103] [104] (2)
           [17] Спортивные карточки [105] [106] (2)
           [18] Жетоны, Медали, Значки [107] [124] (2)
                [46] Жетоны [108] [109] (3)
                [47] Памятные медали и знаки, Значки [110] [111] (3)
                [48] Воинские награды и знаки отличия [112] [121] (3)
                     [50] Россия до 1917 г. [113] [114] (4)
                     [51] Россия и СНГ после 1991 г. [115] [116] (4)
                     [52] СССР с 1917 до 1991 г. [117] [118] (4)
                     [53] Другие страны [119] [120] (4)
                [49] Памятные медали и знаки, Значки [122] [123] (3)
           [19] Фотографии, Письма [125] [126] (2)
           [20] Марки [127] [128] (2)
      [59] Услуги [130] [131] (1)

Выводим всех родителей для элемента: 65
SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM molotok A, molotok B WHERE B.cat_id='65' AND B.cat_left BETWEEN A.cat_left AND A.cat_right ORDER BY A.cat_left

[1] [1] [132] (0)
      [2] Книги, Видео, Музыка, CD [2] [63] (1)
           [5] Книги [29] [58] (2)
                [31] Компьютеры, Программирование, Интернет [40] [55] (3)
                     [60] PHP [41] [48] (4)
                          [65] For Coders [44] [45] (5)

Выводим ветку для элемента: 14
SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM molotok A, molotok B WHERE B.cat_id='14' AND A.cat_left >= B.cat_left AND A.cat_right <= B.cat_right ORDER BY A.cat_left

           [14] Банкноты [75] [100] (2)
                [39] Австралия и Океания [76] [77] (3)
                [40] Азия [78] [79] (3)
                [41] Америка [80] [81] (3)
                [42] Россия и СССР [82] [93] (3)
                     [54] Госвыпуски до 1917 [83] [84] (4)
                     [55] Госвыпуски после 1917 [85] [86] (4)
                     [56] Лотереи, акции, облигации [87] [88] (4)
                     [57] Частные выпуски до 1922 [89] [90] (4)
                     [58] Частные выпуски после [91] [92] (4)
                [43] Африка [94] [95] (3)
                [44] Европа [96] [97] (3)
                [45] Страны СНГ [98] [99] (3)

Выводим "приоткрытое" дерево для элемента: 44
SELECT *, IF (cat_left+1 < cat_right OR cat_level = 1, 1, 0) AS nflag FROM molotok WHERE cat_level=1 OR (cat_level=1 AND cat_left>1 AND cat_right<132) OR (cat_level=2 AND cat_left>64 AND cat_right<129) OR (cat_level=3 AND cat_left>75 AND cat_right<100) ORDER BY cat_left

      [2] Книги, Видео, Музыка, CD [2] [63] (1)
      [8] Коллекционирование [64] [129] (1)
           [9] Вещи знаменитостей, Автографы [65] [66] (2)
           [10] Военные вещи [67] [68] (2)
           [11] Игры: MtG, Pokemon и другие [69] [70] (2)
           [12] Киндер Сюрприз [71] [72] (2)
           [13] Коллекционное оружие [73] [74] (2)
           [14] Банкноты [75] [100] (2)
                [39] Австралия и Океания [76] [77] (3)
                [40] Азия [78] [79] (3)
                [41] Америка [80] [81] (3)
                [42] Россия и СССР [82] [93] (3)
                [43] Африка [94] [95] (3)
                [44] Европа [96] [97] (3)
                [45] Страны СНГ [98] [99] (3)
           [15] Модели [101] [102] (2)
           [16] Открытки [103] [104] (2)
           [17] Спортивные карточки [105] [106] (2)
           [18] Жетоны, Медали, Значки [107] [124] (2)
           [19] Фотографии, Письма [125] [126] (2)
           [20] Марки [127] [128] (2)
      [59] Услуги [130] [131] (1)

Заметьте, что ветки: 2, 42, 18 и 59 не открыты. То есть данный результат получился бы и при выводе для элемента 14. А если бы мы выводили "приоткрытое" дерево для элемента 42, тогда бы добавились его потомки четвертого уровня. Этот фикус можно заюзать для построения навигации по сайту, вообщем поэкспериментируйте.

Второй пример (ns_test2.php)
Представим что нам нужно вывести дерево одной таблицей как тут: http://molotok.ru/catalog/index.php?MIval=/catalog/default.app ( http://molotok.ru/catalog/index.php?MIval=/catalog/default.app ) Рисуем шаблон для Integrated Template(класс HTML_Template_IT) из PEAR.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>molotok sample</title>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
</head>

<body>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<!-- BEGIN t_data -->
  <tr>
    <!-- BEGIN t_inner -->
        <!-- BEGIN _twd --><td width="5%" align="center">*</td><!-- END _twd -->
        <!-- BEGIN _d -->
            <td<!-- BEGIN _ttd --> colspan="{_tcols}"<!-- END _ttd -->><!-- BEGIN _zag --><b>{header}</b><br><!-- END _zag -->
            <!-- BEGIN hdr0 --><a href="{lnk0}">enter category</a><!-- END hdr0 -->
            <!-- BEGIN _data --><!-- BEGIN dlm --> -:- <!-- END dlm --><a href="{lnk}">{tdata}</a><!-- END _data -->
            </td>
        <!-- END _d -->
    <!-- END t_inner -->
  </tr>
<!-- BEGIN t_spacer -->
  <tr>
    <td height="5"<!-- BEGIN _ts --> colspan="{max_lvl}"<!-- END _ts -->></td>
  </tr>
<!-- END t_spacer -->
<!-- END t_data -->
</table>
</body>
</html>

И рисуем код, переменная $max_lvl = 4; //MAX(cat_level) - 1 тоесть она меньше максимального уровня дерева на единицу. Мoжно выставить сразу или дописать вначале запрос и определить.

<?php

function connect_db()
{
    
mysql_connect("localhost", "root", "") or die("Can`t connect");
    
mysql_select_db("bidz") or die("Can`t select");
}


require_once(
"template_it.class.php");
connect_db();
$mod = new IntegratedTemplate();
$mod->loadTemplatefile("tree_tmpl.html");

$tbl = "molotok";
$sql = "SELECT  IF ( A.cat_level = 0, B.cat_left, A.cat_left ) AS cat, A.cat_level, A.cat_name AS name, B.cat_id, B.cat_name FROM ".$tbl." A INNER  JOIN ".$tbl." B ON ( ( B.cat_level = A.cat_level + 1 ) AND ( B.cat_left = B.cat_right - 1 ) AND B.cat_left BETWEEN A.cat_left AND A.cat_right )  WHERE ( A.cat_left != A.cat_right - 1) ORDER BY cat, B.cat_id";
print
$sql."<p>";
$res = mysql_query($sql);
if (
mysql_num_rows($res) == 0) die("Err (2): cat tree!");

//ВНИМАНИЕ $max_lvl требует настройки
$max_lvl
= 4; //MAX(cat_level) - 1
$dlm = false;
$i = 0;
$cat = -1;

while (
$row = mysql_fetch_assoc($res))
{
    if (
$cat != $row['cat'])
    {
        if (++
$i > 1) $mod->parse("t_data");
        
//t_inner
        
$mod->setCurrentBlock("t_inner");

        if (
$row['cat_level'] == 0)
        {
            if (
$max_lvl > 1) $mod->setVariable(array("_tcols" => $max_lvl, "max_lvl" => $max_lvl));
                else
$mod->touchBlock("t_spacer");
            
$mod->setVariable(array("header" => $row['cat_name'], "lnk0" => "?cat=".$row['cat_id']));
            continue;
        }

        
$cols = ($max_lvl + 1) - $row['cat_level'];
        
$dlm = true;
        
$cat = $row['cat'];

        if (
$row['cat_level'] > 1)
            for (
$i = 1; $i <= $row['cat_level']-1; $i++)
            {
                
< font color="#0000BB">$mod
->touchBlock("_twd");
                
< font color="#0000BB">$mod->parse("t_inner");
            }

        if (
$cols > 1) $mod->setVariable("_tcols", $cols);
        
$mod->setVariable("header", $row['name']);
        if (
$max_lvl > 1) $mod->setVariable("max_lvl", $max_lvl); else $mod->touchBlock("t_spacer");
    }

    if (
true) //$lvl < $row['cat_level']
    
{
        
//_data
        
$mod->setCurrentBlock("_data");
        if (
$dlm) $dlm = !$dlm;    else $mod->touchBlock("dlm");
        
$mod->setVariable(array("tdata" => $row['cat_name'], "lnk" => "?cat=".$row['cat_id']));
        
$mod->parse("_data");
    }
}

$mod->show();

?>

Не думаю что SQL запрос идеален, но в принципе он нам подходит. Запускаем всю эту колбасень...

SELECT IF ( A.cat_level = 0, B.cat_left, A.cat_left ) AS cat, A.cat_level, A.cat_name AS name, B.cat_id, B.cat_name FROM molotok A INNER JOIN molotok B ON ( ( B.cat_level = A.cat_level + 1 ) AND ( B.cat_left = B.cat_right - 1 ) AND B.cat_left BETWEEN A.cat_left AND A.cat_right ) WHERE ( A.cat_left != A.cat_right - 1) ORDER BY cat, B.cat_id

Книги, Видео, Музыка, CD
Журналы и газеты ( http://webscript.ru/?cat=3 ) -:- Мультимедийные издания ( http://webscript.ru/?cat=6 ) -:- Музыка ( http://webscript.ru/?cat=7 )
* Видео
DVD-диски ( http://webscript.ru/?cat=22 ) -:- Видеокассеты с неигровыми записями ( http://webscript.ru/?cat=23 ) -:- Видеокассеты с фильмами без перевода ( http://webscript.ru/?cat=25 )
* * Видеодиски
Комедии, Мелодрамы ( http://webscript.ru/?cat=33 ) -:- Семейное и детское кино ( http://webscript.ru/?cat=34 ) -:- Фантастика, Мистика, Ужасы ( http://webscript.ru/?cat=35 )
* * Видеокассеты с зарубежными фильмами
Комедии, Мелодрамы ( http://webscript.ru/?cat=36 ) -:- Семейное и детское кино ( http://webscript.ru/?cat=37 ) -:- Фантастика, Мистика, Ужасы ( http://webscript.ru/?cat=38 )
* Книги
Художественная литература ( http://webscript.ru/?cat=26 ) -:- Детская литература ( http://webscript.ru/?cat=27 ) -:- Дом, Семья, Досуг ( http://webscript.ru/?cat=28 ) -:- Естественные науки ( http://webscript.ru/?cat=29 ) -:- Искусство, искусствоведение ( http://webscript.ru/?cat=30 ) -:- На иностранных языках ( http://webscript.ru/?cat=32 )
* * Компьютеры, Программирование, Интернет
C/C++/C# ( http://webscript.ru/?cat=61 ) -:- Delphi ( http://webscript.ru/?cat=62 ) -:- Other shit ( http://webscript.ru/?cat=63 )
* * * PHP
For Lammotz ( http://webscript.ru/?cat=64 ) -:- For Coders ( http://webscript.ru/?cat=65 ) -:- RTFM etc. ( http://webscript.ru/?cat=66 )
Коллекционирование
Вещи знаменитостей, Автографы ( http://webscript.ru/?cat=9 ) -:- Военные вещи ( http://webscript.ru/?cat=10 ) -:- Игры: MtG, Pokemon и другие ( http://webscript.ru/?cat=11 ) -:- Киндер Сюрприз ( http://webscript.ru/?cat=12 ) -:- Коллекционное оружие ( http://webscript.ru/?cat=13 ) -:- Модели ( http://webscript.ru/?cat=15 ) -:- Открытки ( http://webscript.ru/?cat=16 ) -:- Спортивные карточки ( http://webscript.ru/?cat=17 ) -:- Фотографии, Письма ( http://webscript.ru/?cat=19 ) -:- Марки ( http://webscript.ru/?cat=20 )
* Банкноты
Австралия и Океания ( http://webscript.ru/?cat=39 ) -:- Азия ( http://webscript.ru/?cat=40 ) -:- Америка ( http://webscript.ru/?cat=41 ) -:- Африка ( http://webscript.ru/?cat=43 ) -:- Европа ( http://webscript.ru/?cat=44 ) -:- Страны СНГ ( http://webscript.ru/?cat=45 )
* * Россия и СССР
Госвыпуски до 1917 ( http://webscript.ru/?cat=54 ) -:- Госвыпуски после 1917 ( http://webscript.ru/?cat=55 ) -:- Лотереи, акции, облигации ( http://webscript.ru/?cat=56 ) -:- Частные выпуски до 1922 ( http://webscript.ru/?cat=57 ) -:- Частные выпуски после ( http://webscript.ru/?cat=58 )
* Жетоны, Медали, Значки
Жетоны ( http://webscript.ru/?cat=46 ) -:- Памятные медали и знаки, Значки ( http://webscript.ru/?cat=47 ) -:- Памятные медали и знаки, Значки ( http://webscript.ru/?cat=49 )
* * Воинские награды и знаки отличия
Россия до 1917 г. ( http://webscript.ru/?cat=50 ) -:- Россия и СНГ после 1991 г. ( http://webscript.ru/?cat=51 ) -:- СССР с 1917 до 1991 г. ( http://webscript.ru/?cat=52 ) -:- Другие страны ( http://webscript.ru/?cat=53 )
Услуги
enter category ( http://webscript.ru/?cat=59 )

На этом пока все, не судите строго и разрешите откланяться :) Если возникнут вопросы, мыльте, я всем отвечу.