| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > PHP: Базы Данных > Деревья Nested Sets |
| Автор: Wowa 13.9.2005, 12:10 |
| Хочу использовать алгоритм Nested Sets для построения дерева с неогр. вложеностью. Но система многопользовательская и каждый пользователь должен иметь возможность построить подобное дерево. Создавать на каждого юзера по таблице - не решение. Поэтому нужно хранить все деревья в одной таблице. Если мысли, как это сделать? Кто ничего не знает об этом алгоритме, можно коротко почитать тут: http://www.izone.kiev.ua/web/php/23.htm (вторая часть статьи) |
| Автор: Bikutoru 13.9.2005, 13:29 | ||||
fk_user - какая-то характеристика пользователя. Если он(пользователь) должен быть зарегистрированным, то его id - самое оно, если же нет, то можно использовать идентификатор сессии. Добавлено @ 13:35 Можно и еще упростить - сделать таблицу
а из multiuser_tree fk_user выбросить. Тогда всё сводится к выборке корня и "хождению" по multiuser_tree. Если же пользователи уже описаны, то достаточно добавить в таблицу с их описанием один столбец. |
| Автор: Bikutoru 13.9.2005, 13:48 |
| Уппс. Это же не Nested Sets... |
| Автор: AntonioBanderaz 13.9.2005, 14:55 | ||
Да ничего сложного, делать узлом в руте как-бы пользователя, а все подузлы и листья, ет всё его, вывод такого дерева можно выполнить запросом...
где $tbl - таблица $id - ну это элемент, для которого выводятся все дети, поддерево короче. Добавлено @ 14:57 Забыл, если nflag = 1 - значит есть потомки. |
| Автор: Bikutoru 13.9.2005, 18:38 |
| Кстати, нашёл очень хорошую статью об этом деле. http://www.webscript.ru/stories/04/09/01/8197045 |
| Автор: Wowa 13.9.2005, 19:26 | ||
Да, я тоже об этом думал... Но не знаю, насколько это хорошо, если пользователей несколько десятков тысяч будет. И каждый будет иметь в своем дереве примерно по 15 элементов, который в среднем на двух или трех уровнях вложенности располагаться будут. |
| Автор: AntonioBanderaz 13.9.2005, 23:18 | ||
А думаешь при другой расстановке у тебя будет меньше елементов, как я понял, это для выборочного отображения форумов на сайте... =)) В принципе алгоритм хороший, только по изменениях какого-либо элемента придётся пересчитывать всё, что следует за ним, а вот это уже не есть гуд ( для базы в 10000 элементов ещё нормально, а 10000*15 - не пробовал, посмотри потести скорость)
А вот это всё равно, какая у них вложеность, хоть 1999-ая создай дополнительное поле level, это будет быстрее работать, чем делать пересчёт по всем границам ветвей. У меня такие поля в БД. ID | cat_left | cat_right | cat_level [name .... description] Из них рабочие первые четыре, остальные информационные... |
| Автор: Wowa 13.9.2005, 23:51 | ||||
нет, совсем не для этого...
Если у меня есть три корневых раздела, и я добавляю во второй корневой раздел еще одну ветку. Будут ли затронуты как-то первый и третий разделы? Ничего там пересчитываться не будет? |
| Автор: AntonioBanderaz 14.9.2005, 02:36 | ||||||
Только третий и общий корень, поле right. Да у третьего, ко всем полям, имею ввиду right и left, будет прибавлена 2. Я тут накотал классик для себя, думаю тебе это подойдёт. Класс DB нужен для работы с базой данных:
А это уже для работы с деревьями для пользователя.
Там могут быть маленькие ошибки, и не сделал обработку ошибок. Таблица и названия полей зашиты в запросы, надо в коде менять.. Во втором классе DB - ссылка на экземпляр первого класса. Надеюсь пригодится... =))) |
| Автор: AntonioBanderaz 14.9.2005, 02:46 |
| Да кстате у всего должен быть общий корень, один, а не три или больше... |
| Автор: Wowa 20.9.2005, 20:18 | ||
Нет. Я подумал и решил, что так не годится. Для каждого юзера нужно обязательно отдельное дерево не связанное с другими. Т.к. иначе, если вдруг дерево запорится у кого-то, то может быть такое, что и у других что-то поломается. |
| Автор: Wowa 20.9.2005, 20:33 |
| Если делать так, чтобы с корня выходило много веток и у каждого юзера было бы по своей ветке. То сюдя из этого: http://www.webscript.ru/images/sh_0.gif насколько я понял, если какой-то юзер что-то добавит в своей ветке, то должны будут пересчитаться ключи у всех веток других юзеров, если они "правее". Что совершенно недопустимо и глупо при большом кол-ве юзеров. |
| Автор: Wowa 20.9.2005, 21:35 |
| Я решил все-таки использовать метод Adjacency List, т.к. уровней вложенности всего 3-4 будет. |
| Автор: AntonioBanderaz 20.9.2005, 23:35 | ||||
Ну это врятли, деревья по сути между собой не связяны, если только оболочкой (root'ом);
Напиши по-подробней про него. |
| Автор: Wowa 20.9.2005, 23:45 | ||||
Как это не связаны? По рисунку, который я выше прикрепил - видно, что если я в первой ветке выходящей с корня что-то изменю(например, добавлю еще один уровень), то во второй и третьей ветках выходящих с корня - должны быть пересчитаны left key и right key.
Adjacency List - и есть именно простейший метод хранения деревьях, который ПЕРВЫМ описан в статье, ссылку на которую я привел выше. |
| Автор: AntonioBanderaz 21.9.2005, 00:02 | ||||
Ты боишься если какая ошибка может произойти, так можно при изменениях использовать трансакции, или тоже не подходит? |
| Автор: Wowa 21.9.2005, 00:06 | ||||||
Можно... но для такой просто операции использовать трансакции - как-то странно. Итак должно чики-пики работать
Представь. 10 000 юзеров. У каждого в базе хранится по дереву с несколькими ветками. Какой-то юзер с первой ветки решает добавить себе подветку, теперь должны перестраиваться параметры веток у всех других юзеров. Добавлено @ 00:08
Да, долгий вероятно. Зависит от ситуации. Но если уровней вложенности мало и веток немного, то спокойно можно даже всё дерево выбрать и быстренько в памяти выстроить нить из родителей. Ну или же рекурсией выбирать через запросы к базе.. |
| Автор: AntonioBanderaz 21.9.2005, 00:15 | ||||
Да это будет долговато, даже если поля leftKey и RightKey сделать, извиняюсь за мой плохой английский, "проидексировать", короче в мускуле есть что-то на полобие "register " в С. Только точно не помню как это называется. Скорость увеличится, но думаю не очень на много... Про nested можно сделать разряженное дерево, т.е. с запасом для каждого юзера. Т.е ограничить по кол-ву элементов, И все которые не заданы им, оставлять пустыми и их просто не выводить... А когда добовляет то менять только в области самого юзера. Добавлено @ 00:20
Я считаю нужно сделать двумя способами, и проверить скорость!! Так думаю правильней будет. |
| Автор: Wowa 21.9.2005, 00:24 | ||
Можно, но не стандартными средствами класса. А писать свой или переделывать для этого существующий - долго. Или у тебя есть что-то готовое для этого? |
| Автор: AntonioBanderaz 21.9.2005, 00:30 | ||||
Готового нет, только родил идею Я могу посидеть завтра может что и накатаю.
На самом деле не так уж и долго, может часа 4 + отладка час/полтора. Вот то что сверху для юзеров можно за основу взять, а там в основном запросы и вывод в массив поменять надо, наверно ещё привязку к таблице пользователей надо убрать. (был написан за 1 час) |
| Автор: Wowa 21.9.2005, 00:39 | ||||
Наверное лучше за основу взять этот: http://dev.e-taller.net/dbtree Т.к. он более функционален Добавлено @ 00:40
Интересно, какой запас надо делать. По идее - должно быть практически все равно какой запас делать. Можно по сотке оставлять.. |
| Автор: AntonioBanderaz 21.9.2005, 00:49 | ||||||||
В принципе любой, ты сам определишь какой, т.е это вроде максимума элементов дерева...
Вот блин делема, либо быстрый вывод и долгое изменение, либо быстрое изменение и долгий вывод... как бы найти оптимальное... ???
Добавлено @ 00:50
|
| Автор: Wowa 21.9.2005, 00:57 |
| AntonioBanderaz вот тут есть обсуждение на эту тему: http://www.phpclub.ru/talk/showthread.php?s=&threadid=48194 Не все так просто. Как переносить при этом ветки с подветками? |
| Автор: AntonioBanderaz 21.9.2005, 01:06 | ||
Интересненько... Да, оказалось не всё так просто...
Вот это вообще не представляю... Ели только сначала удалять запас, перемещать, а потом весь запас дополнять, но это уже совсем через ЖЖЖ. Добавлено @ 01:15 http://www.profy.net/forum/view_topic/35.html - вот тут почитай. |
| Автор: AntonioBanderaz 21.9.2005, 01:21 | ||||
| Нашёл подходящий тебе. вот документация
Добавлено @ 01:24 А вот и полная. http://www.inses.ru/lj/tree/
А как всё просто оказалось!!!! Блин -)) Даже обидно, что не додумался.... вот типо сам код |
| Автор: AntonioBanderaz 21.9.2005, 01:33 |
| http://www.sitepoint.com/print/1105/ - тут тоже кое что интересное. |
| Автор: Wowa 21.9.2005, 01:39 | ||
А как он мне может помочь? |
| Автор: AntonioBanderaz 21.9.2005, 01:46 |
| Ну это что-то среднее между Nested и списком. Короче будет оптимально его использовать для твоей задачи... У тебя теперь есть три варианта которые Ты можешь потестить и выбрать самый оптимальный. Посмотри на организацию таблицы. |
| Автор: Gold Dragon 21.9.2005, 08:39 |
| Не знаю на сколько это в тему, но вдруг. В своё время я мучился над генеологическим деревом и как присвоить уникальный номер человеку в этом дереве. Ниже прикрепил рисунок простого дерева. Поясню. - Есть уровни родства, их здесь 4 - Есть группы родства, в которые входят братья и сёстра - В каждой группе есть определённый человек И от сюда можно описать любого человека, например выделенного зелёным - 2.1.2. Во-первых получается уникальный номер. Во-вторых, легко можно найти этого человека в древе и все его связи не зависимо от сложности родства и самого древа. Я понимаю, что это немного не то, но мало ли |
| Автор: AntonioBanderaz 21.9.2005, 15:04 |
| Поставлю задачу - локализовать дерево. Как я понимаю, нужно сделать список деревьев, по которым можно проходить уже созданым алгоритмом. Надо придумать как индотифицировать само дерево, можно и лучше эт будет делать в другой таблице. Теперь у нас две таблицы, одна с деревьями, другая со списком. Теперь появляются проблемы, как быть с перемещением дерева, точнее, как это локально организовать. Как тоже локально добовлять в дерево, чтобы изменялось только локальное дерево. Вот собственно и задача... |
| Автор: Wowa 21.9.2005, 21:12 |
| Вот тут есть хорошая статья по работе с деревьями: http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html Добавлено @ 21:16 traversedTree Object v. 1.12 - видимо как раз то, что мне нужно. Интересно только, насколько качественно написан этот класс.. И нет ли в нем глюков. Сейчас буду смотреть.. |
| Автор: AntonioBanderaz 21.9.2005, 21:32 | ||
Всё таки решил его использовать? По поводу локализации. Объясняю можно ведь использовать nested деревья, только нало сделать возможность управление локальным деревом. Т.е. в некоторой таблице лежит куча так сказать root'ов, по которым нам не пройтись уже существующим классом, ошибку выдаст. А вот если можно будет локализовать дерево, тоесть получать доступ к нему по id его root'а. Грубо говоря в таблице хранится как-бы массив деревьев, и нам нужно обращаться к отдельным его елементам не вызывая изменений в остальных елементах. Вот для этого нам и нужна вторая таблица, чтобы знать сколько у нас деревьев, какой у них id и индефикатор. |
| Автор: Wowa 21.9.2005, 22:41 | ||||
Но ведь при этом мы не уйдем от того, что будут перестраиваться значения столбцов left, right в соседних ветках, которые другим юзерам принадлежать будут. Добавлено @ 22:47
не знаю, я пока изучаю класс. Насколько я понял, то там разделять деревья для разных юзеров нужно путем создания еще одного столбца в ИД юзера, и потом в через setCondition() прописывать доп. условия, чтобы выбирались, обновлялись, удалялись ветки только с опред. юзером. Иначе имхо никак. Не понял, для чего там: var $limitStart;// SQL Limit clause @access private var $limitSet; // SQL Limit clause @access private |
| Автор: Wowa 22.9.2005, 02:26 |
| В общем я решил пойти следующим способом... 1. Использовать Nested Sets 2. Использоваться класс phpDBTree 1.4 для работы с ним. 4. Парсить все запросы к дереву, добавляя к ним WHERE owner=ИД 5. Таким образом я собираюсь хранить в одной таблице довольно простные деревья нескольких десятков юзеров Что скажете? |
| Автор: AntonioBanderaz 22.9.2005, 07:47 | ||||
Я же написал, надо локализовать, т.е не чтобы не затрагивало ничего в других элементах. А вот списки тебе совсем не подходят... На 10000 - они могут из-за рекурсии и большого числа запросов повесить сервис. !!!! Добавлено @ 07:48
Объясни по-подробнее |
| Автор: Wowa 22.9.2005, 10:20 | ||||
Ну, есть обычный класс для работы с этим дереревом. У каждой ветки будет значение owner, которое означает, какому юзеру принадлежит эта ветка. Получается, что мы можем добавляя ко всем запросам WHERE owner=ИД ЮЗЕРА, работать в одной таблице с множеством деревьев. По одному дереву на юзера. Деревья как раз между собой будут через owner различаться. Добавлено @ 10:21
Это ясно, что надо, но я все равно не понял твою логику. |
| Автор: AntonioBanderaz 22.9.2005, 19:06 |
| Ну смотри у нас нет общего дерева, а куча так сказать root'ов в таблице, там могут быть одинаковые элементы с одинаковыми left и right, значит они могут в принципе подходить к любому из деревьев. Чтобы этого не было надо добавить индетификатор дерева, а дальше работать с существующим алгоритмом, только добовлять where tree_id='индетификатор'. А в другой таблице хранить "адреса" корней деревьев, с их индетификаторами. Ну вот как-то так |
| Автор: Wowa 22.9.2005, 19:10 |
| Да, так я и делаю |
| Автор: AntonioBanderaz 22.9.2005, 22:43 |
| Ну наконец пришли к общему так сказать знаменателю. Когда закончишь, выложи глянуть Добавлено @ 22:43 Ну наконец пришли к общему так сказать знаменателю. Когда закончишь, выложи глянуть |