Хочу использовать алгоритм Nested Sets для построения дерева с неогр. вложеностью. Но система многопользовательская и каждый пользователь должен иметь возможность построить подобное дерево. Создавать на каждого юзера по таблице - не решение. Поэтому нужно хранить все деревья в одной таблице.
Если мысли, как это сделать?

Кто ничего не знает об этом алгоритме, можно коротко почитать тут: http://www.izone.kiev.ua/web/php/23.htm (вторая часть статьи)

Код

CREATE TABLE multiuser_tree (     id_node BIGINT UNSIGNED AUTO_INCREMENT NOT NULL,     node_name VARCHAR(50) NOT NULL,     num_children SMALLINT NOT NULL DEFAULT 0, #для ускорения работы     fk_user INT UNSIGNED NOT NULL, #для разделения по пользователям     fk_parent_node BIGINT UNSIGNED DEFAULT 0 NOT NULL, #для организации дерева, 0 - "корень"     PRIMARY KEY(id_node),     KEY(fk_parent_node),     KEY(fk_user) );

fk_user - какая-то характеристика пользователя. Если он(пользователь) должен быть зарегистрированным, то его id - самое оно, если же нет, то можно использовать идентификатор сессии.
Добавлено @ 13:35
Можно и еще упростить - сделать таблицу

Код

CREATE TABLE user_tree_root(     fk_user INT NOT NULL PRIMARY KEY,     fk_root INT NOT NULL REFERENCES multiuser_tree(id_node)     UNIQUE(fk_root) );

а из multiuser_tree fk_user выбросить. Тогда всё сводится к выборке корня и "хождению" по multiuser_tree. Если же пользователи уже описаны, то достаточно добавить в таблицу с их описанием один столбец.

Это сообщение отредактировал(а) Bikutoru - 13.9.2005, 13:30

Уппс. Это же не Nested Sets...

Да ничего сложного, делать узлом в руте как-бы пользователя, а все подузлы и листья, ет всё его, вывод такого дерева можно выполнить запросом...

Код

SELECT A.*, IF (A.cat_left+1 < A.cat_right, 1, 0) AS nflag FROM ".$tbl." A, ".$tbl." B WHERE B.cat_id='".$id."' AND A.cat_left >= B.cat_left AND A.cat_right <= B.cat_right ORDER BY A.cat_left"

где $tbl - таблица
$id - ну это элемент, для которого выводятся все дети, поддерево короче.
Добавлено @ 14:57
Забыл, если nflag = 1 - значит есть потомки.

Это сообщение отредактировал(а) AntonioBanderaz - 13.9.2005, 14:58

Кстати, нашёл очень хорошую статью об этом деле. Здесь


Это сообщение отредактировал(а) Bikutoru - 13.9.2005, 18:40

Цитата(AntonioBanderaz @ 13.9.2005, 13:55)

Да ничего сложного, делать узлом в руте как-бы пользователя

Да, я тоже об этом думал... Но не знаю, насколько это хорошо, если пользователей несколько десятков тысяч будет. И каждый будет иметь в своем дереве примерно по 15 элементов, который в среднем на двух или трех уровнях вложенности располагаться будут.

А думаешь при другой расстановке у тебя будет меньше елементов, как я понял, это для выборочного отображения форумов на сайте... =)) В принципе алгоритм хороший, только по изменениях какого-либо элемента придётся пересчитывать всё, что следует за ним, а вот это уже не есть гуд ( для базы в 10000 элементов ещё нормально, а 10000*15 - не пробовал, посмотри потести скорость)

Цитата(Wowa @ 13.9.2005, 19:26)

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

А вот это всё равно, какая у них вложеность, хоть 1999-ая создай дополнительное поле level, это будет быстрее работать, чем делать пересчёт по всем границам ветвей.

У меня такие поля в БД.
ID | cat_left | cat_right | cat_level [name .... description]
Из них рабочие первые четыре, остальные информационные...

Цитата(AntonioBanderaz @ 13.9.2005, 22:18)

А думаешь при другой расстановке у тебя будет меньше елементов, как я понял, это для выборочного отображения форумов на сайте... =))

нет, совсем не для этого...

Цитата(AntonioBanderaz @ 13.9.2005, 22:18)

В принципе алгоритм хороший, только по изменениях какого-либо элемента придётся пересчитывать всё, что следует за ним, а вот это уже не есть гуд ( для базы в 10000 элементов ещё нормально, а 10000*15 - не пробовал, посмотри потести скорость)

Если у меня есть три корневых раздела, и я добавляю во второй корневой раздел еще одну ветку. Будут ли затронуты как-то первый и третий разделы? Ничего там пересчитываться не будет?

Цитата(Wowa @ 13.9.2005, 23:51)

Если у меня есть три корневых раздела, и я добавляю во второй корневой раздел еще одну ветку. Будут ли затронуты как-то первый и третий разделы? Ничего там пересчитываться не будет?

Только третий и общий корень, поле right. Да у третьего, ко всем полям, имею ввиду right и left, будет прибавлена 2.


Я тут накотал классик для себя, думаю тебе это подойдёт.
Класс DB нужен для работы с базой данных:

Код

<?php class DB {  var $host = '';  var $user = '';  var $password = '';  var $database = '';  var $presistent = false;    var $conn = null;    var $result = false;    function DB($host, $user, $password, $database, $persistent = false) {       $this->host = $host;       $this->user = $user;       $this->password = $password;       $this->database = $database;       $this->presistent = $presistent;   }  function open() {       $this->presistent ? $func = 'mysql_pconnect' : $func = 'mysql_connect';       $this->conn = $func($this->host, $this->user, $this->password);       if(!$this->conn) return false;       if(!@mysql_select_db($this->database, $this->conn) return false;       return true;  }  function close() {       return(@mysql_close($this->conn));  }  function error() {       return(mysql_error());  }  function query($sql) {       $this->result = @mysql_query($sql, $this->conn);       return($this->result != false);  }  function affectedRows() {       return(@mysql_affected_rows($this->conn));  }  function numRows() {       return(@mysql_num_rows($this->result));  }  function fetchObject() {       return(@mysql_fetch_object($this->conn, MYSQL_ASSOC));  }  function fetchArray() {       return(@mysql_fetch_array($this->conn, MYSQL_NUM));  }  function fetchAssoc() {       return(@mysql_fetch_assoc($this->conn));  }  function freeResult() {       return(@mysql_free_result($this->result));  } } ?>

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

Код

<?php class UsersTree {  var $userId = 0;  var $userExists = false;  var $DB;       function UsersTree($userId,$DB) {        $this->DB = $DB;        $this->DB->query("SELECT * FROM users WHERE id='$userId'");        if($this->$DB->numRows() == 1) {             $this->userExists = true;              $this->$userId = $userId;         }        return $this->userExists;       }       function getUserTree() {        if($this->userId && $this->userExists) {             $query = "SELECT A.*, IF (A.left+1 < A.right, 1, 0) AS childExists FROM usersTree A, usersTree  B WHERE B.id='".$id."' AND A.left >= B.left AND A.cat_right <= B.right ORDER BY A.left";             $this->DB->query($query);             $returns = array();             while($node = $this->DB->fetchAssoc()) {                   $returns[] = $node;             }             return $returns;         } else return;       }       function getNodeInfo($id) {        if($this->userId && $this->userExists) {             $this->DB->query("SELECT left,right FROM userTree WHERE id=".$this->userId);             $LR = $this->DB->fetchObject();             $left = $LR->left;             $right = $LR->right;             if($id < $right && $id > $left) {                   $this->DB->query("SELECT left,right,level FROM userTree WHERE id=$id");                    return $this->DB->fetchObject();             } else return;        } else return;            }       function insertUserNode($id,$array) {        if($this->userId && $this->userExists && is_array($array) && $nodeInfo = $this->getNodeInfo($id)) {             $nodeNames = implode(',', array_keys($data)).',';             $nodeValues = "'".implode("','", array_values($data))."',";             $nodeNames .= 'left,right,level';        $nodeValues .= ($nodeInfo->right).','.($nodeInfo->right+1).','.($nodeInfo->level+1);        $query = 'UPDATE userTree SET left=IF(left>'.$nodeInfo->right.',left+2,left), right=IF(right>='.$nodeInfo->right.',right+2,right) WHERE right>='.$nodeInfo->right;        $this->DB->query($query);        $query = 'INSERT INTO userTree('.$nodeNames.') VALUES('.$nodeValues.')';        return $this->DB->query($query);        } else return;       }       function deleteUserNode($id) {         if($this->userId && $this->userExists  && $nodeInfo = $this->getNodeInfo($id)) {             $query = 'DELETE FROM userTree WHERE id='.$id;             $this->DB->query($query);             $query = 'UPDATE userTree SET left=IF(left BETWEEN '.$nodeInfo->left.' AND '.$nodeInfo->right.',left-1,left),right=IF(right BETWEEN '.$nodeInfo->left.' AND '.$nodeInfo->right.',right-1,right),'             .'level=IF(left BETWEEN '.$nodeInfo->left.' AND '.$nodeInfo->right.',level-1,level),left=IF(left >'.$nodeInfo->right.',left-2,left),'             .'right=IF(right >'.$nodeInfo->right.',right-2,right) WHERE '.$this->right.'>'.$nodeInfo->left;        return $this->DB->query($query);         } else return;       }       function updateUserNode($id,$array) {         if($this->userId && $this->userExists &&is_array($array) && $this->getNodeInfo($id)) {             $query = '';             foreach($array as $nodeName=>$nodeValue) {                   $query .= ','.$nodeName."='".addslashes($nodeValue)."'";             }             return $this->DB->query("UPDATE userTree SET ".substr($sql_set,1)." WHERE id=$id");                      } else return;       } } ?>

Там могут быть маленькие ошибки, и не сделал обработку ошибок. Таблица и названия полей зашиты в запросы, надо в коде менять.. Во втором классе DB - ссылка на экземпляр первого класса. Надеюсь пригодится... =))) [b][/b]

Это сообщение отредактировал(а) AntonioBanderaz - 14.9.2005, 02:42

Да кстате у всего должен быть общий корень, один, а не три или больше...

Цитата(AntonioBanderaz @ 14.9.2005, 01:46)

Да кстате у всего должен быть общий корень, один, а не три или больше...

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

Если делать так, чтобы с корня выходило много веток и у каждого юзера было бы по своей ветке. То сюдя из этого:


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

Я решил все-таки использовать метод Adjacency List, т.к. уровней вложенности всего 3-4 будет.

Цитата(Wowa @ 20.9.2005, 20:18)

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

Ну это врятли, деревья по сути между собой не связяны, если только оболочкой (root'ом);

Цитата(Wowa @ 20.9.2005, 21:35)

Я решил все-таки использовать метод Adjacency List, т.к. уровней вложенности всего 3-4 будет.

Напиши по-подробней про него.

Цитата(AntonioBanderaz @ 20.9.2005, 22:35)

Ну это врятли, деревья по сути между собой не связяны, если только оболочкой (root'ом);

Как это не связаны? По рисунку, который я выше прикрепил - видно, что если я в первой ветке выходящей с корня что-то изменю(например, добавлю еще один уровень), то во второй и третьей ветках выходящих с корня - должны быть пересчитаны left key и right key.

Цитата(AntonioBanderaz @ 20.9.2005, 22:35)

Напиши по-подробней про него.

Adjacency List - и есть именно простейший метод хранения деревьях, который ПЕРВЫМ описан в статье, ссылку на которую я привел выше.