+7 (495) 229-0436 | shopadmin@itshop.ru | 119334, г. Москва, ул. Бардина, д. 4, корп. 3 |
|
|
Строим Nested Set дерево без рекурсии29.11.2012 15:04
garex
Деревья в базах данных можно хранить тремя основными методами: Adjacency List, Matherialized Path & Nested Set. Когда мы хотим переехать с AL на NS, это можно сделать с помощью рекурсии (если БД расово верная). Но что делать в случае MySQL?
Краткий обзор методов хранения деревьев в БДЕсли кратко, то:
MySQL и рекурсияВ случае MySQL мы имеем рекурсию, но только на уровне хранимых процедур да и то до 255 уровней. Также мы можем задействовать рекурсию в связке язык программирования + БД, но число запросов здесь может быть потрясающим. Лучше делать всё в базе. Погуглив мы узнаём, что любую рекурсивную задачу можно решить без неё родимой [4]. Задавшись подобным вопросом мы можем попробовать и… у нас получится! Ниже мы представляем вашему вниманию функцию rebuild_nested_set_tree, которая заполняет lft и rgt, зная parent_id.
Функция заполнения дерева без рекурсииДля простоты представим, что у нас в табличке только одно дерево и в нём 8 элементов. На вход функция будет получать ничего. Естественно в production-версии мы будем на вход получать некие id вершин деревьев, которые будем учитывать в логике. Ниже мы приведём только тело функции для экономии места, а полный текст и запросы смотрите на SQLFiddle (спасибо тов. grokru за открытие этого сервиса).
Исходник тела функции rebuild_nested_set_tree
Что мы здесь делаем?В общем и целом мы находим крайний левый верхний элемент с заполненными границами и незаполненными детьми, вычисляем длину ряда его детей, обновляем границы элементов, которые справа от нас и затем уже обновляем границы его детей. Всё это делается без рекурсии в бесконечном цикле, пока у нас не кончатся элементы без границ. Визуализировать процесс нам поможет несложная презенташка:
Ссылки по теме |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
О нас |
Интернет-магазин ITShop.ru предлагает широкий спектр услуг информационных технологий и ПО.
На протяжении многих лет интернет-магазин предлагает товары и услуги, ориентированные на бизнес-пользователей и специалистов по информационным технологиям. Хорошие отзывы постоянных клиентов и высокий уровень специалистов позволяет получить наивысший результат при совместной работе. В нашем магазине вы можете приобрести лицензионное ПО выбрав необходимое из широкого спектра и ассортимента по самым доступным ценам. Наши менеджеры любезно помогут определиться с выбором ПО, которое необходимо именно вам. Также мы проводим учебные курсы. Мы приглашаем к сотрудничеству учебные центры, организаторов семинаров и бизнес-тренингов, преподавателей. Сфера сотрудничества - продвижение бизнес-тренингов и курсов обучения по информационным технологиям.
|
119334, г. Москва, ул. Бардина, д. 4, корп. 3 +7 (495) 229-0436 shopadmin@itshop.ru |
|
© ООО "Interface Ltd." Продаем программное обеспечение с 1990 года |