каждый узел фактически указывает на список узлов-предков. у братьев это идентичные списки. когда мы добавляем узлу первое дитя, мы формирует для этого дитя список предков, который состоит из самого узла к которому добавляют дитя и всех его предков.а уже добавляя к нему братьев мы просто копируем указатель на список предков.
Народ, появилась задачка, для которой нужно реализовать дерево в таблице. Дерево будет являться каталогом с произвольной вложенностью (на деле дальше 5-ого уровня вряд-ли дойдёт, но всё же и это тоже возможно). К этой структуре будут привязываться миллионы записей, прявязать запись можно к любому элементу любого уровня (к рутовому тоже), даже если у этого элемента есть дети. Планируеться высокая нагрузка (и работать всё это будет на кластере, поэтому служебных данных должно быть минимально на столько, на сколько это возможно), добавляться записи будут очень часто и много. Подскажите оптимальный вариант пожайлуста (переносить юзлы нельзя - их можно только создать или удалить, при этом при удалении все записи удаляемого узла и его потомков присваиваються родителю; все узлы-дети становяться детями родительского узла (либо они вообще остаються вне дерева)
Psih Не слушай его, он тебе насоветует если записи будут отдельно, дерево отдельно, то вводить дополнительно третью таблицу для связей - крах для нагруженной системы. Если само дерево категорий будет сравнительно небольшим, и изменяться редко - Nested Sets подходят идеально.
1. многомилионный каталог изменяется редко, но метко 2. откуда ты взял третюю таблицу??? в моей схеме только две таблицы: таблица данных и таблица связей. третяя таблица предначена только для формирования уникальных идентификаторов родительских групп. в выборках она не учавствует вообще. при изменениях её влияние стремится к нулю. более того, я ещё подумал и готов выложить третюю редакцию если в кратце, то в качестве "уникальных идентификаторов родительских групп" может выступать сам родитель. таким образом мы убиваем двух зайцев: у нас есть и связи "родитель-ребёнок" и связи "предок-потомок". если развёрнуто, то логика такая: первым делом реализуем классическую таблицу смежностей. вторым - добавляем таблицу "потомственных связей", где для каждого узла не являющегося листом (имеющего от 1 ребёнка) задаются связи его ид с ид его предков, плюс - связь его с им же (можно и без этого, но тогда во все выборки придётся добавлять дополнительное условие). выборки получаются примерно такими же, как и в предыдущем варианте. плюс, мы можем быстро выбирать детей и родителя.
dark-demon Третья таблица - это сами записи (содержимое каталога), частью каталога они не являются, и судя по всему, у них будут другие совсем атрибуты. "в выборках она не учавствует вообще" - а зачем она тогда вообще нужна? :shock:
Народ, давайте мож какие-то конкретные предложения? К примеру хотя бы структуру таблиц, дальше то я сам разберусь. Прост реально надо и было бы хорошо если бы опытные люди показали хороший пример (а я не настолько туп, что бы применить самому не подумав)
почему содержимое каталога не является частью каталога? уже не нужно читай третюю редакцию ну думай выбор-то не особо и большой... таблицы смежности или вложенные множества. плюс их модификации в том числе и моя. плюсы и минусы тебе известны - примеряй на свою проблему
dark-demon Потому что структура данных различается. Каталог - одна структура (id, parentid и название), записи - другая (например, для каталога сайтов - id, catid, URL, название, ключевики и пр.) К тому же сайт не должен находиться внутри другого сайта, он должен находиться внутри каталога. По крайней мере я так понял задачу.
Psih, могу поделиться своей либой для работы с бинарными деревьями. Мне самому интересны результаты её работы в нагруженном приложении. Надо?
ONK Мог бы сразу выложить, я бы заюзал Ибо в любом случае надо будет перебирать кучу вариантов пока достигну оптимального. Потому что всё это работать будет на кластере, а это ещё более строгие ограничения на запросы чем на обычную базу (работает то всё за исключением FULLTEXT SEARCH на нём, но вот кое-какие вещи работают в в разы а то и десятки раз медленее чем в обычной базе, так что приходиться извращаться так, что мама не горюй)
Посмотрел код библиотеки. В среднем требуется 5 sql запросов при модификации структуры дерева + 3 запроса проверки структуры таблицы от которых можно избавиться (исполняются в конструкторе объекта). Работа с базой данных у меня идёт через собственный "драйвер", её придётся поправить. Назначение библиотеки - поддержка служебной таблицы связей для некой таблицы, хранящей древовидную структуру. код: PHP: <?php class Tree_helper_table{ function Tree_helper_table(&$oDb,$sTable,$sChild_cl,$sParent_cl){ global $CCSIS_NS; $this->db = $oDb; if(!$this->db->getOne("SHOW tables LIKE '".$sTable."'")){ $SQL = "CREATE TABLE ".$sTable." ( ".$sChild_cl." int(12) NOT NULL default '0', ".$sParent_cl." int(12) NOT NULL default '0', KEY k1 (".$sChild_cl."), KEY k2 (".$sParent_cl.")) TYPE=MyISAM"; $this->db->query($SQL); if(!$this->db->getOne("SHOW tables LIKE '".$sTable."'")){ return; } } if(!$this->db->getOne("SHOW COLUMNS FROM `".$sTable."` LIKE '".$sChild_cl."'")){ return; } if(!$this->db->getOne("SHOW COLUMNS FROM `".$sTable."` LIKE '".$sParent_cl."'")){ return; } $this->table = $sTable; $this->child = $sChild_cl; $this->parent = $sParent_cl; } function get_parents($iId){ global $CCSIS_NS; $aParent_ids = array(); if(!empty($this->table)){ $SQL = "SELECT ".$this->parent." FROM `".$this->table."` WHERE ".$this->child." = '%d'"; $oResult = $this->db->safe_query($SQL,$iId); if($oResult->numRows() > 0){ while($aRow = $oResult->fetchRow()){ $aParent_ids[] = $aRow[0]; } } } return $aParent_ids; } function get_children($iId){ global $CCSIS_NS; $aChaild_ids = array(); if(!empty($this->table)){ $SQL = "SELECT ".$this->child." FROM `".$this->table."` WHERE ".$this->parent." = '%d'"; $oResult = $this->db->safe_query($SQL,$iId); if($oResult->numRows() > 0){ while($aRow = $oResult->fetchRow()){ $aChaild_ids[] = $aRow[0]; } } } return $aChaild_ids; } function move_to($iId,$iNew_parent_id = 0,$bAS_a_child = 0){ global $CCSIS_NS; if(!empty($this->table)){ $aChaild_ids = $this->get_children($iId); $aParent_ids = $this->get_parents($iId); $aNew_Parent_ids = $this->get_parents($iNew_parent_id); $aChaild_ids[] = $iId; if($bAS_a_child && $iNew_parent_id != 0){ $aNew_Parent_ids[] = $iNew_parent_id; } if(count($aParent_ids)){ $this->db->query("DELETE FROM `".$this->table."` WHERE ".$this->child." IN(".implode(',',$aChaild_ids).") AND ".$this->parent." IN(".implode(',',$aParent_ids).")"); } if(count($aNew_Parent_ids)){ $bEmpty = 1; $SQL = "INSERT INTO `".$this->table."` (".$this->child.",".$this->parent.")VALUES"; foreach($aNew_Parent_ids AS $k => $v){ foreach($aChaild_ids AS $iChid){ if($bEmpty){ $SQL .= "(".$iChid.",".$v.")"; $bEmpty = 0; }else{ $SQL .= ",(".$iChid.",".$v.")"; } } } $this->db->query($SQL); } } } function remove($iId){ global $CCSIS_NS; if(!empty($this->table)){ $aChaild_ids = $this->get_children($iId); $aParent_ids = $this->get_parents($iId); $sWehere_segment = ""; if(count($aChaild_ids)){ $sWehere_segment = $this->child." IN('".implode(',',$aChaild_ids)."')"; } if(count($aParent_ids)){ if($sWehere_segment != ''){ $sWehere_segment .= " AND ".$this->parent." IN('".implode(',',$aParent_ids)."')"; }else{ $sWehere_segment = $this->parent." IN('".implode(',',$aParent_ids)."')"; } } if($sWehere_segment != ''){ $this->db->query("DELETE FROM `".$this->table."` WHERE ".$sWehere_segment); } $this->db->safe_query("DELETE FROM `".$this->table."` WHERE ".$this->child." = '%1\$d' OR ".$this->parent." = '%1\$d'",$iId); } } } ?> пример использования: PHP: $oHelper_table = new Tree_helper_table($CCSIS_NS->db,$CCSIS_NS->CNF['TAB_PREF'].'_mod_relations','mod_id','parent_mod_id'); //Добавление нового потомка к существующему узлу (если $mod_id - новый идентификатор) или перенос существующей ветки на новое место (ветка начинается с $mod_id и переносится к узлу $parent_id, если третий параметр 1, то как потомок $parent_id). $oHelper_table->move_to($mod_id,$parent_id,1); //удаление узла. После удаления все потомки узла становятся прямыми потомками узла, которому принадлежал удаляемый узел. $oHelper_table->remove($mod_id); Предполагается, что работа с таблицей, в которой хранится структура дерева производится параллельно с операциями по модификации таблицы отношений. В результате мы имеем две таблицы, связывая которые можно делать очень эффективные выборки предков и потомков относительно произвольного узла дерева. Чувствую, что не очень понятно и полно описал, но пока незнаю что дополнить. Может примерами выборки ветвей и поиском пути к корню со связыванием таблиц? Вобщем жду вопросы. -)
dark-demon, вопрос в том, какие альтернативы. Если требуется такая функциональность, то аналог только NS, а этот алгоритм просто завалит сервер на дереве в десяток тысяч элементов. К том-же 5 запросов это только модификация отношений элементов. Простые выборки - 1 очень эффективный запрос. Вот вторая библиотека для безрекурсивной выборки бинарных деревьев. Позволяет воссоздавать в виде многомерного массива объектов древовидные структуры из объектов несущих полезную информацию любого типа. Помимо этого библиотека имеет инструмент "достройки" дерева для реализации постраничной навигации по древовидной структуре, и инструмент связывание с корнем ветвей принадлежащих не найденным узлам. PHP: class CCSIS_Node{ var $child = array(); var $aChild_ids = array(); var $id; var $property; function CCSIS_Node($id,$prop){ $this->id = $id; $this->property = $prop; } function prop_replace($prop){ $this->property = $prop; } function add_child(/*CCSIS_Node */&$child){ if(empty($this->aChild_ids[$child->id])){ $this->child[] = &$child; $this->aChild_ids[$child->id] = 1; } } } class CCSIS_Tree{ var $aTree = array(); var $aTree_ids = array(); var $aNodes = array(); var $aNeeded = array(); var $aChecked = array(); function add_node($id,$prop,$parentID){ if(!empty($this->aNodes[$id])){ $node = &$this->aNodes[$id]; $node->prop_replace($prop); if(isset($this->aNeeded[$id])){ unset($this->aNeeded[$id]); } }else{ $node = new CCSIS_Node($id,$prop); $this->aNodes[$id] = &$node; } if(empty($parentID)){ if(empty($this->aTree_ids[$id])){ $this->aTree[] = &$this->aNodes[$id]; $this->aTree_ids[$id] = 1; } } if(!empty($this->aNodes[$parentID])){ $parent_node = &$this->aNodes[$parentID]; $parent_node->add_child($node); }else{ if($parentID){ $parent_node = new CCSIS_Node($parentID,null); $this->aNodes[$parentID] = &$parent_node; $parent_node->add_child($node); $this->aNeeded[$parentID] = 1; } } } function get_needed(){ $aTmp = array_keys(array_diff_assoc($this->aNeeded,$this->aChecked)); $this->aChecked = $this->aNeeded; return $aTmp; } function complete_tree(){ foreach($this->aNeeded AS $k => $v){ foreach($this->aNodes[$k]->child AS $node){ $this->aTree[] = &$this->aNodes[$node->id]; } } } } Пример использования: Выдрано из рабочего кода, строящего дерево с отношением node_id -> parent_id без вспомогательных таблиц связей. PHP: $oTree = new CCSIS_Tree(); $oResult = $CCSIS_NS->db->safe_query("SELECT a.message_id,a.parent_mid,a.create_date,a.author_user_id,SUBSTRING(a.message_text,1,%2\$d),b.name,a.mod_flag FROM `%1\$s_messages` a LEFT JOIN `%1\$s_user_names` b ON(b.name_id = a.author_name_id) WHERE a.topic_id = '%4\$d' ORDER BY a.parent_mid,a.message_id LIMIT %3\$d",$CONFIG['TAB_PREF'],$CONFIG[108],$CONFIG[107],$CCSIS_NS->tid); if($oResult->numRows() > 0){ while ($row = $oResult->fetchRow()){ if($row[6] == 1 || CCSIS::check_mod_priv(47,$CCSIS_NS->gid,$CCSIS_NS->fid)){ $oTree->add_node($row[0],$row,$row[1]); } } while ($aNeeded = $oTree->get_needed()){ $oResult = $CCSIS_NS->db->safe_query("SELECT a.message_id,a.parent_mid,a.create_date,a.author_user_id,SUBSTRING(a.message_text,1,%2\$d),b.name,a.mod_flag FROM `%1\$s_messages` a LEFT JOIN `%1\$s_user_names` b ON(b.name_id = a.author_name_id) WHERE a.message_id IN ('".implode("','",$aNeeded)."') ORDER BY a.parent_mid,a.message_id LIMIT %3\$d",$CONFIG['TAB_PREF'],$CONFIG[108],$CONFIG[107]); if($oResult->numRows() > 0){ while ($row = $oResult->fetchRow()){ if($row[6] == 1 || CCSIS::check_mod_priv(47,$CCSIS_NS->gid,$CCSIS_NS->fid)){ $oTree->add_node($row[0],$row,$row[1]); } } }else{ break; } } } $oTree->complete_tree(); print_r($oTree->aTree);
а как ты решаешь проблему сортировки? например, нужно выбрать всё поддерево и вывести в виде вложенных ul-ов да так, чтобы каждый li был на своём месте и никуда не скакал при изменении структуры дерева.
dark-demon, в вышеприведённом примере за сортировку отвечает вот эта строка ORDER BY a.parent_mid,a.message_id логика такова, что каждое более новое сообщение имеет больший идентификатор, т.е. по нему можно сортировать. В принципе можно было использовать поле даты создания, но оно в отличии от идентификатора не уникально. В некоторых случаях, со сложной логикой сортировки, я поддерживаю синтетический указатель положения узла среди узлов его уровня. ( ...ORDER BY parent_id,position... )
1. более новые записи вовсе не обязательно будут иметь больший идентификатор 2. более новые записи могут появляться в любой части дерева. при выборке непосредственных детей это годится, но при выборке всей ветви у нас опять всё идёт в разнобой. а делать сквозной индекс сортировки для всех узлов - это считай повторить половину функционала вложенных множеств...
dark-demon, давай ты не будеш высказывать в утвердительной форме свои ошибочные предположения? 1. В моем случае будут и имеют, в других случаях всё зависит от логики конкретного приложения / модуля. 2. Это не имеет значения, дерево от этого деревом не перестаёт быть и алгоритм его обработки не меняется. 3. Это годится для выборки любой произвольной части дерева. 4. Ничего дополнительно делать не надо. Я бы на твоём месте для начала поигрался с этим кодом, чтобы понять как он работает и что с помощью него можно делать. Готов ответить на любые твои вопросы, но пусть это будут вопросы, а не утверждения.
1. это зависит от субд 2. ну вот, например, нужно сделать постраничный вывод большого древа. предложишь выбрать всё дерево, отсортировать и потом отсечь лишнее? издеваешься? там же чёрт ногу сломит...
1. Это зависит от логики приложения, если логика такова, что численно больший идентификатор может принадлежать только более новой по дате создания сущности, но его можно использовать для сортировки, вместо даты создания. 2. Постраничная навигация по дереву возможна без чтения всего дерева. Достаточно выбирать n-ную пачку элементов дерева, строить из них дерево и выбирать из базы данных недостающую часть элементов. В результате на каждой странице (кроме первой) будет отображаться больше узлов дерева, за счёт узлов, необходимых для достройки дерева до корня. Для этого в классе CCSIS_Tree есть метод get_needed(), возвращающий идентификаторы требуемых для достройки дерева узлов. Впрочем, можно обойтись и без этого, принудительно построив дерево в такм виде, в котором оно выбралось (не красивое решение). Для этой цели служит метод CCSIS_Tree::complete_tree(). Этот же метод рекомендуется вызывать на всякий случай перед обработкой полученной древовидной структуры, т.к. иногда из-за ошибок или удаления некоторых узлов могут возникать "потерянные" ветви дерева.
поколупался сегодня с сабжем. добавление узлов получилось примерно таким: PHP: <?php function addnode($node) { $parentid= ifs(@$node[$this->parentfield],0); $id= $this->db->_insert($this->listable,$node); if (!$parentid): $this->db->_insert($this->linktable,array('anc'=>$id,'desc'=>$id)); else: $ancs= $this->db->get0d(" select count(anc) from {$this->linktable} where desc={$parentid} "); if(!$ancs): $this->db->query(" insert into {$this->linktable} select anc,{$parentid} from {$this->linktable} where desc=( select {$this->parentfield} from {$this->listable} where id={$parentid} ) "); /*$this->db->query(" insert into {$this->linktable} select anc,{$parentid} from {$this->listable},{$this->linktable} where id={$parentid} and desc={$this->parentfield} ");*/ $this->db->_insert($this->linktable,array('anc'=>$parentid,'desc'=>$parentid)); endif; endif; return $id; } ?> где $parentid - идетификатор узла к которому приконнекчиваем _insert - это хелпер, который инсертит массив в таблицу и возвращает идентификатор $this->parentfield - название поля с id родителя $this->linktable - название таблицы со связями предок-потомок $this->listable - название таблицы содержащей список узлов. если родитель не задан (корневой узел), то мы просто создаём линк на него же и успокаиваемся. если задан - проверяем есть ли к нему линки от предков. если есть, значит всё пучком (уже есть братья) и мы успокаиваемся если нет, значит добавляемый узел - первый ребёнок и потому нужно скопировать линки к родителю родителя так, чтобы новые линки шли от тех же предков уже к самому родителю. плюс добавляем линк от родителя к самому себе. закомменченный вариант с объединением вместо подзапроса в sqlite работает медленнее (проверял кучей инсертов внутри транзакции, на полях - индексы), но под мускулом, например, может быть всё с точностью до наоборот. anc - предок desc - потомок
PHP: <?php function getancs ($parentid) { $nodes= unprefix($this->db->get2d(" select * from {$this->linktable}, {$this->listable} where desc={$parentid} and anc=id "),array($this->listable.'.',$this->linktable.'.')); return $nodes; } /*function getancs ($parentid) { $nodes= $this->db->get2d(" select * from {$this->listable} where id in ( select anc from {$this->linktable} where desc={$parentid} ) "); return $nodes; }*/ ?> - это реализация функции получения всех предков по идентификатору родителя. тут быстрее оказалось как ни странно объединение, не смотря на использование unprefix. sqlite при объединении добавляет ко всем полям имена таблиц, что очень не удобно в дальнейшей работе. unprefix обрезает префиксы у полей. процедура, скажем так, не быстрая..
PHP: <?php function getdescs ($nodeid) { $nodes= $this->db->get2d(" select * from {$this->listable} where {$this->parentfield} in ( select desc from {$this->linktable} where anc={$nodeid} ) "); return $nodes; } /*function getdescs ($nodeid) { $nodes= unprefix($this->db->get2d(" select * from {$this->linktable},{$this->listable} where anc={$nodeid} and desc={$this->parentfield} "),array($this->listable.'.',$this->linktable.'.')); return $nodes; }*/ ?> - получение всех детей узла. тут оба варианта были наравне (при условии использования индексов - без них объеднение ужасно тормозило, а подзапросу пофиг ^_^), но использование unprefix на больших выборках уводило скрипт в даун.