Каждый разработчик рано или поздно сталкивается с проблемой хранения и выборки данных в виде дерева. Самый распространенный вариант - наличие у потомков ссылки на родителя. У него есть свои плюсы - это простота изменения дерева (удаление, добавление, перенос веток). Однако есть и свои минусы - это ресурсоемкие и медленные алгоритмы выборки. Как правило это рекурсивные функции с множеством мелких выборок из БД, либо одна выборка с последующей циклической и рекурсивной обработкой и упорядочиванием данных.

Выборка дерева

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

<?php
function display_tree($root) {
    // Получаем левое и правое числа ветки, начинающейся с $root
    $result = mysql_query('
        SELECT lft, rgt FROM tree WHERE title="'.$root.'"
    ');
    $row = mysql_fetch_array($result);

    // Начинаем с пустого стека правых чисел
    $right = array();

    // Теперь  выбираем всех потомков ветки, начинающейся с $root
    $result = mysql_query('
        SELECT title, lft, rgt 
        FROM tree 
        WHERE lft BETWEEN '.$row['lft'].' AND '.$row['rgt'].' 
        ORDER BY lft ASC
    ');

    // Отображаем каждую строку
    while ($row = mysql_fetch_array($result)) {
        // Проверим стек, есть ли он
        if (count($right)>0) {
            // Проверим, надо ли нам уже удалить ветку из стека
            while ($right[count($right)-1] < $row['rgt']) {
                array_pop($right);
            }
        }

        // Отобразим ветки с нужным отступом
        echo str_repeat(' ', count($right))
        echo $row['title']."\n";

        // Добавим элемент в стек
        $right[] = $row['rgt'];
    }
}
?>

Путь к любому элементу дерева

SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

+-------+
| title |
+-------+
| Food  |
| Fruit |
| Red   |
+-------+

Сколько потомков?

Кол-во детей = (rgt – lft - 1) / 2

Автоматический обход дерева

<?php
function rebuild_tree($parent, $left) {
    // Правое значение узла - это на 1 увеличенное левое знначение
    $right = $left+1;
    
    // Берем всех детей узла
    $result = mysql_query('
        SELECT title FROM tree WHERE parent="'.$parent.'"
    ');
    while ($row = mysql_fetch_array($result)) {
        // Рекурсивно вызываем эту функцию для каждого потомка
        // $right - это текущее rgt, увеличенное ф-ей rebuild_tree
        $right = rebuild_tree($row['title'], $right);
    }

    mysql_query('
        UPDATE tree SET lft='.$left.', rgt='.$right.' 
        WHERE title="'.$parent.'"
    ');

    // Вернем правое значение узла +1
    return $right+1;
}
?>

rebuild_tree('Food',1);

Добавление узла

UPDATE tree SET rgt=rgt+2 WHERE rgt>=6;
UPDATE tree SET lft=lft+2 WHERE lft>=6;

Food
 Fruit
   Red
     Cherry
     Strawberry
   Yellow
     Banana
 Meat
   Beef
   Pork

Заключение