Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 160
Весьма познавательно.
Когда-то, когда появилась mysql5 с рудиментарными хранимыми процедурами, писал такую процедуру для неё, чтоб рекурсивно дерево извлекала. Но это всё равно очень криво работало :(
Когда-то, когда появилась mysql5 с рудиментарными хранимыми процедурами, писал такую процедуру для неё, чтоб рекурсивно дерево извлекала. Но это всё равно очень криво работало :(
Не обижайтесь maovrn… дальше поймете почему.
Для бухгалтерии скорости не надо, а для WEB это жизнь…
Поэтому.
Рекурсия это зло (я даже очень категоричен в этом). Теряем конроль над запросами — т.е. уже зло, плюс при хорошей нагрузке на сервер он ляжет и никакие добавления серверов не помогут, потому что нет гибкости… мы не сможим «по человечески» распараллелить сервера…
Существуют «иерархические» алгоритмы для работы с БД (например Nested Sets, вполне неплохой, но тяжелый в понимании и не совсем иерархический), но я бы назвал это псевдоиерархия…
MySQL — это реляционная модель, но извините уже отставшая от требований на сегодня. Деревья и ветвления с большой глубиной все больше входят в мир web технологий…
И всё больше и больше я слышу вопрос, а можно ли «приручить» ...SQL-и для работы с иерархическими структурами, и есть ли панацея.
Отвечу — есть. И не рекурсией, так как при нагрузке она просто «убьет» сервер…
Выход есть и уже работает. Я сделал иерархическую CMS (сейчас идет beta-тестирование, разрабатывал в общей сложности 2 года, это не клон теперешних, совершенно другая архитектура) без лишних join-ов и без рекурсии.
Я анализировал все алгоритмы более года, наконец взял всё лучшие из них и можно сказать сделал свой алгоритм. Единственный его недостаток, немного избыточность данных, но это не текст и избыточность минимальна. Зато по скорости (равномерности нагрузки) и гибкости реляционная модель курит в стороне. Причем все это реализовано даже на таком, не подготовленном к иерархии MySQL
Кстати из-за этого совсем изменилась архитектура CMS! Теперь она стала меньше, гибче и “универсальнее”. Теперь простыми правилами можно сделать как магазин, форум, социальную сеть… т е он явлеятся унифицированныи и универсальным…
То же и с нагрукой… Такую архитектуру легко распараллелить… зацепил? ;)
Для бухгалтерии скорости не надо, а для WEB это жизнь…
Поэтому.
Рекурсия это зло (я даже очень категоричен в этом). Теряем конроль над запросами — т.е. уже зло, плюс при хорошей нагрузке на сервер он ляжет и никакие добавления серверов не помогут, потому что нет гибкости… мы не сможим «по человечески» распараллелить сервера…
Существуют «иерархические» алгоритмы для работы с БД (например Nested Sets, вполне неплохой, но тяжелый в понимании и не совсем иерархический), но я бы назвал это псевдоиерархия…
MySQL — это реляционная модель, но извините уже отставшая от требований на сегодня. Деревья и ветвления с большой глубиной все больше входят в мир web технологий…
И всё больше и больше я слышу вопрос, а можно ли «приручить» ...SQL-и для работы с иерархическими структурами, и есть ли панацея.
Отвечу — есть. И не рекурсией, так как при нагрузке она просто «убьет» сервер…
Выход есть и уже работает. Я сделал иерархическую CMS (сейчас идет beta-тестирование, разрабатывал в общей сложности 2 года, это не клон теперешних, совершенно другая архитектура) без лишних join-ов и без рекурсии.
Я анализировал все алгоритмы более года, наконец взял всё лучшие из них и можно сказать сделал свой алгоритм. Единственный его недостаток, немного избыточность данных, но это не текст и избыточность минимальна. Зато по скорости (равномерности нагрузки) и гибкости реляционная модель курит в стороне. Причем все это реализовано даже на таком, не подготовленном к иерархии MySQL
Кстати из-за этого совсем изменилась архитектура CMS! Теперь она стала меньше, гибче и “универсальнее”. Теперь простыми правилами можно сделать как магазин, форум, социальную сеть… т е он явлеятся унифицированныи и универсальным…
То же и с нагрукой… Такую архитектуру легко распараллелить… зацепил? ;)
А я для теоремы Ферма чудо-доказательство придумал, идёт бета-тестирование.
Извините но совсем не смешно.
Хотите поучавствовать. Есть требования. Одно из них соглашение о неразглашении.
А так как вы шутитите — вам скорее всего откажу.
Хотите поучавствовать. Есть требования. Одно из них соглашение о неразглашении.
А так как вы шутитите — вам скорее всего откажу.
мда, как обычно стадное явление, один минус поставил — за ним потянулись остальные…
коммент то «не о чем», тем более «сарказм тема». Внутренние разборки, а у нас как обычно… кого бьют? И не разобравшись вместе со всеми забить человека — детство.
Сделайте вначале что либо, потом саркастически и поговорим. Имхо ответил правильно, потому что если бы человек хотел увидить, он бы написал: а где можно увидить, пощупать…
И вообще не понятна психология плюсующих… вы плюсуете чувство юмора или поддерживаете сарказм? Если первое, тогда не понятно минусование ответа… значит второе.
коммент то «не о чем», тем более «сарказм тема». Внутренние разборки, а у нас как обычно… кого бьют? И не разобравшись вместе со всеми забить человека — детство.
Сделайте вначале что либо, потом саркастически и поговорим. Имхо ответил правильно, потому что если бы человек хотел увидить, он бы написал: а где можно увидить, пощупать…
И вообще не понятна психология плюсующих… вы плюсуете чувство юмора или поддерживаете сарказм? Если первое, тогда не понятно минусование ответа… значит второе.
а мне просто не нравится салатовый цвет =)
Подтвердите сначала свои слова о «революционной CMS», предоставьте примеры, алгоритмы, доказательства, в конце концов, и тогда вам, может быть, поверят. Уж не обессудьте, но трындеть любой горазд. А громкие, но голословные и ничем не подкрепленные утверждения — это совсем не то, за что хотелось бы поставить плюс.
Скажите пожалуйста, а есть ли возможность поучаствовать в бетта тестировании? Я когда-то пытался сам что то такое как вы говорите реализовать, но не сил не опыта не хватило. Но уж очень интересно посмотреть на ваш прогресс в этой области.
Вы немного опоздали, её окончательно доказали 14 лет назад.
Ценное замечание. Меня вы ничем не зацепили. Все надо применять с умом. Вполне логично что иерархические запросы более требовательны к ресурсам. К тому же они не предполагают работу с графами, которые встречаются не реже деревьев.
Вообще построение дерева по всей таблице это скорее для примера. В реальной жизни всегда можно ограничить область выборки или создать агрегатную таблицу, куда попадут строки в уже правильном порядке вместе с полем level, тогда понадобится раз в день (или неделю, месяц) обновлять этот агрегат.
Любопытно было бы взглянуть на вашу CMS. Похоже при ее разработке вы применили nested sets? У этого метода есть один минус: если понадобится передвинуть какую-нибудь ветку (скажем, «Сервер 1» из примера перевезти в Лиски), придется проходить по всем дочерним записям. Впрочем, это не имеет значения, если такое поведение не предполагается или бывает крайне редким.
Вообще построение дерева по всей таблице это скорее для примера. В реальной жизни всегда можно ограничить область выборки или создать агрегатную таблицу, куда попадут строки в уже правильном порядке вместе с полем level, тогда понадобится раз в день (или неделю, месяц) обновлять этот агрегат.
Любопытно было бы взглянуть на вашу CMS. Похоже при ее разработке вы применили nested sets? У этого метода есть один минус: если понадобится передвинуть какую-нибудь ветку (скажем, «Сервер 1» из примера перевезти в Лиски), придется проходить по всем дочерним записям. Впрочем, это не имеет значения, если такое поведение не предполагается или бывает крайне редким.
NS там нет, я от него избавился очень давно. И вам советую.
Я немного намекну… я анализировал алгоритмы почти год…
Немного подсмотрел у IBM (коммерческие финансовые программы), но взял совсем немного сути.
Немного взял у NS — но только суть не архитектуру алгоритма.
Алгоритм совершенствовался полее года.
Я немного намекну… я анализировал алгоритмы почти год…
Немного подсмотрел у IBM (коммерческие финансовые программы), но взял совсем немного сути.
Немного взял у NS — но только суть не архитектуру алгоритма.
Алгоритм совершенствовался полее года.
Ну вы меня вообще заинтриговали. Обещаете рассказать когда исследования подойдут к концу?
Да вы увидите я напишу в «Я пиарюсь»…
Только судя по комментам участников (не относится к вам и другим трезвомыслящим людя), а надо ли?
Что-то после инвайтов, как то ряды разработчиков порядели… столько «детей» появилось…
Детям: вам папа говорил, что минусовать без причины — признак дурачины? Всегда надо приводить аргументы.
Только судя по комментам участников (не относится к вам и другим трезвомыслящим людя), а надо ли?
Что-то после инвайтов, как то ряды разработчиков порядели… столько «детей» появилось…
Детям: вам папа говорил, что минусовать без причины — признак дурачины? Всегда надо приводить аргументы.
Аргументы: на протяжении уже двух дней подряд от вас от вас здесь есть только куча комментов типа: «вы все дети, потому, что меня минусуете, а я сам написал cms, она революционная и использует революционные алгоритмы, но я вам её не покажу, потому, что она ещё не готова и вообще вы ничего в ней не поймёте, потому вы все дети».
Зато вы, ничего не предложив в замен, критикуете и отвергаете простое и удобное (в разработке), традиционнон решение — для работы с деревьями использовать рекурсию. Решение, кстати, которому лет больше, чем вам.
Простите, (уважаемый), вы — пустозвон.
Зато вы, ничего не предложив в замен, критикуете и отвергаете простое и удобное (в разработке), традиционнон решение — для работы с деревьями использовать рекурсию. Решение, кстати, которому лет больше, чем вам.
Простите, (уважаемый), вы — пустозвон.
То что вы «додумываете» себе — это ваше личное горе… я такого не говорил и не имел ввиду. Я пытался переубедить это заблуждение…
Показал топик другим специалистам — долго смеялись.
Далее…
Оо, вы уже перешли на личные оскорбления… :))
Так опускаться нельзя молодой человек…
Мда, мало вас папа в детстве ремнем бил наверно… ошибки в воспитании видимо, жаль в таком возрасте вы их уже не исправите.
Далее отвечаю…
Да плюньте вы на мой алгоритм, если он вам не нравится и вы его не видели (а уже обсуждаете).
Рекурсия в высокоскоростный БД, это это традиционное заблуждение. Да(!) существуют, другие алгоритмы, в конце концов… да тот же Nested Sets в 1000 раз лучше… или «материализованный путь», а есть и обьединенные эти два алгоритма…
Они тоже — универсальные. И вся выборка выполняется одним запросом! Уперлись вы в «свою» рекурсию…
Нравиться — ради бога… пользуйтесь, не хотите слушать других… ходите по кругу…
Показал топик другим специалистам — долго смеялись.
Далее…
Оо, вы уже перешли на личные оскорбления… :))
Так опускаться нельзя молодой человек…
Мда, мало вас папа в детстве ремнем бил наверно… ошибки в воспитании видимо, жаль в таком возрасте вы их уже не исправите.
Далее отвечаю…
Да плюньте вы на мой алгоритм, если он вам не нравится и вы его не видели (а уже обсуждаете).
Рекурсия в высокоскоростный БД, это это традиционное заблуждение. Да(!) существуют, другие алгоритмы, в конце концов… да тот же Nested Sets в 1000 раз лучше… или «материализованный путь», а есть и обьединенные эти два алгоритма…
Они тоже — универсальные. И вся выборка выполняется одним запросом! Уперлись вы в «свою» рекурсию…
Нравиться — ради бога… пользуйтесь, не хотите слушать других… ходите по кругу…
А статейку уже можно посмотреть где-то?
Интересно бы было сейчас почитать
Интересно бы было сейчас почитать
Так получилось, что революции не произошло, но это совсем другая история
Вы часто перемещаете ветки?
Для бухгалтерии это не часто, а для web-а так и вообще раз в полгода максимум.
Переименование ветки — гараздо чаще, но если грамотно построена архитектура то это тоже очень простой вопрос.
Для бухгалтерии это не часто, а для web-а так и вообще раз в полгода максимум.
Переименование ветки — гараздо чаще, но если грамотно построена архитектура то это тоже очень простой вопрос.
Кстати, помимо реляционных СУБД, рассмотренных мною, бывают еще и иерархические, специально заточенные под хранение иерархических данных. Мне никогда не приходилось с ними сталкиваться (если не считать реестр MS Windows), но мне кажется, раз уж предъявляются жесткие требования к производительности именно на иерархических данных, к ним стоит присмотреться.
Да ну? А как же файловые системы, LDAP (в частности, Microsoft AD), DNS? :)
Не понятно… почему Вам минус поставили… а, я понял, вы поддержали меня :)
Так как я высказываюсь довольно резко, у меня много «анти-почитателей»…
Но я всегда высказываюсь резко в только в том случае, если это по пройденному опыту, и я знаю о чем говорю.
А поставили «просто так», а ведь Вы правы ;)
Кстати для разработки иерархической БД очень много сути можно взять из файловых систем… (я взял, и доступ и расширения и еще много чего)
Просто те кто минусовали, врядли вообще что-то сделали… из разряда ламеров.
Сейчас ламеры опять заминусуют :) Ну, ну… мне от этого не хуже :))
Так как я высказываюсь довольно резко, у меня много «анти-почитателей»…
Но я всегда высказываюсь резко в только в том случае, если это по пройденному опыту, и я знаю о чем говорю.
А поставили «просто так», а ведь Вы правы ;)
Кстати для разработки иерархической БД очень много сути можно взять из файловых систем… (я взял, и доступ и расширения и еще много чего)
Просто те кто минусовали, врядли вообще что-то сделали… из разряда ламеров.
Сейчас ламеры опять заминусуют :) Ну, ну… мне от этого не хуже :))
Сейчас вас удивлю… вы сталкиваетесь каждый день! И почти каждую секунду…
Вот и ответ: FAT и другие файловые системы :)))
Вот и ответ: FAT и другие файловые системы :)))
На каком основании вы делаете вывод относительно скорости рекурсивных запросов?
Вы сами сравнивали производительность или видели какое-то исследование?
Вы сами сравнивали производительность или видели какое-то исследование?
На основе 18-летнего опыта в этой области.
Если вам не важна скорость и вам плевать на контроль запросов… пользуйтесь. Я вам не даю?
Это самый «легкий» способ, для начинающих.
Если вы хотите высокопроизводительное web приложение с высокой нагрузкой… я советую забыть про рекурсию.
О рекурсии уже давно изжевано и написано много статей.
А вам тяжело самому найти исследования? Их очень много. И все специалисты в один голос пишут, что это зло.
Если вам не важна скорость и вам плевать на контроль запросов… пользуйтесь. Я вам не даю?
Это самый «легкий» способ, для начинающих.
Если вы хотите высокопроизводительное web приложение с высокой нагрузкой… я советую забыть про рекурсию.
О рекурсии уже давно изжевано и написано много статей.
А вам тяжело самому найти исследования? Их очень много. И все специалисты в один голос пишут, что это зло.
Повелся я на ваш троллинг по поводу добра и зла. Зря вы так категоричны про рекурсию, контроль можно потерять и без рекурсии, банально написав неоптимальный запрос. В дискретной математике рекурсия так же присутствует во многих алгоритмах. Скорее велосипеды — это зло, хотя если хорошенько поискать можно и добрые велосипеды найти.
Автор, отличная статья, послал вам личное письмо по поводу включения статьи в следующий habradigest.
По поводу создания иерархий хотел бы еще и еще раз разрекламировать hierarchyId MS SQL Server 2008:
habrahabr.ru/blogs/sql/27774/
если вы дополните статью небольшим параграфом про hierarchyId, я буду просто счастлив :)
По поводу создания иерархий хотел бы еще и еще раз разрекламировать hierarchyId MS SQL Server 2008:
habrahabr.ru/blogs/sql/27774/
если вы дополните статью небольшим параграфом про hierarchyId, я буду просто счастлив :)
Очень познавательно. Попробую применить. =)
Если честно, лучше не надо…
Я описал выше почему.
Я описал выше почему.
Эй «минус», а аргументы? как обычно троллим…
опишите ещё, что конкретно применять вместо этого, тогда можно будет отказаться от этого подхода
К сожалению пока свой алгоритм выложить в паблик не могу. (читайте мои комменты «почему»)
Но могу сказать одно, даже NS и материализованный путь на порядок лучше алгоритма описанного автором.
Но могу сказать одно, даже NS и материализованный путь на порядок лучше алгоритма описанного автором.
Я уверен, что стандартные решения, предложенные производителями СУБД и описанные в данном топике, подойдут для большого круга задач. А стандартизованность и простота решения окупит себя по сравнению с «самопальными» алгоритмами, пусть даже и несколько более производительными. Конечно, если дерево станет гигантским и производительность упрется именно в иерархические запросы, возможно, придется что-нибудь переписать. Но я бы тогда начал с переосмысливания хранимых данных и попытался бы уложить их в реляционную модель. Или хотя бы ограничил область выборки. Или использовал бы агрегаты. Следует смотреть по обстоятельствам. Использование нестандартных методов, с моей точки зрения, еще большее зло чем падение производительности при рекурсии.
Если все будут говорить «все придумали до нас», не будет никакого прогресса. Я искренне желаю вам успехов с вашим алгоритмом. Но в настоящее время ваш алгоритм использовать нельзя, у NS есть свои минусы. Поэтому я не был бы столь категоричен.
Если все будут говорить «все придумали до нас», не будет никакого прогресса. Я искренне желаю вам успехов с вашим алгоритмом. Но в настоящее время ваш алгоритм использовать нельзя, у NS есть свои минусы. Поэтому я не был бы столь категоричен.
Вы шутите?
Конечно, Вам не предложат коммерческих алгоритмов… это алгоритм для… не хочу матом ругаться, тех у кого денег нет чтобы купить Oracle-вские программы и для того чтобы те кто пользуются этими «алгоритмами», «тормозили» безбожно и бежали в магазин и покупали Oracle-вские программы…
А название «самопальные» можно под 99% и-нета причесать… заканчиваем холивар. Рекурсия в БД — ЗЛО и не надо других вводить в заблуждение.
Конечно, Вам не предложат коммерческих алгоритмов… это алгоритм для… не хочу матом ругаться, тех у кого денег нет чтобы купить Oracle-вские программы и для того чтобы те кто пользуются этими «алгоритмами», «тормозили» безбожно и бежали в магазин и покупали Oracle-вские программы…
А название «самопальные» можно под 99% и-нета причесать… заканчиваем холивар. Рекурсия в БД — ЗЛО и не надо других вводить в заблуждение.
Рекурсия в БД — ЗЛО и не надо других вводить в заблуждение.
Полностью согласен. Проблемы с пониманием этого возникают у программистов, мыслящих только в процедурном ключе. Так же те не понимают как в реляционном мире SQL можно жить без for-ов, while-ов, switch-ей и if-ов… =))
Кстати, у Оракла в конструкции SELECT есть функции, работающие аналогично switch-ам (DECODE)и if-ам (IIF). Иногда их приходится применять. И не сказал бы что это плохо. Если есть инструмент, почему бы им не пользоваться. Конечно, во всем должна быть мера. Но и подходить к СУБД с позиции тупой хранилки данных, пользуясь только синтаксисом самого первого стандарта SQL-89, согласитесь, тоже не правильно.
Пардон, первым был SQL-82. Но суть предыдущего от этого не меняется.
Соглашусь =) Но…
Как раз-таки из-за того, что большинство программистов подходят к СУБД с позиции «тупой хранилки данных» — и приходится прибегать к нестандартным запросам. И вот здесь — инстументы оракла сильно вас выручают =)
Но и подходить к СУБД с позиции тупой хранилки данных, пользуясь только синтаксисом самого первого стандарта SQL-89, согласитесь, тоже не правильно.
Как раз-таки из-за того, что большинство программистов подходят к СУБД с позиции «тупой хранилки данных» — и приходится прибегать к нестандартным запросам. И вот здесь — инстументы оракла сильно вас выручают =)
СУБД — это именно хранилка данных, с интерфейсом для их занесения, перечисления и извлечения.
Вы не поняли меня. Я говорил про то, что не стоит "подходить к СУБД с позиции тупой хранилки данных(черному ящику)", т. к. этот подход в большинстве случаев приводит к печальным последствиям(за исключением проектов уровня hello world).
Даже самая «навороченная» СУБД не спасёт вас, если ваши ваши таблицы используются в качестве «свалки данных». Защиты от дурака в СУБД — нет =) Учитесь ею правильно пользоваться.
Даже самая «навороченная» СУБД не спасёт вас, если ваши ваши таблицы используются в качестве «свалки данных». Защиты от дурака в СУБД — нет =) Учитесь ею правильно пользоваться.
Ну, СУБД разные бывают. Те, интерфейс которых построен на языке SQL, как раз и надлежит рассматривать как чёрный ящик. Собственно, SQL для того и придуман, чтобы при запросе указывать только свойства нужных данных, не задумываясь о том, как именно эти данные будут найдены и аггрегированы.
Ну, СУБД разные бывают. Те, интерфейс которых построен на языке SQL, как раз и надлежит рассматривать как чёрный ящик.
Конечно, в идеале оно так и должно быть. Но в реальном мире вашим «черным ящиком» нужно ещё как-то управлять(устанавливать, настраивать, бэкапить, оптимизировать, масшабировать и т.д. — куча ньюансов) И вот здесь ваши теоретические познания SQL вам уже никак не помогут.
Полностью поддерживаю. Изначально SQL предполагался как язык конечного пользователя. Но сейчас он настолько сложен, что нужен программист. Помимо этого, все СУБД имеют в своем арсенале какие-то свои уникальные функции, методы работы и т.д.
Например, как ограничить выборку первыми N строками? Такой запрос, особенно в web, выполняется очень часто. А решается он у всех по разному: в mySQL это LIMIT(N), в PostgesSQL это LIMIT N, в Oracle rownum<=N
Например, как ограничить выборку первыми N строками? Такой запрос, особенно в web, выполняется очень часто. А решается он у всех по разному: в mySQL это LIMIT(N), в PostgesSQL это LIMIT N, в Oracle rownum<=N
А я вечный двигатель изобрел только показать не могу пока — тайна:)
Вам не кажется, что это глуповато?
Вам не кажется, что это глуповато?
Можно ещё упомянуть nested sets. Да, вникать в них надо довольно долго, но в итоге результаты на, мой взгляд, себя оправдывают. По крайней мере начинаешь видеть задачу хранения иерархий в несколько другом свете. Способ подходит для всех реляционных СУБД. Показывает своё преимущество при больших уровнях вложенности.
Для небольших деревьев я использую несколько иной подход — написал класс, который формирует дерево в памяти, загружая поля ID, PARENT_ID, TITLE обычным селектом. Для большинства задач этого вполне хватает и гибкость такого подхода оправдывает некоторый расточительный расход памяти.
В MySQL вышел из ситуации тем, что записываю полный путь элемента до корневого элемента (parents_ids=«1,3,5») т.е. уровень можно посчитать по запятым, а ветки выбираю при помощи FIND_IN_SET. Ничего нового в этом нет, но пока удачных реализаций этого метода не находил, хотябы потому что везде где видел подобную реализацию используется LIKE, а мой пока еще не оформлен должным образом чтобы вывести на паблик.
Надо попробовать, пока тоже использую LIKE.
Есть проблема с хранением полного пути вместо его генерации на лету — когда надо передвинуть узел на новое место иерархии, то придется пересчитывать и менять все потомки. А при хранении только ссылки на родителя и генерации пути на лету надо изменить только одну запись, что конечно более надежно и более эффективно. Особенно если деревья большие.
Полностью с Вами согласен, перенос веток действительно становиться проблематичной задачей в таком подходе, пока не было задач по переносу веток, а поразмышлять на досуге, времени особо нет.
Это легко делается если у вас есть id узла который меняете и есть новый алгоритм… :)
Да кстати, а вы часто перемещаете узлы? ;) Я думая, что нет… :)
Поэтому выполнить одну ресурсоемкую задачу раз в полгода, это не рекурсия которая такую нагрузку дает ежесекундно…
Да кстати, а вы часто перемещаете узлы? ;) Я думая, что нет… :)
Поэтому выполнить одну ресурсоемкую задачу раз в полгода, это не рекурсия которая такую нагрузку дает ежесекундно…
Я думаю, не лишним будет упомянуть, что оператор «with» так же есть в Oracle. И по большому счету никто не запрещает создать иерархический запрос на его основе. Хотя это из серии «а оно надо?». Все же «with» в Oracle удобно использовать для других целей, а не только построения иерархий.
Оператор with в Oracle используется. В частности в конструкции START WITH. Можно с его помощью создать представление. Но вот обратиться к нему в процессе создания этого представления, как в синтаксисе SQL-1999 у меня не получилось (может руки не от туда ростут :-( ). Не могли бы вы написать правильный запрос? Кстати, я сейчас проверял на Oracle 10.
Я говорила про конструкцию типа:
with
rec1 as ( select * from dual),
rec2 as ( select * from dual)
select *
from rec1, rec2;
Наверное, не совсем так выразилась. Я имела в виду, что в оракле есть похожая конструкция «with» использующихся для немного других целей.
И что она очень похожа на:
WITH [recursive] имя_алиаса_запроса [ (список столбцов) ]
AS (запрос)
основной запрос
with
rec1 as ( select * from dual),
rec2 as ( select * from dual)
select *
from rec1, rec2;
Наверное, не совсем так выразилась. Я имела в виду, что в оракле есть похожая конструкция «with» использующихся для немного других целей.
И что она очень похожа на:
WITH [recursive] имя_алиаса_запроса [ (список столбцов) ]
AS (запрос)
основной запрос
Что-бы тут написать такое, чтобы сказать что прочитал с удовольствием, и не схлопотать минус?
«Чтобы понять рекурсию, сначала надо понять рекурсию». — завис.
А почему человеку влепили минус?
Вы не вдумались, а он почти прав… когда разработчик теряет конроль над запросами — то жди «даун»
Вы не вдумались, а он почти прав… когда разработчик теряет конроль над запросами — то жди «даун»
Nested Sets, не требует рекурсии, правда все очень интересно запутано, но если один раз распутатся и написать клас обертку, то потом можно не заморачиватся. Вот отличная статейка с примерами www.getinfo.ru/article610.html
Удаление элемента из netsted set очень ресурсоемкая операция.
Согласен, но вобщем все зависит от задачи, например в моей задаче то иерархический список только дополняется обьектами, ну и выборка само собой. Но зато плюс в том что не нужна никакая рекурсия, и это мне определенно нравится.
Хотя… может и мнение мое субьективное, всетаки еще смотря от количества элементов… тоесть при одном-десяти элэментах, разницы в скорости, что например это долго, я не видел. Возможно при большем количестве обьектов буду видеть разницу скорости. Но повторю что сама структура хранения и операции над ней мне нравятся, хоть и не доходил до пиковых каких-то пределов.
Рекурсия — это зло.
Когда разработчик теряет контроль над запросами (а в рекурсии так оно есть) — жди «дауна»
Когда разработчик теряет контроль над запросами (а в рекурсии так оно есть) — жди «дауна»
За то что рекурсия это зло, я согласен, поэтому ее не использую =) Ну в крайнем случае если есть обходной вариант =) Поэтому и использую NS =)
Слава богу от NS я избавился и ничуть не сожалею. Наоборот.
Пользуюсь совсем другим алгоритмом.
Пользуюсь совсем другим алгоритмом.
И еще забыли добавить… если вдруг сбой (потеря например записи)… при NS нарушается целостность структуры…
NS это скорее псеводоиерархия. Какае-то «плоская иерархия» :)
А вообще, про все это я написал выше
NS это скорее псеводоиерархия. Какае-то «плоская иерархия» :)
А вообще, про все это я написал выше
Я вот недавно реализовал дерево так:
выбрал все данные из базы в одномерный масив обьектов, где сделал индек равный ID
затем делаю один проход в цикле и если PID не равен нулю делаю такую штуку:
$pages[PID]->child = &$pages[ID];
Интересует мнение имеет ли такое решение право на жизнь?
выбрал все данные из базы в одномерный масив обьектов, где сделал индек равный ID
затем делаю один проход в цикле и если PID не равен нулю делаю такую штуку:
$pages[PID]->child = &$pages[ID];
Интересует мнение имеет ли такое решение право на жизнь?
Проблема выбрать значение только одной какой нибудь ветки.
Такое решение имеет право на жизнь, при сравнительно небольшом количестве элементов, но пример вашего кода так будет выглядеть правильнее: $pages[PID]->child[] = &$pages[ID];
А в противном случае у каждого узла может быть _только_ по одному варианту…
А в противном случае у каждого узла может быть _только_ по одному варианту…
Тоже ресурсоемкий… есть подход гараздо легче.
Ну вот, теперь нам, ораклоидам, все завидывать будут! :)
Спасибо, очень интересно.
Рекурсия порой печально, но иногда приходится.
Можно пойти немного по-другому способу:
id (varchar) | title (varchar)
aa | Россия
aaaa | Москва
aaab | Санкт-Петербург
aaabaa | Павловск
aaabab | Торфяное
aaac | Владивосток
…
aaza | Мухосранск
ab | Англия
ac | Китай
Как выбрать всю ветку из России?
Пишу по-русски, т.к. MySQL давно не использовал
ВЫБРАТЬ ВСЁ, ЧТО В ИДЕНТИФИКАТОРЕ НАЧИНАЕТСЯ С 'aa'.
Как выбрать всю ветку из России, не включая Россию?
ВЫБРАТЬ ВСЁ, ЧТО В ИДЕНТИФИКАТОРЕ НАЧИНАЕТСЯ С 'aa' И STRLEN(id) > STRLEN('aa')
Ну и т.д. Вдруг кому пригодится.
Можно пойти немного по-другому способу:
id (varchar) | title (varchar)
aa | Россия
aaaa | Москва
aaab | Санкт-Петербург
aaabaa | Павловск
aaabab | Торфяное
aaac | Владивосток
…
aaza | Мухосранск
ab | Англия
ac | Китай
Как выбрать всю ветку из России?
Пишу по-русски, т.к. MySQL давно не использовал
ВЫБРАТЬ ВСЁ, ЧТО В ИДЕНТИФИКАТОРЕ НАЧИНАЕТСЯ С 'aa'.
Как выбрать всю ветку из России, не включая Россию?
ВЫБРАТЬ ВСЁ, ЧТО В ИДЕНТИФИКАТОРЕ НАЧИНАЕТСЯ С 'aa' И STRLEN(id) > STRLEN('aa')
Ну и т.д. Вдруг кому пригодится.
а теперь передвиньте Санкт-Петербург в Китай! Придется менять рекурсивно все потомки! вместо одно только Питера
UPDATE table SET id = CONCAT( [id-китая], SUBSTR( id, STRLEN([id-России]) ) WHERE SUBSTR(id, 0, STRLEN([id-России]) = [id-России]
Один запрос
Один запрос
не о количестве запросов же речь, а о количестве редактируемых записей
Перенос ветки — не часто выполняемая операция. Обработать пару миллионов записей один раз в месяц можно.
ну я не был бы столь категоричен.
соглашусь, что в большинстве случаев применения деревьев, модификация не частый случай
но например в разных оптимизационных задачах это может быть рутинной операцией исполняемой тысячи и миллионы раз
соглашусь, что в большинстве случаев применения деревьев, модификация не частый случай
но например в разных оптимизационных задачах это может быть рутинной операцией исполняемой тысячи и миллионы раз
Проблема программистов в том, что для них есть только 3 числа: 0, 1 и бесконечность. Т.е., числа 350 нет. Программист не может осознать тот факт, что как не старайся, но в данном случае не будет больше 350 элементов. Если элементов больше одного, то надо сделать так, чтобы работало и 2 элемента и 2 миллиона элементов. Хотя ведь их ну никак не будет больше 350. Это не в обиду, это одно из наблюдений проектировщиков интерфейсов. Я лишь цитирую. Число 350 взято с потолка, также может быть и 14.
Разные оптимизационные задачи составляют не такой уж и большой процент от общего числа задач. Да, я не настаиваю на том, что этот подход суперотличен. Я им сам уже давно не пользуюсь. Но для интернет-магазина с рубрикатором до 100 веток его вполне достаточно.
А сейчас я использую ltree в PostgreSQL. Вполне себе неплохо. Принцип немного похож. На нем работает dmoz.org, так что с производительностью там тоже неплохо.
Разные оптимизационные задачи составляют не такой уж и большой процент от общего числа задач. Да, я не настаиваю на том, что этот подход суперотличен. Я им сам уже давно не пользуюсь. Но для интернет-магазина с рубрикатором до 100 веток его вполне достаточно.
А сейчас я использую ltree в PostgreSQL. Вполне себе неплохо. Принцип немного похож. На нем работает dmoz.org, так что с производительностью там тоже неплохо.
Ребята если вы такой запрос покажите в нормальной фирме… с вами и разговаривать не будут…
извините конечно… но подставлять тут же высчитываемые данные при помощи CONCAT SUBSTR знаете что сделает? Подумайте сами.
Я дам подсказку: index
извините конечно… но подставлять тут же высчитываемые данные при помощи CONCAT SUBSTR знаете что сделает? Подумайте сами.
Я дам подсказку: index
Я это написал для того, чтобы показать, что это можно сделать одним запросом. Не ставя задачу, сделать это быстро и сверхкачественно. К тому же MySQL-ем уже давно не пользуюсь, поэтому и данный способ не использую. Ну и в дополнение, как я уже писал выше: для дерева из 100 веток этот запрос не смертелен. Для 1000 тоже. А для бесконечности — часто ли такие задачи возникают?
Одним запросом? union фактически еще подключение запроса, плюс ко всему рекурсия… это совсем не «один» запрос.
На вторую часть вопроса отвечу…
для бухгалтерии не смертельно, они ждут отчетов и по полчаса…
для web-а — 1 секунад это уже вечность…
По маркетинговым исследованиям, если юзер не увидел страницу в течении 5-х секунд, 80% (для 3-х — 60%) — что он её закроет и больше не зайдет… для Web-a это равносильно гибели проекта.
На вторую часть вопроса отвечу…
для бухгалтерии не смертельно, они ждут отчетов и по полчаса…
для web-а — 1 секунад это уже вечность…
По маркетинговым исследованиям, если юзер не увидел страницу в течении 5-х секунд, 80% (для 3-х — 60%) — что он её закроет и больше не зайдет… для Web-a это равносильно гибели проекта.
Ой сорри я немного перепутал…
1-ю часть ответа это автору статьи :)
Но вторая часть ответа подходит и под первую…
Вы проверяли как у вас в таких запросах используются индексы?
1-ю часть ответа это автору статьи :)
Но вторая часть ответа подходит и под первую…
Вы проверяли как у вас в таких запросах используются индексы?
Тут проблема: а если буквы алфавита кончатся?
Все деревья конечны. Не бывает бесконечных деревьев. Если планируется делать ну очень огромный список, можно составные части ключей делать не из двух символов, а из 5 или 10.
Сколько вариантов может дать звено из 10 англоязычных символов? Если я правильно помню математику, то либо 10^26 либо 26^10. Нормально получается.
На самом деле и 5 хватит: 5^26 = 1490116119384765625 вариантов соседей одной ветки.
Сколько вариантов может дать звено из 10 англоязычных символов? Если я правильно помню математику, то либо 10^26 либо 26^10. Нормально получается.
На самом деле и 5 хватит: 5^26 = 1490116119384765625 вариантов соседей одной ветки.
Уж математику-то я напомню: 10 символов, каждый имеет 26 разных значений — 26^10 вариантов (проверочное слово: 8 символов, 2 различных значения — 2^8 = 256 вариантов).
Неудобно всё равно получается со строкой. Хотя в типичных проектах (скажем, тот же хабр) действительно такая строка в целом не разрастётся больше, скажем, 20-ти символов. Комментарии более 10 уровней нечасто попадаются :)
Неудобно всё равно получается со строкой. Хотя в типичных проектах (скажем, тот же хабр) действительно такая строка в целом не разрастётся больше, скажем, 20-ти символов. Комментарии более 10 уровней нечасто попадаются :)
С рекурсиями в запросах давно разобрался для MS SQL и Oracle, но всё равно почитал с удовольствием, спасибо!
Тип данных ltree: www.postgresql.org/docs/8.3/static/ltree.html
Рекурсия — весьма себе ресурсоемкий процесс. Кроме того требующий от разработчика наличия определенной фантазии. А иногда вообще ставит в тупик и ощущения безысходности и опустошения =))
(опечатался по Фрейду — написал безысКОДности — успел исправить)
Поэтому я больше ими не пользуюсь. Один умный парень придумал Nested Sets — и это очень sexy.
www.dbmsmag.com/9603d06.html
threebit.net/tutorials/nestedset/tutorial1.html
а вот по-русски
www.getinfo.ru/article610.html
(опечатался по Фрейду — написал безысКОДности — успел исправить)
Поэтому я больше ими не пользуюсь. Один умный парень придумал Nested Sets — и это очень sexy.
www.dbmsmag.com/9603d06.html
threebit.net/tutorials/nestedset/tutorial1.html
а вот по-русски
www.getinfo.ru/article610.html
NS тоже не выход, существует лучше алгоритм :)
здесь :)
NS это плоская псевдоиерархия, которая тяжело распараллеливается, у которой целостность слабая… да и еще много недостатков.
здесь :)
NS это плоская псевдоиерархия, которая тяжело распараллеливается, у которой целостность слабая… да и еще много недостатков.
вставляет, конечно, подольше.
где-то начиная с тысячного узла в середку дерева аккурат по минуте на узел (дерево многоуровневое и ветвистое).
это уже (sorry for my english), не вставляет ни фига.
а вообще самая большая проблема с деревьями — не выбора ветки от единого родителя (эта вещь оптимально делается не рекурсией, а скорее циклом — поличество запросов равно уровню вложенности, посему в самом худшем случае (дерево у нас — лиана или виноград какой-то, и каждая ветка имеет ровно одного потомка) эта штука будет работать с той же скоростью, что рекурсия, в лучшем же — намного быстрее) а правильной сортировки выбранного. И тут возможны варианты (помимо nested sets — потому как с обновлениями и вставками на нем все просто совсем ахово получается).
где-то начиная с тысячного узла в середку дерева аккурат по минуте на узел (дерево многоуровневое и ветвистое).
это уже (sorry for my english), не вставляет ни фига.
а вообще самая большая проблема с деревьями — не выбора ветки от единого родителя (эта вещь оптимально делается не рекурсией, а скорее циклом — поличество запросов равно уровню вложенности, посему в самом худшем случае (дерево у нас — лиана или виноград какой-то, и каждая ветка имеет ровно одного потомка) эта штука будет работать с той же скоростью, что рекурсия, в лучшем же — намного быстрее) а правильной сортировки выбранного. И тут возможны варианты (помимо nested sets — потому как с обновлениями и вставками на нем все просто совсем ахово получается).
Ага это NS — узнаю :)
Знаете, есть алгоритмы быстрее, вот что я скажу… я выше писал уже о них.
NS — плоский псевдоиерархический алгоритм, с кучей недостатков. Вот просто в паблике пока ничего нет лучше… а в коммерческих проектах — есть :)
Знаете, есть алгоритмы быстрее, вот что я скажу… я выше писал уже о них.
NS — плоский псевдоиерархический алгоритм, с кучей недостатков. Вот просто в паблике пока ничего нет лучше… а в коммерческих проектах — есть :)
ну, мы тоже используем свои алгоритмы. Правда, разрабатываем их чуть подольше. В целом сейчас оно уже работает вполне удволетворительно (кусок дерева — чтобы использовались индексы — вложенностью 10, объемом где-то в 30000 узлов отрабатывается примерно за 1 — 2 секунды, а с закешированным запросом — раз в 100 быстрее). Правда, наше решение катит только под PostgreSQL (возможно будет работать и под ораклом, если оно шагнуло вперед после 2001 года).
А под мускуль существует альтернатива на dklab — изящный и очень быстрый запрос, правда, с ограничением по вложенности — не более 32 уровней (или 31).
А под мускуль существует альтернатива на dklab — изящный и очень быстрый запрос, правда, с ограничением по вложенности — не более 32 уровней (или 31).
Я тестировал на уровнях вложенности ~20 (больше у меня почему-то не получается придумать для Web задачи :)
и 100`000 записях (сколько узлов не считал), главная страница… Ctrl-P:
Всего 32: 0.025
Всего &php: 0.241
На сколько я помню на dklab всё что связано с иерархией затихло… тот алгоритм что у них есть, назвать тяжело алгоритмом.
Он очень сырой… люди там встретили трудности (а трудности там были немалые, да еще и с кучей join) и… забросили всё это дело подальше :) Это было кажется года 2-3 назад… dbtree кажись называлась.
:) Могу теперь с оглядкой на 3 года назад только улыбнуться :)
и 100`000 записях (сколько узлов не считал), главная страница… Ctrl-P:
Всего 32: 0.025
Всего &php: 0.241
На сколько я помню на dklab всё что связано с иерархией затихло… тот алгоритм что у них есть, назвать тяжело алгоритмом.
Он очень сырой… люди там встретили трудности (а трудности там были немалые, да еще и с кучей join) и… забросили всё это дело подальше :) Это было кажется года 2-3 назад… dbtree кажись называлась.
:) Могу теперь с оглядкой на 3 года назад только улыбнуться :)
Гы. Я использую, правда для вложенности не более 3-х.
И только для вычисления агрегатной таблицы.
Преимущество этого способа вижу только в том, что он обладает атомарностью — во время выполнения никакая зараза не сможет модифицировать MyISAM таблицу.
Минус у способа один и очень существенный — размер SQL запроса сильно увеличивается с уровнем вложенности.
Но этот монстроидальный запрос работает довольно шустро.
И только для вычисления агрегатной таблицы.
Преимущество этого способа вижу только в том, что он обладает атомарностью — во время выполнения никакая зараза не сможет модифицировать MyISAM таблицу.
Минус у способа один и очень существенный — размер SQL запроса сильно увеличивается с уровнем вложенности.
Но этот монстроидальный запрос работает довольно шустро.
Размер увеличивается join-ами?
join`ы — это сущие пустяки. Проблема в вычислении нужных полей — приходится много условий проверять, чтобы определить какого уровня текущая запись. Если подскажете как оптимизировать, с удовольствием перейму опыт :)
Запрос такой (алгоритм тщательно не разрабатывался и не скрывается от общественности):
UPDATE catalog_tree, (
SELECT t0.cid,
CASE WHEN t0.pid=0 THEN t0.shown
WHEN t1.pid=0 AND t0.shown>0 THEN t1.shown
WHEN t2.pid=0 AND t0.shown>0 AND t1.shown>0 THEN t2.shown
ELSE 0 END AS shown,
CASE WHEN t0.pid=0 THEN 0
WHEN t1.pid=0 THEN 1
ELSE 2 END AS level,
CASE WHEN t0.pid=0 THEN t0.cid
WHEN t1.pid=0 THEN t1.cid
WHEN t2.pid=0 THEN t2.cid
ELSE 0 END AS id0,
CASE WHEN t0.pid=0 THEN t0.title
WHEN t1.pid=0 THEN t1.title
WHEN t2.pid=0 THEN t2.title
ELSE 0 END AS title0,
CASE WHEN t0.pid=0 THEN 0
WHEN t1.pid=0 THEN t0.cid
WHEN t2.pid=0 THEN t1.cid
ELSE 0 END AS id1,
CASE WHEN t0.pid=0 THEN ''
WHEN t1.pid=0 THEN t0.title
WHEN t2.pid=0 THEN t1.title
ELSE 0 END AS title1,
CASE WHEN t0.pid=0 THEN 0
WHEN t1.pid=0 THEN 0
WHEN t2.pid=0 THEN t0.cid
ELSE 0 END AS id2,
CASE WHEN t0.pid=0 THEN ''
WHEN t1.pid=0 THEN ''
WHEN t2.pid=0 THEN t0.title
ELSE 0 END AS title2,
CASE WHEN t0.pid=0 THEN CONCAT(LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0'),'000000000000000000000000')
WHEN t1.pid=0 THEN CONCAT(LPAD(HEX(t1.sort),4,'0'),LPAD(HEX(t1.cid),8,'0'),
LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0'),'000000000000')
WHEN t2.pid=0 THEN CONCAT(LPAD(HEX(t2.sort),4,'0'),LPAD(HEX(t2.cid),8,'0'),
LPAD(HEX(t1.sort),4,'0'),LPAD(HEX(t1.cid),8,'0'),
LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0')) END AS srt
FROM
catalog_tree t0
LEFT JOIN catalog_tree t1 ON (t0.pid=t1.cid)
LEFT JOIN catalog_tree t2 ON (t1.pid=t2.cid)
) AS v_catalog_tree
SET catalog_tree.shown=v_catalog_tree.shown,
catalog_tree.level=v_catalog_tree.level,
catalog_tree.id0=v_catalog_tree.id0,
catalog_tree.title0=v_catalog_tree.title0,
catalog_tree.id1=v_catalog_tree.id1,
catalog_tree.title1=v_catalog_tree.title1,
catalog_tree.id3=v_catalog_tree.id3,
catalog_tree.title3=v_catalog_tree.title3,
catalog_tree.srt=v_catalog_tree.srt
WHERE catalog_tree.cid=v_catalog_tree.cid
Запрос такой (алгоритм тщательно не разрабатывался и не скрывается от общественности):
UPDATE catalog_tree, (
SELECT t0.cid,
CASE WHEN t0.pid=0 THEN t0.shown
WHEN t1.pid=0 AND t0.shown>0 THEN t1.shown
WHEN t2.pid=0 AND t0.shown>0 AND t1.shown>0 THEN t2.shown
ELSE 0 END AS shown,
CASE WHEN t0.pid=0 THEN 0
WHEN t1.pid=0 THEN 1
ELSE 2 END AS level,
CASE WHEN t0.pid=0 THEN t0.cid
WHEN t1.pid=0 THEN t1.cid
WHEN t2.pid=0 THEN t2.cid
ELSE 0 END AS id0,
CASE WHEN t0.pid=0 THEN t0.title
WHEN t1.pid=0 THEN t1.title
WHEN t2.pid=0 THEN t2.title
ELSE 0 END AS title0,
CASE WHEN t0.pid=0 THEN 0
WHEN t1.pid=0 THEN t0.cid
WHEN t2.pid=0 THEN t1.cid
ELSE 0 END AS id1,
CASE WHEN t0.pid=0 THEN ''
WHEN t1.pid=0 THEN t0.title
WHEN t2.pid=0 THEN t1.title
ELSE 0 END AS title1,
CASE WHEN t0.pid=0 THEN 0
WHEN t1.pid=0 THEN 0
WHEN t2.pid=0 THEN t0.cid
ELSE 0 END AS id2,
CASE WHEN t0.pid=0 THEN ''
WHEN t1.pid=0 THEN ''
WHEN t2.pid=0 THEN t0.title
ELSE 0 END AS title2,
CASE WHEN t0.pid=0 THEN CONCAT(LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0'),'000000000000000000000000')
WHEN t1.pid=0 THEN CONCAT(LPAD(HEX(t1.sort),4,'0'),LPAD(HEX(t1.cid),8,'0'),
LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0'),'000000000000')
WHEN t2.pid=0 THEN CONCAT(LPAD(HEX(t2.sort),4,'0'),LPAD(HEX(t2.cid),8,'0'),
LPAD(HEX(t1.sort),4,'0'),LPAD(HEX(t1.cid),8,'0'),
LPAD(HEX(t0.sort),4,'0'),LPAD(HEX(t0.cid),8,'0')) END AS srt
FROM
catalog_tree t0
LEFT JOIN catalog_tree t1 ON (t0.pid=t1.cid)
LEFT JOIN catalog_tree t2 ON (t1.pid=t2.cid)
) AS v_catalog_tree
SET catalog_tree.shown=v_catalog_tree.shown,
catalog_tree.level=v_catalog_tree.level,
catalog_tree.id0=v_catalog_tree.id0,
catalog_tree.title0=v_catalog_tree.title0,
catalog_tree.id1=v_catalog_tree.id1,
catalog_tree.title1=v_catalog_tree.title1,
catalog_tree.id3=v_catalog_tree.id3,
catalog_tree.title3=v_catalog_tree.title3,
catalog_tree.srt=v_catalog_tree.srt
WHERE catalog_tree.cid=v_catalog_tree.cid
Небольшое пояснение. Дерево построено по простейшей схеме родитель-ребенок.
Введены вычислимые поля сортировки и пути к корню для ускорения выборок и осуществления обратной совместимости со старой версией каталога, которая дерево держала в 3-х таблицах.
PS: Уже можно насчитать 5 способов хранения дерева в таблице:
1) id-parent_id
2) NS
3) Path to root
4) Разбиение каждого уровня по отдельным таблицам
5) X — загадочный очень производительный способ, но не известный общественности :)
Введены вычислимые поля сортировки и пути к корню для ускорения выборок и осуществления обратной совместимости со старой версией каталога, которая дерево держала в 3-х таблицах.
PS: Уже можно насчитать 5 способов хранения дерева в таблице:
1) id-parent_id
2) NS
3) Path to root
4) Разбиение каждого уровня по отдельным таблицам
5) X — загадочный очень производительный способ, но не известный общественности :)
Могу посоветовать как делает IBM в своих коммерческих программах…
Они хранят id-шники ветки
id | id1 | id2 | id3…
где если ничего нет то 0, всей ветки т.е. последний id ветки будет свой же id
тогда очень легко делать и выборку и обновление… если знаешь id узла спокойно апдейтишь
в стиле UPDATE… WHERE id3 (например) = 12345
и в таком же духе…
А выборку тоже очень легко делать
SELECT
…
WHERE
id2 =2
// и ограничиваем по ветке
id5=0
Немного избыточно, но очень быстро и очень гибко.
Они хранят id-шники ветки
id | id1 | id2 | id3…
где если ничего нет то 0, всей ветки т.е. последний id ветки будет свой же id
тогда очень легко делать и выборку и обновление… если знаешь id узла спокойно апдейтишь
в стиле UPDATE… WHERE id3 (например) = 12345
и в таком же духе…
А выборку тоже очень легко делать
SELECT
…
WHERE
id2 =2
// и ограничиваем по ветке
id5=0
Немного избыточно, но очень быстро и очень гибко.
Пора бы уже mysql добавить возможность работы с рекурсивными запросами.
Эмм, по поводу MySQL…
set @a = '444'; # root id
select *, @a := concat_ws(',', @a, ID) from TreeItems where parentID IN (@a);
Разве не подходит? Или я что-то упустил?
set @a = '444'; # root id
select *, @a := concat_ws(',', @a, ID) from TreeItems where parentID IN (@a);
Разве не подходит? Или я что-то упустил?
Небольшие поправки. Вот это:
Работает только в 10g, в версиях ниже выдается ORA-01473: cannot have subqueries in CONNECT BY clause.
А вот такое, почему-то, в 9-ке выдает всего одну строку вместо 10 (почему — не знаю):
SELECT rownum as rn FROM dual CONNECT BY level <= (SELECT max(id) FROM test_table);
Работает только в 10g, в версиях ниже выдается ORA-01473: cannot have subqueries in CONNECT BY clause.
А вот такое, почему-то, в 9-ке выдает всего одну строку вместо 10 (почему — не знаю):
SELECT 1, level FROM dual CONNECT BY rownum <=10
Хм, интересно. У меня как раз 10g и оба запроса работают как надо. Если найду решение для 9-ки, дам знать.
Вот здесь: www.sqlsnippets.com/en/topic-11821.html в разделе «Gotchas» и подразделе «Issues» как-то мутно объясняют, что, де, это из-за того, что CONNECT BY обязан содержать PRIOR, и приводят рабочий вариант для девятки:
select * from (select level from dual connect by level < 10) ;
Да, именно так. На sql.ru обсуждалась такая бага 9-ки.
Спасибо большое за статью! Честно говоря, раньше не слышал об иерархии в базах. Думаю, что не я один :)
Если бы делал показ дерева на сайте, поступил бы так же, как Вы описали — загрузка верхнего уровня, затем подзапрос по клику на узел.
Добавляю статью в избранное.
P.S. Исправьте, пожалуйста «ни раз» -> «не раз».
Если бы делал показ дерева на сайте, поступил бы так же, как Вы описали — загрузка верхнего уровня, затем подзапрос по клику на узел.
Добавляю статью в избранное.
P.S. Исправьте, пожалуйста «ни раз» -> «не раз».
И всё бы хорошо, да только полный граф этими запросами в Оракле не получишь.
Народ, честно, не могу понять практического применения описанных запросов, с точки зрения конечного продукта, а не академических или консольных задач. Сколько работал с иерархическими данными нигде на уровне базы и SQL-запросов не нужно было выбирать все дерево, а если и нужно было, то обычного selectа и orderа хватало. А задачи были от навороченных отчетов, до достроения OLAP-системы на реляционной Sybase 9 в банке. Может приведет кто-то конкретный пример применения?
Что-то никто не спешит отвечать, буду сам отдуваться. Я никогда не слышал о крупных проектах, использющих иерархические данные способом, описанным в статье. Возможно такие есть, но, скорее всего, нет. Применимость иерархических запросов можно выделить в большую группу мелких и средних проектов.
Для них это приемлемо потому что:
1. Структура данных становится простой и понятной.
2. Код не загроможден лишними функциями обработки строк для построения дерева средствами внешнего для SQL языка.
3. Гораздо быстрее написать несколько команд иерархического запроса, чем городить огород.
4. Используются стандартные методы. Программисту, который будет заниматься поддержкой и развитием, будет проще разобраться.
А минус всего один: относительно низкая производительность.
Пока плюсы перекрывают минус, почему бы не использовать. Я лично применял несколько раз, когда требовалось отобразить дерево.
Или товарищей чисто от самого факта «более низкая производительность» коробит? Так давайте все на си писать, никаких php, ruby и т.д. — они же медленнее.
Для них это приемлемо потому что:
1. Структура данных становится простой и понятной.
2. Код не загроможден лишними функциями обработки строк для построения дерева средствами внешнего для SQL языка.
3. Гораздо быстрее написать несколько команд иерархического запроса, чем городить огород.
4. Используются стандартные методы. Программисту, который будет заниматься поддержкой и развитием, будет проще разобраться.
А минус всего один: относительно низкая производительность.
Пока плюсы перекрывают минус, почему бы не использовать. Я лично применял несколько раз, когда требовалось отобразить дерево.
Или товарищей чисто от самого факта «более низкая производительность» коробит? Так давайте все на си писать, никаких php, ruby и т.д. — они же медленнее.
ничего себе, промазал как-то комментом…
см. ниже :)
см. ниже :)
Данным способом существуют только масса мелких проектов…
Для больших и сильнонагруженных используются в основном другие алгоритмы.
Я вообще не понимаю. Очень многие разработчики используют БД как хранилище данных и полностью забывают про архитектуру.
Для тех, кто использует БД как хранилище данных и предназначена рекурсия… это как отмычка. Для всех замков: долго — но может откроет… В коммерческих проектах — так делать нельзя. Надо подходить сначала к БД -как к архитектуре.
Для больших и сильнонагруженных используются в основном другие алгоритмы.
Я вообще не понимаю. Очень многие разработчики используют БД как хранилище данных и полностью забывают про архитектуру.
Для тех, кто использует БД как хранилище данных и предназначена рекурсия… это как отмычка. Для всех замков: долго — но может откроет… В коммерческих проектах — так делать нельзя. Надо подходить сначала к БД -как к архитектуре.
Спасибо за ответ. Позвольте прокомментировать Ваши ответы.
1. Структура данных от запроса не зависит.
2. Согласен
3. Если для консоли, то да, а если на туже HTML-страницу вывести со всеми стилями и прочим? Ведь весь огород городится для презентационности представления.
4. Спорный вопрос, я бы не сказал, что подобные запросы настолько изящны, что в них легко разбираться.
А вот вопрос производитеьности к получению данных имеет самое прямое отношение. Честно говоря, жалко людей, у которых на генерацию всяких отчетов уходит очень много времени.
1. Структура данных от запроса не зависит.
2. Согласен
3. Если для консоли, то да, а если на туже HTML-страницу вывести со всеми стилями и прочим? Ведь весь огород городится для презентационности представления.
4. Спорный вопрос, я бы не сказал, что подобные запросы настолько изящны, что в них легко разбираться.
А вот вопрос производитеьности к получению данных имеет самое прямое отношение. Честно говоря, жалко людей, у которых на генерацию всяких отчетов уходит очень много времени.
Тогда и прокомментирую.
1. Это скорее относилось к структуре данных по отношению к методу NS: нумерация строк и ссылки на родителей гораздо понятнее левых и правых сторон.
3. При выводе на веб-страницу, достаточно обворачивать каждую строку (вернее поля строки) в HTML-теги в порядке поступления строк без всякой дополнительной обработки.
4. Дело вкуса, не буду спорить.
Я не думаю что отчет должен содержать миллионы строк. Зачем это человеку? А выборка из сотни-другой строк происходит настолько быстро, что человек не в состоянии заметить разницы, какой вид запроса применял программист.
1. Это скорее относилось к структуре данных по отношению к методу NS: нумерация строк и ссылки на родителей гораздо понятнее левых и правых сторон.
3. При выводе на веб-страницу, достаточно обворачивать каждую строку (вернее поля строки) в HTML-теги в порядке поступления строк без всякой дополнительной обработки.
4. Дело вкуса, не буду спорить.
Я не думаю что отчет должен содержать миллионы строк. Зачем это человеку? А выборка из сотни-другой строк происходит настолько быстро, что человек не в состоянии заметить разницы, какой вид запроса применял программист.
Разрешите контр-аргументы.
1) Для простых и понятных структур данных статьи пишут совсем другого характера.
2) Язык SQL не предназначен для решения подобного рода задач, поэтому решение получается чрезвычайно кривым и сильно зависимым от конкретного производителя RDBMS. Согласен, что функции построения дерева нужно инкапсулировать в какой-то изолированый модуль, но при грамотной архитектуре, это не большая проблема.
3) Гораздо быстрее реализовать и затем легче поддерживать древовидные структуры с помощью паттерна Composite на уровне более развитого языка программирования, и не городить огород.
4) Используются не стандартные методы, как уже упомянулось в п. 2. Рабозбраться с этой хренотенью будет реально тяжело. Программист должен быть experienced в конкретной базе данных.
Про performance и scalability говорить не будем.
1) Для простых и понятных структур данных статьи пишут совсем другого характера.
2) Язык SQL не предназначен для решения подобного рода задач, поэтому решение получается чрезвычайно кривым и сильно зависимым от конкретного производителя RDBMS. Согласен, что функции построения дерева нужно инкапсулировать в какой-то изолированый модуль, но при грамотной архитектуре, это не большая проблема.
3) Гораздо быстрее реализовать и затем легче поддерживать древовидные структуры с помощью паттерна Composite на уровне более развитого языка программирования, и не городить огород.
4) Используются не стандартные методы, как уже упомянулось в п. 2. Рабозбраться с этой хренотенью будет реально тяжело. Программист должен быть experienced в конкретной базе данных.
Про performance и scalability говорить не будем.
Зерно истины есть в ваших словах. Не буду спорить. Мне вот только непонятно, что это за гипотетический программист такой, котороый может разобраться с Composite или другим модулем для построения дерева, но при этом не в состоянии осилить несколько команд sql-запроса. И еще по поводу пункта 4: очень желательно чтобы программист был осведомлен о возможностях СУБД, с которой он работает. Потому что в каждой есть свои нюансы. В одной надо делать так, в другой иначе, в третьей можно и так, и эдак. Нельзя весь функционал базы данных сводить к кроссплатформенному SELECT * FROM…, и потом дообробатывать внешними средствами.
sql хоть и не прдназначен для иерархических данных, но при грамотном подходе научить можно.
Добавлю в копилку автора, запрос на выборку всех потомков для заданного родителя, для СУБД MaxDB.
declare c cursor for with recursive tree (node_id, node_pid, node_level) as
( select id, pid, 0
from test_table where Условие_выборки_родительского_элемента
union all
select id, pid, node_level+1
from test_table, tree
where tree.node_id = test_table.pid
)
select node_id
from tree
order by node_level
declare c cursor for with recursive tree (node_id, node_pid, node_level) as
( select id, pid, 0
from test_table where Условие_выборки_родительского_элемента
union all
select id, pid, node_level+1
from test_table, tree
where tree.node_id = test_table.pid
)
select node_id
from tree
order by node_level
Мои 5 копеек по поводу репрессий в отношении рекурсий: ну ёлки-палки, ну кто ж будет такой глупый, чтобы реально делать рекурсивный запрос каждый раз? Собрал один раз структуру в хэш (массив), сериализовал (если надо), сунул в кеш, да перестраиваешь время от времени, когда структура в базе изменяется. При чем не обязательно перестраивать всю структуру целиком, достаточно просто участками, т.к. перестраивать довольно часто надо отнюдь не всё, только определенные ветки.
Даже с учетом ресурсоёмкости процесса перестраивания кеша (что происходит, наверное, не часто) всё это всёравно выглядит лучше, чем materialized path, да и ведет себя не так «забавно» как NS.
Как-то так.
Даже с учетом ресурсоёмкости процесса перестраивания кеша (что происходит, наверное, не часто) всё это всёравно выглядит лучше, чем materialized path, да и ведет себя не так «забавно» как NS.
Как-то так.
Вот что значит использовать для отображения дерева таблицы.
В Cache всё было бы значительно проще:
пусть данные хранятся в глобале ^Tree
Распечатаем глобал и посмотри что внутри:
zw ^Tree
^Tree(«Россия»)=1
^Tree(«Россия»,«Воронеж»)=2
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"")=3
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Главный офис»)=6
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 1»)=7
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»)=8
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»,«Сервер 1»)=9
^Tree(«Россия»,«Лиски»)=5
^Tree(«Россия»,«Лиски»,«ЛискиПресс»)=10
^Tree(«Россия»,«Москва»)=4
Уже это дерево легко преобразовать в xml и отобразить в интерфейсе.
Предположим что этого не достаточно и нам необходимо самим рекурсивно оббегать структуру — будем использовать низкоуровневую функцию $query ($q)
результатом выполнения комманды:
s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) w l,! }
будет:
^Tree(«Россия»)
^Tree(«Россия»,«Воронеж»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"")
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Главный офис»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 1»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»,«Сервер 1»)
^Tree(«Россия»,«Лиски»)
^Tree(«Россия»,«Лиски»,«ЛискиПресс»)
^Tree(«Россия»,«Москва»)
Добавим отступы (пусть никого не пугает вложенный цикл
f i=1:1:len {w " "} ) и идентефикаторы выполним комманду:
s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) f i=1:1:len {w " "} w "(",$g(@l),") ",$qs(l,len),! }
получим:
Всё. Никаких хитростей никаких наворотов стандартные низкоуровневые функции. Стандартное дерево, в котором и хранятся все данные. Даже индексы не задействованы.
В Cache всё было бы значительно проще:
пусть данные хранятся в глобале ^Tree
Распечатаем глобал и посмотри что внутри:
zw ^Tree
^Tree(«Россия»)=1
^Tree(«Россия»,«Воронеж»)=2
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"")=3
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Главный офис»)=6
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 1»)=7
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»)=8
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»,«Сервер 1»)=9
^Tree(«Россия»,«Лиски»)=5
^Tree(«Россия»,«Лиски»,«ЛискиПресс»)=10
^Tree(«Россия»,«Москва»)=4
Уже это дерево легко преобразовать в xml и отобразить в интерфейсе.
Предположим что этого не достаточно и нам необходимо самим рекурсивно оббегать структуру — будем использовать низкоуровневую функцию $query ($q)
результатом выполнения комманды:
s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) w l,! }
будет:
^Tree(«Россия»)
^Tree(«Россия»,«Воронеж»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"")
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Главный офис»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 1»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»)
^Tree(«Россия»,«Воронеж»,«ООО „“Рога и копыта»"",«Офис 2»,«Сервер 1»)
^Tree(«Россия»,«Лиски»)
^Tree(«Россия»,«Лиски»,«ЛискиПресс»)
^Tree(«Россия»,«Москва»)
Добавим отступы (пусть никого не пугает вложенный цикл
f i=1:1:len {w " "} ) и идентефикаторы выполним комманду:
s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) f i=1:1:len {w " "} w "(",$g(@l),") ",$qs(l,len),! }
получим:
(1) Россия
(2) Воронеж
(3) ООО "Рога и копыта"
(6) Главный офис
(7) Офис 1
(8) Офис 2
(9) Сервер 1
(5) Лиски
(10) ЛискиПресс
(4) Москва
Всё. Никаких хитростей никаких наворотов стандартные низкоуровневые функции. Стандартное дерево, в котором и хранятся все данные. Даже индексы не задействованы.
про скорость обработки таких деревьев я скромно умолчу — время рекурсивной обработки зависит от размера дерева логарифмически. То есть вывод по скорости дерева с миллионом узлов аналогичен select * From table (предположим что имеем там миллион записей). Насчёт сортировки тоже заморачиваться не стоит.
И вообще преобразовать табличные данные в деревянные — легко, обратная процедура не всегда возможна и очень ресурсоёмка (имеется ввиду на уровне БД а не интрефейса).
И вообще преобразовать табличные данные в деревянные — легко, обратная процедура не всегда возможна и очень ресурсоёмка (имеется ввиду на уровне БД а не интрефейса).
Строчка запроса взрывает мне мозг, уж больно синтаксис непривычный. Но выглядит очень впечатляюще. В Oracle, как ни крути, деревья всего лишь дополнительная фича, а не главная составляющая.
тогда распишу сокращения понятнее будет
сокращённый вариант
set l="^Tree" //устанавливаем значение переменной
for { //цикл
set l=$query(@l) //берём следующий по очереди элемент дерева (алгоритм обхода функции $query сверху вниз затем справа налево)
quit:l="" //выходим из цикла когда всё обошли
set len=$querylength(l) //определяем глубину вложенности (вниз) текущего узла
for i=1:1:len {write " "} //печатаем отступы
write "(",$get(@l),") ",$querysubscript(l,len),! //печатем в скобках значение узла + его имя
}
сокращённый вариант
s l="^Tree" f { s l=$q(@l) q:l="" s len=$ql(l) f i=1:1:len {w " "} w "(",$g(@l),")",$qs(l,len),! }
Спасибо Вам большое за познавательную статью! Думаю, что многим из Хабрасообщества эта статья будет реально полезна. Также понравилась форма преподнесения: просто о сложном, подробно, интересно. Говорю, как человек, только изучающий язык запросов.
возможно уже кто-то комментировал…
пример запроса с использованием WITH — «зациклен»
вероятно, подразумевалось вот так:
пример запроса с использованием WITH — «зациклен»
вероятно, подразумевалось вот так:
WITH RECURSIVE
Rec (id, pid, title)
AS (
SELECT id, pid, title FROM test_table
UNION ALL
SELECT test_table.id, test_table.pid, test_table.title
FROM Rec, test_table
WHERE Rec.id = test_table.pid
)
SELECT * FROM Rec
WHERE pid is null;
Я не эксперт в MS SQL, ошибка возможна. Но я в упор не вижу чем различается ваш запрос от приведенного в статье.
p.s. Приятно, что материал пользуется спросом и комментируется спустя 7 лет после публикации :-)
p.s. Приятно, что материал пользуется спросом и комментируется спустя 7 лет после публикации :-)
выбор полей в рекурсивной части CTE должен быть из таблицы, а не из CTE, иначе «зацикленность».
извиняюсь: в прошлом комментарии забыл перенести еще условие выборки корневого уровня в CTE, иначе запрос только корневую строчку вернет.
плюс выражение recursive в ms sql, да и в oracle лишнее.
в общем, как-то так:
статья обрела здесь некую фундаментальность за эти 7 лет в вопросах рекурсии средствами SQL.
спасибо )
извиняюсь: в прошлом комментарии забыл перенести еще условие выборки корневого уровня в CTE, иначе запрос только корневую строчку вернет.
плюс выражение recursive в ms sql, да и в oracle лишнее.
в общем, как-то так:
WITH
Rec (id, pid, title)
AS (
-- корневая часть
SELECT id, pid, title FROM test_table
WHERE pid is null
UNION ALL
-- рекурсивная часть
SELECT test_table.id, test_table.pid, test_table.title
FROM Rec, test_table
WHERE Rec.id = test_table.pid
)
SELECT * FROM Rec;
статья обрела здесь некую фундаментальность за эти 7 лет в вопросах рекурсии средствами SQL.
спасибо )
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Иерархические (рекурсивные) запросы