Посадим Дерево?
В один прекрасный момент своей солнечной жизни практически каждый разработчик веб-приложений сталкивается с проблемой хранения иерархичных данных в реляционной СУБД. Конечно, надо сразу признать, что умные дяди и, наверное, даже тёти, придумали приятного монстрика по имени «XML», который, легко решает любую проблему хранения иерархии, но, увы, не решает проблемы хранения пары миллионов записей. А посему появляется на свет относительно интересная проблемка – а как, собственно, хранить в «плоской» базе данных «древовидные» структуры?
В своё время и я поломал над этой проблемой голову, вспомнил первый курс факультета информатики, тогда до меня не совсем допирало, зачем, собственно, там быть асами «конкретной» математики. Но ничего, прорвался и допёр до «рекурсивного» метода работы с деревьями.
Рекурсивный Метод
Метод сам по себе прост, как 2+2. В таблице наряду с уникальным идентификатором каждой записи в СУБД так же хранится идентификатор родителя этой записи. Навигация и простая работа с деревом производится с помощью рекурсивных функций. Всё это конечно очень приятно и красиво – до поры до времени. С таким подходом можно легко поставить сайт на пару тысяч страниц, но никак не форум на пару десятков тысяч вложенных сообщений. Всё просто, рекурсия сама в себе подразумевает множество запросов к базе данных (по одному на каждый уровень дерева) и банальный форум может ввести в ступор всю системы не на одну секунду. Да ещё и сами рекурсивные функции могут, не смотря на свою элегантность, убить систему.
Ну на нет и суда нет, а посему начал ломать свою измученную голову дальше. Создавать и уничтожать подключения в серому веществу внутри моей черепной коробки, бешено щёлкать мышкой по экрану и в итоге в каком-то старинном учебнике нашёл теорию «траверсации деревьев» (tree traversal). Почитал. Понял. Почитал ещё. Понял ещё. Подумал. Почитал. И полез в сеть искать примеры ;)
Tree Traversal
Сеть большая, а я маленький, да, вот, видимо, удаленький. Всего-то за 5 минут нашёл массу бесполезного материала. Сложилось такое ощущение, что никто толком до конца не понимает как работать с траверсом. И даже статья на, вполне уважаемом сайте sitepoint оказалась неполной и с парой корявостей в представленном коде (автору, кстати, написал доброжелательное письмо с поправками).
Вкратце, траверс — это определённая нумерация данных, с помощью которой можно вычислить принадлежность к дереву отдельно взятой записи. Заново объяснять как работает колесо у меня, собственно, нет желания, а потому просто читайте статью на «sitepoint», там всё достаточно ясно и понятно и даже правильно до тез пор, пока автор не сталкивается с первой сложностью.
У меня сложилось ощущение, что автор не представляет как добавлять данные в любую точку дерева, тем более автор только вскользь упоминает о самой большой диллеме – уничтожении частей дерева, без потери организации данных. Вот тут-то я его и дополню.
Добавление данных
Метод представленный в статье не совсем верен, так как он добавляет в древо не новый «отросток», а отросток на тот же уровень, который передаётся функции в форме указателя на, типа, родителя. Чтобы его исправить достаточно самую малость подправить первый запрос к СУБД и всё-таки вынести подсчёт левого и правого индекса из последнего запроса. Исправленный вариант будет выглядеть примерно так:
UPDATE tree SET rgt=rgt+2 WHERE rgt>=5; UPDATE tree SET lft=lft+2 WHERE lft>5; INSERT INTO tree SET lft=5, rgt=5+1, title='Strawberry';
Всё хорошо, что хорошо кончается, а потому, думаю, стоит разъяснить как удалять данные из дерева без потери организации данных (у автора оригинальной статьи либо времени, либо мозгов не хватило).
Удаление данных
Хороший программист знает, что хорошие программы рисуются на бумаге, а потому взяв простой листок бумаги и дешёвую ручку BIC я быстренько нарисовал простенькое дерево, пронумеровал левые и правые индексы, и начал хаотично чесать затылок и ковыряться в носу. Решение, как всегда, пришло не стучась. И так передо мной стояло две задачи.
Первая — как удалить запись в дереве и все её ветви. Всё до банальности просто, детёныши любой записи будут иметь левый индекс больше своей «мамы», а правый меньше. Соответственно, чтобы удалить всё поддерево включая самого родителя, достаточно выполнить запрос с ограничителем «WHERE rgt <= $currentRight AND lft >= $currentLeft». Детский сад, право.
Вторая задача — как не потерять левые и правые индексы других данных, а ещё лучше, как их привести в полный порядок. Тут всё тоже довольно просто, если дядя Лёша добровольно даст ключ от квартиры, где идеи лежат, а Лёша добрый, потому точно даст ;)
И так, все индексы у всех записей, находящихся правее удалённой записи на дереве надо уменьшить на (разницу индексов удалённой записи + 1). Для чайников просто приведу пример запроса к СУДБ.
UPDATE tree SET rgt = rgt – ($currentRight – $currentLeft + 1) WHERE rgt > $currentRight; UPDATE tree SET lft = lft – ($currentRight – $currentLeft + 1) WHERE lft > $currentLeft;
Вот и вся математика. Ловкость рук, не более. Но не всё так просто, товарищи, увы, не всё так просто. У данного метода работы с данными хоть и есть явный плюс в скорости построения гигантских деревьев (поскольку запрос к базе делается всего один), у него есть и масса маленьких минусов, которые в предыдущем методе работы с данными отсутствуют.
- Попробуйте вытащить родителя некой записи, не вытаскивая всего дерева.
- Попробуйте вытащить только один, первый, уровень «детей» отходя от какой-либо записи.
Исходя из этих ограничений довольно сложно будет построить, например, выпадающие меню.
Оптимальный Вариант
Как что? Совмещать и властвовать. Что нам, простым смертным, мешает использовать оба подхода одновременно. Использовать первый для навигации по дереву (вверх/вниз) а второй для постройки самого древа и отдачи его клиенту? Правильно, ничего нам не мешает. Просто в нашей таблице помимо левого и правого индексов будем хранить указатель на родителя и всё будет в чистейшем ажуре. Далее просто совмещаем все необходимые функции навигации по древу в одном объекте и все дороги к построению форумов на скорости mach3 для нас открыты.
Дядя Лёша добрый, вы не знали? Так знайте, сам на скорую руку накидал объект, который совсем не хило строит деревья любой сложности, бегает по ним сломя голову и плюётся нужными и желанными данными.
Всякая Всячина
Товарищи, я все равно не советую всё что у вас есть пихать в одно дерево, будьте людьми рассудительными и заводите по отдельному древу на каждую тему в вашем форуме, или на каждую статью на вашем сайте. Поверьте, производительность будет выше!
Клизма
А на этом сайте нет концепта закладок? Очень хотелось бы...
14.11.2004 // 16:39 [ ссылка ]
Ответ от Автора
можно, наверное, с куками сделать
14.11.2004 // 16:44 [ ссылка ]