в статьях на тему организации древовидных структур в реляционных БД обычно описывают два варианта реализаций (исключая их вариации): 1. каждый элемент хранит только ссылку на непосредственного родителя. + быстрое и простое добавление узлов, изменение структуры, выборка непосредственных детей и непосредственного родителя. - выборка всех потомков и всех предков - сложные и тормозные операции. 2. вложенные множества. абстрактно говоря: каждый узел хранит свой порядковый номер и номер последнего вложенного элемента; узлы с промежуточными номерами также являются его потомками. + простая и быстрая выборка как непосредственных детей, так и потомков произвольного уровня вложенности. аналогично с выборкой предков. + все узлы упорядочены, что избавляет нас от необходимости изобретать механизм задания порядка следования узлов. - сложная и тормозная вставка новых узлов, а также изменение структуры. причём, если тормоза в тех или иных случаях допустимы (например, они пренебрежимо малы или тормозные запросы вызываются относительно редко), то от сложности реализации никуда не деться. давайте попробуем забыть про эти способы и попытаемся подойти к проблеме с чистого листа пусть у нас есть список узлов (например - сообщения пользователей форума): [sql]create table [mo-msg-list] ( [msg-id] integer primary key, [msg-cont] text )[/sql] я опустил не относящиеся к теме поля таблицы. если у нас форум по типу IPB или ЖЖ, то сообщения могут образовывать древовидную структуру с многочисленными ветвлениями. какие задачи возникают при работе с таким деревом? основные: по заданному узлу найти... 1) ... предков до определённого уровня (перейти к исходному обсуждению) 2) ... детей до определённого уровня (вывести список ответов с завязками дочерних обсуждений) 3) ... всех детей (для поиска последних сообщений в дочерних обсуждениях) более редкие - всевозможные изменения структуры (в том числе и добавление узлов). как всё это согласуется с реляционной моделью данных? фактически нам не столь важно знать является ли один узел дитём другого, сколько является ли один узел потомком другого. информация о том является ли узел непосредственным потомком - легко получается из информации об уровнях вложенности обеих узлов, которую всегда можно добавить на этапе изменения структуры. эти рассуждения подводят нас к необходимости создания отдельной таблицы для организации связей "многие-ко-многим" ("предок-потомок"): [sql]create table [mo-msg-rel] ( [rel-id] integer primary key, [rel-from] int, [rel-to] int, [rel-type] int )[/sql] в итоге получаем две таблицы: упомянутый выше плоский список узлов и надстройка над ним - список векторов, соединяющих узлы. важно отметить, что список узлов никак не зависит от списка векторов, что позволяет для одного и того же множества узлов иметь несколько древовидных структур (для этого можно создавать дополнительные таблицы, или же просто ввести дополнительное поле [rel-type] - выбор зависит от количества типов и их "тяжеловесности"). есть одна не решённая пока проблема - нужно как-то задавать порядок следования узлов-братьев. страндартным решением тут является присваивание каждой записи определённого числа по которому и производится сортировка при выборке. но реализация изменения структуры сильно усложняется: если требуются выборки поддеревьев - требуется поддержание уникальности значений в поле сортировки, иначе - достаточно уникальности в пределах одного родителя, что не сильно упрощает задачу. забудем и про этот метод нам нужно организовать упорядоченный список, а это частный случай дерева, которое - частный случай графа, а механизм образования множества графов над одним набором узлов у нас уже есть, осталось им воспользоваться введя в обращение второй тип узлов - "предыдущий-следующий" не будем останавливаться на достигнутом поверх всего этого можно накладывать и другие независимые графы, например: - можно одну и ту же ветку прилинковать к нескольким другим веткам - можно организовать "кольца" (для галереи, например) - можно реализовать связи с родственными ветками ("похожие обсуждения", "рекомендуем ознакомиться" итп) - можно реализовать систему тэгов. запросы к бд получаются относительно простые - двух-трёх сложные, без рекурсивных выборок. при этом они очень похожи друг на друга. типовой запрос выборки всех потомков выглядит так: [sql]select * from [mo-msg-list],[mo-msg-rel] where [msg-id] in ( select [rel-to] from [mo-msg-rel] where [rel-from]=3 and [rel-type]=1 ) and [msg-deep]=4 and [msg-id]=[rel-from] and [rel-type]=2[/sql] , где: 1 - идентификатор типа связи "родитель-потомок" 2 - идентификатор типа связи "пердыдущий-следующий" 3 - идентификатор исходного узла 4 - требуемая глубина вложенности подзапрос использовался, чтобы не захламлять итоговую таблицу информацией о древовидной структуре, тем не менее в ряде случаев она нужна - тогда следует использовать слияние. ну а далее - дело техники: создаём хеш с идентификаторами узлов в качестве индексов и восстанавливаем дерево (в данном случае - список). задача, конечно не тривиальная, но и не шибко сложная. изменение структуры - тоже простая операция - удаляется часть записей и добавляются новые. тут главное ничего не забыть, но для этого существуют триггеры, либо классовая абстракция на худой конец. отмечу ещё одну фичу - избыточность информации. с одной стороны это раздувает БД, с другой - ускоряет выборки. кроме того - сомнительная возможность восстановления частично утраченной структуры в сравнении с упомянутыми вначале алгоритмами, сей ценой некоторого увеличения объёма БД позволяет быстро делать выборки не порождая при этом диких тормазов при изменении структуры. комменты приветствуются
да, ещё есть вариант "материализованный путь", где каждый узел хранит идентификаторы всех его предков разделённые специальным разделителем. он во много подобен первому рассмотренному варианту, но рекурсивную обработку заменяет на поиск по подстроке, что, скажем так, не слишком быстро + сильная избыточность.
Интересно, респект По две таблицы на каждое дерево - чересчур жирно и двойные запросы - из одной таблицы связи, из другой данные - сведут все твои усилия по упрощению/оптимизации системы на нет. Вложенные множества ака Nested Sets - удобное решение, к тому же просто эстетически красивое. Поддержка и пересчет значений в нем действительно нетривиальная задача, но... только если ты пересчитываешь изменившиеся ветви после внесения изменений в дерево. Я бы реализовал так: у каждого узла есть 2, так сказать, критических поля - это id родителя и порядковый номер в нем, и еще 3 дополнительных поля, относящиеся к Nested Sets - left, right, level. При редактировании дерева используются только "критические" поля, а после внесения изменений - полностью пересчитывается все дополнительные поля дерева одной, достаточно простой, рекурсивной функцией. Совмещаем простоту и красоту реализации и скорость выборок... за счет скорости внесения изменений правда. Что поделать, за все надо платить.
да нет, нормально. разнесение разнородных данных по таблицам способствует ускорению выборок. впрочем, можно засунуть все деревья (даже для разных таблиц) в одну таблицу - главное - указать разные типы связей. да ладно, не может быть, чтобы джойны так уж тормозили... в том то и дело, что пересчитывать придётся у доброй половины записей. это только добавление. перенос ветви - куда более нетривиальная задача. я бы предпочёт заплатить местом в БД, чем скоростью где-либо
Я предлагаю пересчитывать все дерево целиком - т.е. выбирать его полностью и обновнять те записи, у которых изменились значения вычисляемых полей. Т.е. алгоритмической разницы между операцией вставки и операцией переноса ветки нет никакой - другое дело, что на большом дереве все тут же просядет но этим, похоже, и канонические Nested Sets грешат не в меньшей степени.
dark-demon, два года назад я занимался как раз решением затронутой тобой проблемы. И я её решил. (типа всё хватит) Теперь чуть подробнее. Для работы со сложными древовидными структурами у меня создано специальное API. По сути используется озвученная тобою идея хранить информацию о связях в дополнительной таблице. Только вот со структурой ты как и я, в своё время, намудрил. У меня тоже сначало было две таблица (в одной хранились все предки, в другой все потомки), я чувствовал что что-то здесь не оптимально и есть простор для оптимизации, сначало я хотел объединить таблицы добавив дополнительный флаг "направления" (как у тебя), но после нескольких замечаний одного из членов ПХПклуба я неожиданно понял, что решение по сути элементарно. Направление задаётся самим именем столбца (родитель, потомок) и достаточно просто правильно составить элементарнейший SQL запрос. Сейчас я попытаюсь найти ту тему на ПХПклубе,,, кину ссылку в этой теме. Пор сути достаточно иметь таблицу связей родитель -> потомок которую можно использовать для всех необходимых выборок. Для удобства я написал API принимающий имя таблицы имя поля предка и имя поля потомка, и содержащий все необходимые мне инструменты модификации дерева. + API для генерации бинарного дерева за 1 SQL запрос. Этот тип хранения древовидных структур работатет имеет все преймущества NS и не имеет недостатков типа перестройки синтетических индексов при каждой операции с деревом. Собственно это всё.
ONK Даже с одной дополнительной таблицей, мне твое решение все равно не очень нравится. Дополнительная таблица есть дополнительная таблица; ее нужно поддерживать и перестраивать. Согласен, операции добавления/изменения в твоем случае проще, но зато выборки будет сложнее - и в конце концов одно другое уравновесит, а по объему/памяти будет проигрыш. Ведь ты по сути вводишь таблицу с огромным количеством записей - представь, сколько памяти будут жрать ее индексы в том же MySQL. Мне из той темы понравилась одна мысль - распределенные Nested Sets. В примере с форумом из первого сообщения здесь: вместо того, чтобы хранить одно тяжелое дерево на весь форум, хранится по отдельному "деревцу" на каждую тему форума. Скорость выборок (то, что наиболее важно для активного форума) - максимальная. Дополнительных данных - немного. Дополнительных таблиц - вообще нет. Операции вставки и изменения - сравнительно быстрые, даже с полным пересчетом дерева, так как в одной теме сообщений немного, скажем не более 1000, а это для Nested Sets ерунда.
Dagdamor, код поддержания служебных таблиц связей пишется однократно. Все операции модификации таблицы сводятся к 2-м SQL запросам. Все операции выборки дерева сводятся к одному SQL запросу с объединением со служебной таблицей. Количество записей в служебной таблице в реальных условиях не так велико, а так как хранимые данные имеют фиксированный тип + являются индексами, то скорость выборки очень высокая и практически не зависит от размера таблицы. Для хранения внутренних связей ответов в теме вообще не нужно никаких извращений, достаточно хранить id предка, выборка элементарна, построение дерева тоже, скорость,,, быстрее не бывает.
ONK Это все понятно - при использовании Nested Sets все примерно так же, код тоже пишется однократно (не двукратно же его писать? ), все операции сводятся к одному запросу и одному вызову функции пересчета, все операции выборки - тоже простые SQL запросы, разве что без использования вспомогательных таблиц. Но что значит, количество данных во вспомогательной таблице не так велико? В лучшем случае (горизонтальное дерево) это порядка N записей, где N - это количество нодов в дереве, в худшем случае (вертикальное дерево) - это порядка N^2 записей. В реальных условиях будет где-то N^1.5, а это неприемлемо - вспомогательная таблица, несмотря на фиксированный размер записи и короткие поля, по объему очень быстро перевесит основную, а поскольку вся она по сути проиндексирована, будут проблемы с памятью, как оперативной, так и дисковой.
Dagdamor, про проблемы с памятью и диском не надо песен -), ничего не будет, СУБД для того и писаны, чтобы эффективно решать такие задачи. Теперь по поводу математики. В твои подсчёты вкрались серьёзные ошибки. В лучшем случае в таблице бедет пусто, т.к. необходимость отображения связи с корнем просто отсутствует. В худшем случае количество записей в таблице будет равно n^2/2 - n/2 где n - кол-во записей в основной таблице. Для дерева в 50 элементов в худшем случае будет 1255 записей, в лучшем 0, а при нормальной вложенности не более 100.
у меня ничего подобного нет собственно у меня так и есть за ссылку спасибо - почитаю. по сабжу - по поводу упорядоченных списков - есть, мягко говоря, некоторые сложности для организации постраничного вывода... пойду помидитирую
нет, rel-type - это тип связи. типы могут быть "указатель на потомка", "указатель на дитя", "указатель на следующего", "указатель на родственный документ" итд.
dark-demon, это оно и есть, просто в твоём случае, из-за поддержки дополнительной функциональности, возможных значений не 2 а 4. Честно говоря лень думать над тем что ты описал, но наверняка и тут есть что оптимизировать в плане объёма хранимых данных и методов их выборки. Как минимум можно убрать половину возможных значений параметра rel-type.
ONK Эта фраза меня не убеждает, совершенно А я как написал? "n^2/2 - n/2" - это и есть выражение порядка n^2. То есть, если у тебя в таблице 50 тыс. записей, в худшем случае в дереве связей будет порядка 2,5 млрд. записей, ну один миллиард, если учитывать коэффициенты - небольшое утешение. Даже в среднем случае (n^1.5) тебе потребуется порядка 10 миллионов связей для такой таблицы. Не многовато ли? Попробуй такую таблицу импортировать или экспортировать. Попробуй ее пересчитать, если на импорт жалко траффика. Попробуй в нее добавить новую запись. Это называется динамическое программирование - хранение вычисляемых данных вместо их расчета "на лету", и с ним на практике надо быть очень осторожным. Мы не говорим о дереве в 50 записей здесь. Такое дерево можно хранить как угодно, хоть в виде сериализованной структуры
Dagdamor, по поводу дерева, я просто приведу пример реального древа модулей. Дерево очень хорошее, вложенность доходит до 10 при этом всего два коря (общедоступная часть сайта и бэкэнд). Сейчас в таблице модулей 254 записи, а в служебной таблице отношений 622 записи. Т.е. Для среднестатистического дерева модулей можно принять соотношение количества элементов к количеству служебных записей в таблице отношений 1 к 3 (с запасом). Теперь по поводу больших таблиц и производительности. Когда я генерил тестовый контент для форума, время вставки новой записи в таблицу ответов (более 24М записей) не превышало 2мс. При этом таблица динамического типа, в ней 17 столбцов и 5 индексов (3 из которых составные). Выборка 20 случайно разбросанных по таблице записей занимает до 40мс, последовательно расположенных менее 10мс, выборка 20 упорядоченных записей принадлежащих конкретной теме менее 20мс. Это я к тому, что дело не в размере таблиц и количестве записей а в умении с ними работать...
[offtop] а вы добавте к этому ~50 конкурирующих запросов и посмотрите сколько тогда будет выборка занимать времени А то теория и идиальные условия с реальность частенько всё-же расходяться. [/offtop]
Psih, синтетические тесты которые я проводил моделируют самые худшие условия. В реальности 95% запросов в обсуждаемой предметной области запрашивают одни и теже данные, соответственно они кэшируются на всех уровнях, начиная от кэша винчестера и заканчивая собственным кэшем СУБД. В результате, если первый запуск SQL запроса потребовал 70мс то последующие уложатся в 1мс.
в рассмотренном в первом посте алгоритме есть один существенный минус - большая избыточность при высокой глубине дерева. например: два брата десятого уровня вложенности имеют фактически десять одинаковых ссылок на родителей. и таких ситуаций случается много. значит стоит рассмотреть вариант с указанием для каждого узла указателя на список родителей, при этом братья будут указывать на один и тот же список. в итоге у нас получается две таблицы: [sql]create table [mo-msg-list] ( [msg-id] integer primary key, [msg-cont] text, [plist-id] int, [msg-deep] int )[/sql] [sql]create table [mo-parent-list] ( [parent-id] integer primary key, [plist-id] int, [msg-id-parent] int )[/sql] а запросы такого вида: вывод всех детей... [sql]select * from [mo-msg-list], [mo-parent-list] where [msg-id-parent]=1 and [mo-msg-list].[plist.id]=[mo-parent-list].[plist-id];[/sql] тут правда выводятся все пары узел-идПредка. на мой взгляд лучше действовать в два захода - на первом получить множество узлов, а на втором - их внутренние связи, хотя это и несколько медленнее. итого: все выборки остаются по прежнему довольно простыми, а вот апдейты упрощаются - теперь добавление братьев не требует изменений в таблице связей. плюс - сильная экономия памяти. для таблицы связей: в худшем случае - O(n^2) в лучшем - O(1) в реальных условиях думаю будет линейный, а то и логарифмический рост. ну, собственно, если никто не найдёт в этом подходе проколов, то можно будет уже писать класс для работы с этим делом, способный конкурировать с реализациями NS и таблиц смежностей. =^_^=
dark-demon Вынужден тебя огорчить, в этом методе есть свои затупы. mo-msg-list.plist-id - это обязательное поле или нет? Оно может принимать значение NULL? Если может - дерево связей действительно разгружается, но усложняются выборки и алгоритмы добавления/переноса (для каждого затрагиваемого нода нужно предварительно проверить, был ли уже построен список родителей, если нет - построить его), если же поле является обязательным - связей будет столько же, сколько и в способе ONK'а. Просто при добавлении каждой новой записи тебе придется для нее тут же добавлять список родителей => экспоненциальный рост.
поле естественно является обязательным для всех узлов дерева кроме корневого, иначе это уже будет не дерево. я наверно плохо акцентировал... поле [mo-msg-list].[plist-id] для братьев будет иметь одно и то же значение, а в таблице связей будут прописаны векторы от [plist-id] до всех [msg-id-parent]. перенос веток, конечно, не такая тривиальная вещь, как в таблице смежностей, но и не такая уж сложная. самый простой вариант - вырезать там (удалить все связи дочерних нод с предками выше корня ветви) , вставить тут (сформировать связи с новыми предками).
На сколько я понял идею,,, здесь нехватает таблицы "уровней", в которой хранились бы уникальные идентификаторы каждого элементарного уровня дерева. В таблице отношений будут лежать связи уровней со всеми предками, а в таблице элементов дерева будет указан идентификатор уровня, к которому принадлежит элемент. Т.е. количество таблиц для поддержки одного дерева возрастает до 3-х.
она тут в принципе не особо и нужна. разве что с той целью чтобы повесить на неё первичный ключ и соответственно ускорить формирование уникального [plist-id] при добавлении потомка.
dark-demon Запутался я с этим способом... как так получается, что при добавлении новых узлов у тебя не затрагивается таблица связей? Допустим, у меня есть дерево A->B (A родитель B). Связи есть. Я добавляю нод C так что A->C. Получается, что B и C - братья, следовательно, при добавлении этого нода связи править не надо. Как тогда добавлять нод D, так что C->D ? В какой момент D узнает свой путь в дереве (A->C) и откуда?