Многомерные деревья (сново)

[Rynor]

2 su1d:
а что рекурсия (level-sublevel без left и right) совсем плоха?

 

[Макс]

но это вроде это кишки mysql а не алгоритм деревьев пхп

при чем тут ПХП ? Алгоритмы чаще всего не зависят от языка реализации. b-trees - это алгоритм построения индексов в БД (не только mysql). Индексы хранятся в виде дерева, собственно поэтому сюда и написали об этом алгоритме.

зачем left, right, level?

ты с алгоритмом nested sets разобрался ? В этих полях хранится структура дерева. Вообще-то level необязателен, но с ним просто удобнее.

 

[WMix]

ты с алгоритмом nested sets разобрался ?

в общем да хотя вопрос с каким из них только в топике 2 обговаривали

id ето понятно
left согласен нужен
right если это id то ясно а если нет то что?
я спросил как тема называлась? // я бы почитал мы бы на одном языке говорили

level необязателен, но с ним просто удобнее.

мои учителя говорили что так делать нельзя
вот тут тоже вопрос : с одной стороны память с другой процессор на что наплевать?
я за чистые данные (в данном случии у дерева) если не прав обьясните начинающему

b-trees - это алгоритм построения индексов в БД

я знаю (видел что в оракле тоже использован), я говорил что это не для пхп те к теме не относилось

а что рекурсия (level-sublevel без left и right) совсем плоха?
да это я и спрашивал те как лучше реализовать

ультратрее неплох но не то тк там нет реализа mysql те древо хапается целиком а потом сортируется

а надо запрос верно составить скажем учесть дату во всех подлевилах и зацепить 10 актуальных каждого подлевила и с корнем

зы: подлевел может быть на 10 или 20 уровне

 

[Макс]

вот тут тоже вопрос : с одной стороны память с другой процессор на что наплевать?
я за чистые данные (в данном случии у дерева) если не прав обьясните начинающему

level в некоторых запросах очень даже помогает. ИМХО одно "лишнее" int поле - это не страшно. Что касается "чистоты данных" - то я не стесняюсь создавать лишние поля в таблицах если это повысит производительность

right если это id то ясно а если нет то что?

нет не ID, это правое смещение. На http://dev.e-taller.net/dbtree есть статьи по этой теме.
В одной нарисовано "дерево" с расставленными левыми и правыми смещениями. Я как эту каринку увидел - только тогда понял, что представляют из себя эти смещения.

 

[WMix]

ага понятно
----------------------------------
http://dev.e-taller.net/dbtree

элемент 1 [1] [12]
|
+ - элемент 2 [2] [9]
| |
| + - элемент 3 [3] [4]
| + - элемент 4 [5] [8]
| |
| + - элемент 4.1 [6] [7]
|
+ - элемент 5 [10] [11]
в моём первом примере он id был (почему нет они по порядку и единственные)
ну конечно о превязанных таблицах надо думать

в данной id, left, right, level структуре два поля лишние (для удобства кода)

вот поэтому я и ищу другой алгоритм

Rynor мы стобой еденомышленники

 

[Rynor]

но есть проблема с рекурсией вроде как
как быстро найти родителя для дальнего дитя...
я еще код не писал, некогда, но вроде как все той же рекурсией в обратную сторону перебор...

 

[Crazy]

Все структуры данных, реализующие деревья и предполагающие использование рекурсии плОхи тем, что неизбежно возникают траблы с БД: SQL нерекурсивен (в общем случае)

 

[WMix]

да кстати

Rynor и тебе посоветую другой алгоритм

я тут подначитался подумал и понял все прелести структуры nested sets

всё дерево обойденно уже при запросе (чаще читают чем пишут)

если правильно базу раскидать (без id не обойтись) (скажем для форума вопрос как корень писать) то и на запись времени много не надо

а с рекурсией при каждом чтении процесор напрягать

так а теперь вопросы

какие классы реализируют nested sets дерево?
о чём надо подумать заранее при реализе дерева?

 

[Altex]

--- ответ на первый самый постинг ---
-------------------------------------------------

<HTML>
<BODY>

<?

// Класс с описанием формата начальных данных
class tree_element {
var $name; // Название элемента
var $id; // Его идентификатор
var $pid; // Идентификатор его родителя

// Конструктор класса
function tree_element($name,$id,$pid) {
$this->name=$name;
$this->id=$id;
$this->pid=$pid;
return 0;
}
}

// Начальные данные
$tree[]=new tree_element("Атлоны XP",1,7);
$tree[]=new tree_element("Тачки",2,0);
$tree[]=new tree_element("Русские",3,2);
$tree[]=new tree_element("ВАЗ",4,3);
$tree[]=new tree_element("Иностранные",5,2);
$tree[]=new tree_element("BMW",6,5);
$tree[]=new tree_element("Компы",7,0);
$tree[]=new tree_element("Селероны P4",8,7);
$tree[]=new tree_element("Mercedes",9,5);

// Массив выходных значений ф-ии get_children
$result=array();

// Ф-я возвращает идентификаторы элементов,
// пренадлежащих элементу с заданным идентификатором
function get_children($id) {
global $tree;
global $result;
$result=array(); // Очищаем массив выходных значений
for ($i=0; $i<count($tree); $i++) {
if ($tree[$i]->pid==$id) {
$result[]=$tree[$i]->id;
}
}
return 0;
}

// Ф-я построения ветки дерева, начиная с элемента
// с заданным идентификатором
function get_branch($id) {
global $tree;
global $result;
get_children($id);
$temp=$result;
if ($id) echo "<li>".$tree[$id-1]->name."<ul>\n";
for ($i=0; $i<count($temp); $i++) {
get_branch($temp[$i]); // Рекурсия
}
if ($id) echo "</ul>\n";
return 0;
}

// Построение дерева, начиная с элемента
// с идентификатором '0'
echo "<ul>";
get_branch(0);
echo "</ul>";

?>

</BODY>
</HTML>

 

[Макс]

какие классы реализируют nested sets дерево?

http://dev.e-taller.net/dbtree/phpDbTree.zip

о чём надо подумать заранее при реализе дерева?

насколько часто будет обновляться дерево,
насколько (реально) оно может быть "глубоким"
насколько обосновано использование алгоритма nested sets или id->parent_id
какие операции будут проводиться с деревом
(это все ИМХО)

 

[Макс]

кстати только-что увидел что в Pear появился класс
DB::NestedSet
(пока что beta-версия)

 

[WMix]

спасибо