Построение одной ветке от текущего id_cat до самого верхнего.

[St.]

Помогите пожалуйста с правильным решением!
Интересуют еще примеры для решения этой задачи, т.е. оптимизация, скорость выполнения...
Туго у меня с этими ветками и деревьями.

У меня получилось так (см. ниже).

Входящий идентификатор категории/подкатегории в $id_cat.
Если $id_cat = 100, то получим на выходе: Разделы > Раздел 1.
Если $id_cat = 102, то получим на выходе: Разделы > Раздел 3 > Раздел 3.1.

// Построение одной ветке от текущего id_cat до самого верхнего.

// Пример.
//    Разделы > Раздел 3 > Раздел 3.1

/*
id_cat  parent_id  title
    98          0  Разделы
   100         98  Раздел 1
   101         98  Раздел 3
   102        101  Раздел 3.1
   106         98  Раздел 2

*/

// Получаем все id_cat и parent_id.
$query = "SELECT `id_cat`, `parent_id` FROM dl_category";
$result = mysql_query($query);

// Все id_cat и parent_id в массив.
while($row = mysql_fetch_assoc($result))
   {
   $arr_id_cat_all[] = $row['id_cat'];
   $arr_parent_id_all[] = $row['parent_id'];
   }

mysql_free_result($result);

// Получаем ветку id_cat'ов.
// От текущего id_cat до самого верхнего (до нулевого).
if ($id_cat != '0')
   {
   $id_cat_tmp = $id_cat;
   for ($x = 0; $x < count($arr_id_cat_all); $x++)
      {
      if ($arr_id_cat_all[$x] == $id_cat_tmp)
         {
         // id_cat'ы в массив $branch_id_cat[].
         $branch_id_cat[] = $id_cat_tmp;
         // Родитель.
         $id_cat_tmp = $arr_parent_id_all[$x];

         if ($id_cat_tmp != '0')
            {
            // Нет, еще не все.
            $x=0;
            }
            else
            {
            // Все id_cat'ы уже в массиве,
            // в такой последовательности: 54321;
            $branch_id_cat[] = $id_cat_tmp;

            // Поменять местами 54321 на 12345.
            for ($x = count($branch_id_cat) - 1; $x >= 0; $x--)
               {
               $new_branch_id_cat[] = $branch_id_cat[$x];
               }

            // Все...
            break;
            }
         }
      }
   }
   else
   {
   $new_branch_id_cat[] = '0';
   }

// Сделать: 1,2,3,4,5
$string_branch = implode(",", $new_branch_id_cat);

[laimas]

У вас даже запрос не предполагает выборку именно дерева.

1) Традиционное получение дерева - рекурсия в запросе.

2) Рекурсия, это плохо и ее можно избежать - запрос формируется как подключение таблиц потомков.

3) NESTED SETS - иное описание дерева в базе данных.

[St.]

3) NESTED SETS - иное описание дерева в базе данных.

Спасибо. Попытаюсь разобраться.

[St.]

laimas!
Если вы еще здесь? Можно где-то почитать об этом:

2) ...запрос формируется как подключение таблиц потомков.

Спасибо.

NESTED SETS
Многое непонятно...

[laimas]

Я здесь, но на данный момент нет времени писать много. Позже, и только теоретические выкладки, хотя это не означает, что это гольная теория. )

[St.]

А можно как-то к PHP подключить свой модуль, ну скажем написаный на ассемблере?
Это чтобы решить проблемы связанные с рекурсией.

Дополнение.
Вот ответ: exec в PHP, читать здесь: http://php.net/manual/ru/function.exec.php и пусть рекурсия вас не пугает.
А дальше - есть Си, есть ассемблер...

[laimas]

А можно как-то к PHP подключить свой модуль, ну скажем написаный на ассемблере?

На Ассемблере? Ну тогда уж сразу набить код на перфокарте

РНР язык высокого уровня, но для каждой платформы свой интерпретатор. А Ассемблер вообще привязан к системе команд процессора. Расширения для РНР пишут на С.

Рекурсия для выборки дерева, это множество запросов к базе и никаким Ассемблером этого не исправить.

Но можно обойтись единственным запросом, но с условием, что на глубину вложения есть ограничение. Если глубина вложения небольшая (например меню сайта, где большая глубина вложения вряд ли уместна), то формируется запрос, который прост по сути - в запросе подключается таблица (в которой хранится дерево) числом равным максимальному уровню вложения минус 1, по условию равенства parent ее записей id предыдущего подключения:

SELECT label1.fields, label2.fields, label3.fields, ... FROM table label1
LEFT JOIN table label2
ON label2.parent = label1.id
LEFT JOIN table label3
ON label3.parent = label2.id
.....
WHERE ....
ORDER BY ....

где label формируемые псевдонимы подключаемых таблиц и их полей. Результатом запроса будут записи сгруппированные по дереву, которые в цикле можно разобрать формируя html-код меню или иное требуемое.

[St.]

Спасибо за информацию.
Насчет ассемблера, Вы не правы...

Дополнение.
Рекурсию можно отдать через exec программе написаной на си или ассемблере.
Вот небольшой (маленький) пример как это выглядет:

echo exec("buildbranch 102", $resultarr);

где buildbranch - программа.
102 - идентификатор, на основе которого нужно построить ветку.
Результат вернеться в массив $resultarr.

Программа которая написана в самом вверху переписуется на си, если нужно получить максимальную производительность - ее пишут на ассемблере.

Это только маленький и неполный пример, как это может быть.

Немного компьютерной истории.
Процессор 3мГц, гибкий диск 800кб, на нем англо-русский и руско-английский словарь (один символ - один байт, 1024 байта - 1кб).
Так вот, суть этой байды...
Перевод слов мгновенный.
Улыбнитесь! Это ассемблер.


Ну да ладно.

П.С.
Что говорят специалисты по поводу ассемблера?
"На нем можно одновременно чистить зубы и писять в ведро".

[laimas]

если нужно получить максимальную производительность - ее пишут на ассемблере.

Вот об этом не надо рассказывать и что такое Ассемблер тоже, знаем, увлекались.

Дело не в Ассемблере, а в запросах к базе, это вы понимаете? Если писать традиционно, как это и делается, то это будут рекурсивные запросы к базе. От такого третирования базы не спасет не Ассемблер ни что иное.

Можно выбрать все скопом, все переложить в массив, а уже рекурсивным на РНР строить ветви. Впрягать сюда еще и Ассемблер, это кошмар. Кроме рекурсии есть еще два подхода, думайте и выбирайте.

[St.]

Дело не в Ассемблере, а в запросах к базе, это вы понимаете? Если писать традиционно, как это и делается, то это будут рекурсивные запросы к базе.

MySQL не предназначен для подкатегорий! Нет у него команд для этого!
Для этого существуют другие субд!

Программа, которая написана вверху, мной была переписана на Си.
Что Вам сказать?

От такого третирования базы не спасет не Ассемблер ни что иное.

Вот, вот... Догадайтесь сами, что Вам можно сказать...

Метод NESTED SETS, хорош для выбивания денег из любознательных.
Я мысленно прохожусь по порядку от 1 до 32 и не мого понять кто будет обнавлят левый и правый ключ после добавления узла? Тема не раскрыта полностью. Писать автору я не буду, он может денег попросить.

Вот сама программа (см. ниже).
Ладно, шутки-шутками, а посуществу, программа написанная на PHP вверху, дохнет на 3000 категорий с десятком подкатегорий, плюс одна подкатегория имеет 30 вложенных подкатегорий. Так вот, на этих 30 подкатегориях время генерации странцы приблизительно 0.45 сек.
Что касается Си - скушал и не подавился...
Комп древней с установленной ОС FreeBSD.

Вот еще мысль: Ассемблер, Си, Js - браузерные шахматы.
Правда выиграть у компьютера невозможно...

// Это Си не путать с PHP.
#include <stdio.h>
#include <string.h>
#include <stdlib.h> // exit(1);

#define N 80

//
// Чтение двух столбцов текстового файла в два массива.
//    Пример текстового файла:
//       ... ...
//       234 560
//       103 789
//       456 232
//       ... ...
//
int i = 0, k = 0, j =0 , j_1 = 0, j_2 = 0;
	long int current_id_cat, current_id_cat_tmp;
		long int array_branch_id_cat[8192];
			long int array_new_branch_id_cat[8192];

int main(int argc, char* argv[])
{
// Получаем текущий идентификатор категории.
current_id_cat = atoi(argv[2]);

FILE *file = NULL;
    // В argv[1] путь с именем файла идентификаторов.
    file = fopen(argv[1], "r");

if(file == NULL)
    {
    // Ошибка открытия файла.
    puts("Error opening file!");
    exit(1); // Завершение с кодом ошибки 1.
    }

char array_1[8192][N]; // id_cat.
char array_2[8192][N]; // parent_id.
char line[N];

    while ( fgets (line, N, file) )
        {
            j_1 = 0; j_2 = 0; k = 0;

            while(1)
                {
                // Останов, если нет пробела.
                if (k > N) break;

                // Останов, если найден пробел.
                if (line[k] == ' ')break;
                    {
                    array_1[i][j_1] = line[k];
                    }

                j_1++;
                k++;
                }

            // Пропустить пробел.
            k++;

            while(1)
                {
                // Останов, если нет конца строки.
                if (k > N) break;

                // Останов, если найден конец сторки.
                if (line[k] == '\n')break;
                    {
                    array_2[i][j_2] = line[k];
                    }

                j_2++;
                k++;
                }

            i++;
        }

    fclose(file);

// Решаем вопрос с веткой.
if (current_id_cat != 0)
    {
    // Находим ветку.
    k = 0;
    current_id_cat_tmp = current_id_cat;

    for (j = 0; j < i; j++)
        {
        if (atoi(array_1[j]) == current_id_cat_tmp)
            {
            // id_cat'ы в массив array_branch_id_cat[].
            array_branch_id_cat[k] = current_id_cat_tmp;
            k++;

            // Родитель.
            current_id_cat_tmp = atoi(array_2[j]);

            if (current_id_cat_tmp != 0)
                {
                // Нет, ещё не все.
                j = 0;
                }
                else
                {
                // Все id_cat'ы уже в массиве,
                // в такой последовательности: 54321;
                array_branch_id_cat[k] = current_id_cat_tmp;
                k++;

                // Поменять местами 54321 на 12345.
                i = 0;
                for (j = k-1; j >= 0; j--)
                    {
                    array_new_branch_id_cat[i] = array_branch_id_cat[j];
                    i++;
                    }

                // Вот они.
                for (j = 0; j < k; j++)
                // В вывод их, PHP потом их заберёт...
                printf("%d\n", array_new_branch_id_cat[j]);

                // Всё.
                break;
                }
            }
        }
    }
    else
    {
    // Текущий id_cat равен нулю.
    // В вывод...
    printf("%d\n", current_id_cat);
    }

return 0;
}

П.С.
Вы неправильно батон крош... Ну это, ломаете...
Надеюсь, админы не удалят мою писанину...