Форум dkLab и Denwer

[Phoebus]

Третьего дня возник вопрос с правильным хранением древовидных структур в СУБД типа Mysql. На форуме через поиск найти ничего не смог, поэтому и создал новую тему.
Дело в том, что многие методы имеют очень большой недостаток - медлительность при проходе через все ветви (ну, вам ли объяснять!).
Вот, к примеру, самый примитивный метод - указывать в каждой записи идентификатор parent-записи, типа такого:
||id||parentid||text
||1||0||sadsa
||2||0||sfafa
||3||1||sadsada
||4||2||sdadadfasf
||5||3||sdadasd
где parentid==0 указывает на то, что запись является корневой. Но рекурсия в данном случае при большом количестве записей - дело страшное, да...

Или вот недавно один человек предложил вообще безбашенный метод - делать только два вида записей: корневой и children, а в children класть сериализованный массив со всеми нужными записями (метод тут привел лишь для примера, не подумайте, догадываюсь, что может нехило глюкануть)...

В связи с этим возник вопрос: ведь есть же и другие, более эффективные методы (типа такого, правда, у него проблемы при добавлении новых записей.. хотя...) Так вот, может кто-нибудь знает хорошие эффективные методы хранения деревьев в бд и не против ими поделиться?
(особенно очень хочется услышать, что скажет по этому поводу Дмитрий Кóтеров...)

Заранее Спасибо.

[Rumata]

вообще-то это уже обсуждалось здесь и где-то на http://xpoint.ru
еще рекоммендую погуглить/пояндексить на тему Nested Sets

приведенная Вами ссылка имеет переводы на русском, но мне кажется и оригинал и переводы грешат ошибками в запросах SQL

[Дмитрий Кóтеров]

Сходите, пожалуйста, в Поиск по запросу «Nested Sets». Спасибо! ;-)

[Graymur]

http://www.livejournal.com/~demiurg/53125.html?mode=reply

[Константин Жинько [tIT]]

Phoebus wrote:

самый примитивный метод - указывать в каждой записи идентификатор parent-записи, типа такого

Я все время так и делал, и скорость меня устраивала даже

Phoebus wrote:

при большом количестве записей

Способ действительно самый примитивный... Например для организации каталога магазина http://arbois.ru я делал именно так и прогонял с достаточно реальным количеством записей... Всегда думала меньше секунды, как на виндах, так и на фре...
Сейчас там структура каталога немного изменилась, а следовательно и логика алгоритма (из-за другого представления), но принцип дерева тот же.
[offtop]
Мда... только что туда заглянул -- каталог, мягко говоря, на стадии тестирования...%
И зачем заказывали, раз не пользуются?%
С жиру, видимо, бесятся...
[/offtop]
А Вам для каких целей нужно дерево? Для какого приложения?

[Юрий Насретдинов]

Phoebus:
Из личного опыта могу все-таки посоветовать id-parentid , все эти Nested Sets это все чепуха, в большинстве случаев оптимальным решением будет именно такой способ. Сам на это напарывался уже.

[Phoebus]

tIT wrote:

А Вам для каких целей нужно дерево? Для какого приложения?

CMS
Конкретнее:
а) друвовидная структуризация документов (т.е. каталог/подкаталог/документ, вложенность любого вида)
б) древовидные комментарии (как в lj)

[Юрий Насретдинов]

Phoebus
Для а) однозначно id-parentid, а для б) ИМХО больше подойдет именно Nested Sets.

[Евгений Галашин]

yUAC
а) почему?

[Юрий Насретдинов]

Евгений Галашин
Это намного более гибкая структура, и с ней намного проще работать. И тут не критично немного большее количество запросов

[Phoebus]

yUAC wrote:

yUAC

Странно.... я как-раз таки думал совсем по другому, т.е. nested sets использовать для хранения документов, потому что их добавлением занимается лишь ограниченный круг людей => небольшие тормоза при INSERT не будут столь существенны. В отличие от комментариев, которые добавляются намного чаще, вложенность будет использоваться чаще (возможно) и поэтому тут INSERT (который очень быстр в методе id-parentid) не менее важен чем SELECT... впрочем, в последнем случае действительно при выборке могут возникнуть тормоза т.к. выводить мне придется все деревья целиком, от корня до самого нижнего child-a...

yUAC wrote:

И тут не критично немного большее количество запросов

Ну, вообще да, что-то я об этом не подумал... Просто мысли были забиты статейкой (замечательная вещь! )

оффтопом:

Дмитрий Кóтеров wrote:

Сходите, пожалуйста, в Поиск по запросу «Nested Sets». Спасибо!

Я, естесвенно, в поиске искал все что мог придумать касаясь "иерархический" и "древовидный", а вот "nested sets" абсолютно из памяти вылетело ;)

[Юрий Насретдинов]

Phoebus wrote:

которые добавляются намного чаще, вложенность будет использоваться чаще (возможно) и поэтому тут INSERT (который очень быстр в методе id-parentid) не менее важен чем SELECT

Дело в том, что INSERT начинает проявлять свои «тормоза» на Nested Sets только при количестве записей начиная от 100. В комментариях конечно такого быть не может, а если даже и может, то SELECT в данном случае ИМХО намного более важен - просмотров комментариев по идее должно быть намного больше, чем добавлений комментариев (если база грамотно спроектирована, конечно).

Phoebus wrote:

Просто мысли были забиты статейкой

У меня в свое время тоже. Потом пришлось от этой мысли отказаться - слишком сложно (хотя это не самая большая проблема), а главное - не нужно!

Phoebus wrote:

nested sets использовать для хранения документов, потому что их добавлением занимается лишь ограниченный круг людей

Ну и что! Вам же не нужно для хранения документов сразу выводить все дерево! Nested Sets как раз нужен тогда, когда необходимо хранить большое количество документов в строгой иерархии, и при этом каждый раз по полдерева доставать. А если это делается для сайта, то тут несколько конкретных запросов по полю parentid будут работать быстрее, чем один запрос на выборку всей ветки документов, и последующего разбора этой ветки. Если не поняли, то могу привести пример (писать лень, если действительно не поняли, то напишу)

[Phoebus]

yUAC wrote:

последующего разбора этой ветки. Если не поняли, то могу привести пример

Нет, все ясно, спасибо ;)
Единственное, хочу спросить: ощутимы ли будут тормоза если используя метод Nested Sets хранить данные о комментариях (т.е. где текста мало чаще всего) в той же таблице что и древовидные отношения dbtree? Т.е. добавить к столбцам id|lft|rgt еще и username|commentstext|email, а не разделять их на две таблицы со связью по id - сильно ли упадет скорость прохода по дереву?

[Юрий Насретдинов]

Phoebus wrote:

сильно ли упадет скорость прохода по дереву

Неа. Я так делал - скорость от этого не зависит, а если и зависит, то несильно.

[Vladimir Sergeev]

У меня стояла задача в дереве для объекта получить с максимальной скоростью всех его родителей и обработать их.
Собственно, Nestsd Sets и иже с ним сразу отпали, я стал использовать `id`-`parent_id`-`level`.
Однако, никакой рекурсии использовать я тоже не стал - все манипуляции по извлечению родителей
уместилиь в два SQL-запроса: один получает по ID объекта его level, а другой level раз связывает
таблицу саму с собой, выдавая ID родителей.
Все работает довольно быстро.
У меня система контрля доступа, дерево юзеров(забил 100 000, уровень вложения - до 25), дерево объектов(те же числа) и таблица с записями привелегий(забил 150 000 записей). Вся работа: связывание таблиц сначала самих с собой, потом друг с другом, в том числе и обработка полученной из БД инфы, занимает 0,05 с. В этом контексте на все про все использовались уже 4 запроса.
Что интересно, время обработки практически одинаково и для 5 объектов, и для 100 000 - слава MySQL!:)
Кстати, при таком подходе в MySQL3 масимальный уровень вложения не может превышать 31.
(действует ограничение на число связываемых таблиц)

[Юрий Насретдинов]

Bred Vilchec
А можно примерчик запроса?

[Дмитрий Кóтеров]

Видимо, что-то типа

Code (SQL):	скопировать код в буфер обмена
SELECT t1.*, t2.*, ... FROM   tree t1   RIGHT JOIN tree t2 ON t2.parent=t1.id   RIGHT JOIN tree t3 ON t3.parent=t2.id   ... WHERE t1.id=?

Ну или что-то типа того. Причем число JOIN-ов совпадает с глубиной дерева. Можно просто все 31 уровня сразу забить - тогда там автоматом с некоторого момента пойдут NULL-ы, и выберутся потомки до максимум 32-го уровня (я, правда, не уверен - может, нужно запрос чуть-чуть подкорректировать). В принципе, тоже вариант, и работать должно довольно быстро (с чего б ему долго работать, если он выбирает ровно столько записей, сколько нужно).

[Юрий Насретдинов]

Дмитрий Кóтеров
Очень интересное решение ;)

[Дмитрий Кóтеров]

Осталось только его на практике как-нибудь проверить. Но - пока не подвернулось задачи.
В принципе, 32 - это очень значительный уровень для большинства деревьев. Я так даже навскидку и не могу представить задачи, где бы его оказалось недостаточно.

[Константин Жинько [tIT]]

Bred Vilchec wrote:

Кстати, при таком подходе в MySQL3 масимальный уровень вложения не может превышать 31.

Поэтому в больших виртальных магазинах лучше все-таки рекурсию

[Юрий Насретдинов]

Да все равно выигрыш мизерный... Особенно если нет затрат на передачу данных по сети - можно делать сколько угодно запросов, самое главное - чтобы сама нагрузка на базу данных была не очень высокая

[Константин Жинько [tIT]]

резонно

[Дмитрий Кóтеров]

yUAC, не совсем ты прав, как мне кажется. Тут штука в том, что может потребоваться, к примеру, не выбрать все, а подсчитать число чего-то. Например, вычислить число товаров в разделах, имя предка (произвольного!) которых начинается на "А".

[Юрий Насретдинов]

Дмитрий Кóтеров
Ух закрутил... В таком случае бедной СУБД придется перебирать ВСЮ базу, и тут уже не имеет особого значения, как составлен запрос - с такими «финтами ушами», или без.

[Дмитрий Кóтеров]

Ты забыл про индексы. Совсем и не факт, что ей придется перебирать всю базу.

[Vladimir Sergeev]

Во-первых, прошу не забывать, что ограничение в 31 уровень справедливо только для
MySQL 3, в четвертой версии число связываемых таблиц увеличено.
Поэтому можно смело использовать этот подход, тем более если магазин такой крутой, то проблема отсталого хостинга для него не актуальна.
Позже поковыряюсь в документации и найду точные числа.

Вот структура таблицы:

Code (SQL):	скопировать код в буфер обмена
CREATE TABLE `users_tree` (   `id` int(11) UNSIGNED NOT NULL AUTO_INCREMENT,   `parent_id` int(11) UNSIGNED NOT NULL DEFAULT '0',   `level` smallint(6) UNSIGNED NOT NULL DEFAULT '0',   PRIMARY KEY  (`id`),   KEY `parent_id` (`parent_id`,`level`) ) ENGINE=MyISAM DEFAULT CHARSET=cp1251;

Сразу скажу, я далеко не спец в проектировании и оптимизации БД, поэтому уверен,
что есть и более рациональные способы расставить индексы в таблице.
Для каждого юзера в отдельной таблице хранится его имя(оно используется крайне редко).

А вот и реальный запрос, собираемый скриптом по кусочкам:

Code (SQL):

скопировать код в буфер обмена

SELECT @user0 := tbl0.id, @user1 := tbl1.id, @user2 := tbl2.id, @user3 := tbl3.id, @user4 := tbl4.id, @user5 := tbl5.id FROM users_tree AS tbl0, users_tree AS tbl1, users_tree AS tbl2, users_tree AS tbl3, users_tree AS tbl4, users_tree AS tbl5 WHERE tbl0.id = '102' AND tbl1.id = tbl0.parent_id AND tbl2.id = tbl1.parent_id AND tbl3.id = tbl2.parent_id AND tbl4.id = tbl3.parent_id AND tbl5.id = tbl4.parent_id AND tbl5.parent_id =0

Результат этого запроса скрипт даже не получает, ведь следующий запрос использует
установленые переменные.

Кстати, я в ближайшее время допишу класс к контроллеру доступа и скорее всего выложу его в "Готовые решения", приходите посмотреть:)

tIT wrote:

Поэтому в больших виртальных магазинах лучше все-таки рекурсию

Если я не ошибаюсь, в рекурсии число запросов будет равно уровню вложения объекта?
Не слишком ли "жирно" получается, ведь как мы знаем, основное время уходит на получение результата запроса?
Тем более, сама рекурсия достаточно жадна до ресурсов.

[Vladimir Sergeev]

Сегодня все утро насиловал БД:), хотел посмотреть, насколько размер и вложенность
данных влияют на скорость работы. Вбил в БД еще по 1 000 000(!) случайных пользователей,
объектов и привелегий, общий размер базы превысил 220 Мб.
Самый "младший" в иерархии пользователь имел уровень вложенности 30,
а самый "младший" объект - 32.

Выяснение отношения пользователя 863786 к объекту 934355 заняло всего 0.972 секунды!
Этот результат оказался средним среди аналогичных тестов на больших вложениях.
А сколько бы делал это рекурсивный скрипт?
При том, надо заметить, у меня далеко не мощная машина - Celeron 2000 и 256 Mb RAM.

После этого я провел еще один маленький тест - циклом 1000 раз выяснял, имеет ли случайный пользователь
права на случайный объект. Цикл занял чуть менее 200 секунд, это значит, что на одну итерацию
приходилось по 0,2 секунды.

Думаю, эти результы(как увелечительное стекло) являются весомым аргументом в пользу
возложения "грязной" работы на БД.

PS если кому-либо интересно, могу поделиться тестирующими скриптами, однако одно маленькое "но":
заполнение БД занимает часа два-три, если не больше.:)

[Евгений Галашин]

Bred Vilchec: +2

[Константин Жинько [tIT]]

Bred Vilchec wrote:

Если я не ошибаюсь, в рекурсии число запросов будет равно уровню вложения объекта? Не слишком ли "жирно" получается, ведь как мы знаем, основное время уходит на получение результата запроса? Тем более, сама рекурсия достаточно жадна до ресурсов.

Так и есть (-;
Но у меня почему-то все быстро работало при условии, что СУБД на той же машине, что и Apache.

[Константин Жинько [tIT]]

Bred Vilchec wrote:

После этого я провел еще один маленький тест - циклом 1000 раз выяснял, имеет ли случайный пользователь права на случайный объект. Цикл занял чуть менее 200 секунд, это значит, что на одну итерацию приходилось по 0,2 секунды.

Великолепно!
+1

[Vladimir Sergeev]

Могу предпринять только симметричные ответные меры:
Евгений Галашин+2
tIT+1
:)

Спасибо.

PS карму надо повышать не мне, а разработчикам MySQL.

[Дмитрий Кóтеров]

Bred Vilchec wrote:

`level` smallint(6) UNSIGNED NOT NULL DEFAULT '0',

Не пойму только, зачем Вам level. По идее, его всегда можно вычислить тем же SQL-запросом (см. конструкцию MySQL IF()).

И - еще один момент. Как Вы обходитесь без LEFT JOIN (или RIGHT JOIN)? Тот запрос, который Вы выше привели, по идее, работать не должен - ведь, например, в tbl5 не найдется соответствующего элемента (если максимальная вложенность в базе - 4), и будет возвращен пустой результат.

[Юрий Насретдинов]

Дмитрий Кóтеров
А это просто другой вид JOIN`а

[Дмитрий Кóтеров]

yUAC, спасибо. А и Б - это просто разные буквы алфавита. ;-)

[Vladimir Sergeev]

Дмитрий Кóтеров wrote:

Тот запрос, который Вы выше привели, по идее, работать не должен - ведь, например, в tbl5 не найдется соответствующего элемента (если максимальная вложенность в базе - 4), и будет возвращен пустой результат.

Собственно вот за этим-то level и нужен.
Это, конечо, некоторая избыточность хранимых данных, но по сравнению с Nested Sets и
dbtree не такая уж и большая.

[Дмитрий Кóтеров]

Еще раз: очень вероятно, что при использовании LEFT JOIN-а никакой level не нужен.
Эх, сейчас попробую все-таки написать тестовый скрипт. Ждите.

[Vladimir Sergeev]

Оки, теперь я понял Вашу идею.
Жду с нетерпением, особенно хотелось бы увидеть таинственный запрос с if'ами.
В принципе, если это сработает, это будет здорово, однако
в моем приложении level все же необходим.

Как я уже говорил, у меня 4 запроса:
первый получает level'ы
второй и третий связывают сами с собой таблицы юзеров и объектов
а вот четвертый, основной, связывает три таблицы и фактически выдает мне результат,
allow или denied.
Вся соль в том, что в ходе этого запроса мне необходимо "пробежать"
всех родителей пользоватлей (они получены 2-м запросом), начиная с корневого,
а также всех родителей объектов(они получены в 3-ем запросе), отсортировав их именно
по level.
Есть конечно кривой обходной путь - сортировать по id, мол у кого id меньше, тот и младше.
Но мне он тоже не подойдет, поскольку возможен перенос объекта или пользователя в другую ветку,
при этом, естественно, все такие "тонкие" связи нарушатся.

[Дмитрий Кóтеров]

Собственно, все получилось. Вот скрипт:

http://dbtree.dklab.ru/search.php

Таблица очень проста: (id, parent, text). Индексы по всем полям. В качестве эксперимента я туда вбил содержимое своего виртуального диска в Денвере (около 84694 файлов и директорий). Имена файлов и директорий пошли в поле text.

Запрос к скрипту задается в формате:

/имя/имя/имя/...
(поиск относительно корня)

или

имя/имя/...
(поиск относительно произвольной ветки!)

где имя - это любая LIKE-маска, которая будет подставлена на соответствующее место в пути. Например:
- запрос "/" вернет все элементы;
- запрос "/home" - только те, что в /home
- запрос "www" - вернет все содержимое всех директорий www
- и т.д.

Глубина выборки показывает, на сколько элементов вглубь нужно копать.
Отображаются не все результаты поиска, а только первые N (см. соответствующее поле).
Наконец, флажок "Подсчитывать число записей" заставляет перед основным запросом выполнить запрос с COUNT(), который подсчитает общее число записей. Это довольно долго, если записей много.

Обратите внимание, что сами директории НЕ отображаются. Например, в результате http://dbtree.dklab.ru/search.php?mask=%2Fhome&depth=3&num=100&count=on - нет элемента "/" и "/home". Однако, если директория пуста, то тогда она отобразится, например: http://dbtree.dklab.ru/search.php?mask=%2Ftmp%2F%21sendmail&depth=3&num=100&count=on. таким образом, действуют правила: отображаются только листовые элементы!

К счастью, по листовым вершинам можно легко восстановить всех родителей чисто на PHP (все имена и ID-шники для этого в результатах имеются). Вообще, чисто на MySQL сделать выборку не только листовых вершин, но вообще всех, похоже, нельзя.

Внизу, под результатами, показывается сам SQL-запрос.

Вывод: на мой взгляд, работает все очень хорошо. Единственное место, где возможны тормоза, - это подсчет числа потомков некоторого элемента, если таких потомков много, и разветвленность дерева большая. В этом, пожалуй, выигрывают Nested Sets.

[Дмитрий Кóтеров]

Да, еще одно. Если "глубина копания" превышает фактическую глубину дерева, на быстродействие это отрицательным образом не сказывается. Иными словами, если у вас есть дерево с максимальной вложенностью 10, то можно делать запросы с вложенностью 30 - тормозить по сравнению с вложенностью 10 не будет.

[Ant]

Дмитрий Кóтеров wrote:

http://dbtree.dklab/search.php

«.ru» не забудьте добавить, кому надо попасть на страницу.