Меню
Что нового?

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

Макс

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

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

WMix

герр M:)ller
Партнер клуба
ты с алгоритмом nested sets разобрался ?
Нажмите для раскрытия...
в общем да хотя вопрос с каким из них только в топике 2 обговаривали

id ето понятно
left согласен нужен
right если это id то ясно а если нет то что?
я спросил как тема называлась? // я бы почитал мы бы на одном языке говорили
level необязателен, но с ним просто удобнее.
Нажмите для раскрытия...
мои учителя говорили что так делать нельзя
вот тут тоже вопрос : с одной стороны память с другой процессор на что наплевать?
я за чистые данные (в данном случии у дерева) если не прав обьясните начинающему
b-trees - это алгоритм построения индексов в БД
Нажмите для раскрытия...
я знаю (видел что в оракле тоже использован), я говорил что это не для пхп те к теме не относилось

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

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

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

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

Макс

Старожил PHPClub
вот тут тоже вопрос : с одной стороны память с другой процессор на что наплевать?
я за чистые данные (в данном случии у дерева) если не прав обьясните начинающему
Нажмите для раскрытия...
level в некоторых запросах очень даже помогает. ИМХО одно "лишнее" int поле - это не страшно. Что касается "чистоты данных" - то я не стесняюсь создавать лишние поля в таблицах если это повысит производительность

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

WMix

герр M:)ller
Партнер клуба
ага понятно
----------------------------------
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

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

Crazy

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

WMix

герр M:)ller
Партнер клуба
да кстати

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

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

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

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

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

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

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

Altex

Новичок
--- ответ на первый самый постинг ---
-------------------------------------------------
PHP: 
<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>
 

Макс

Старожил PHPClub
какие классы реализируют nested sets дерево?
Нажмите для раскрытия...
http://dev.e-taller.net/dbtree/phpDbTree.zip
о чём надо подумать заранее при реализе дерева?
Нажмите для раскрытия...
насколько часто будет обновляться дерево,
насколько (реально) оно может быть "глубоким"
насколько обосновано использование алгоритма nested sets или id->parent_id
какие операции будут проводиться с деревом
(это все ИМХО)
 
Войдите или зарегистрируйтесь для ответа.
Сверху