3

Мне нужно хранить дерево в базе данных так, чтобы операции чтения его ветки вместе со всеми вложенными в неё ветками выполнялись максимально быстро. Время выполнения остальных операций (вставка, удаление и т.д.) — не принципиально. Главное: чтобы они были реализуемы. Подскажите, как это лучше реализовать?

Я так понимаю в такой ситуации наилучших результатов можно добиться используя Closure Table или Nested Sets. Как думаете, что лучше? Может, посоветуете что-то другое?

СУБД: MySQL, но желательно использовать только стандартный SQL синтаксис, без наворотов, не поддерживаемых, в других СУБД.

5
  • Есть базы, которые умеют выполнять запросы recursive cte. Всё дерево вытаскивается за один запрос Из бесплатных - это postgres. Ну и все широко известные коммерческие это умеют. Так же можно извлечь всё дерево, постепенно извлекая дочерние ноды. Или хранимую процедуру сделать для извлечения дерева. Может зря панику наводите про быстродействие. Что такие огромные высокие и ветвистые деревья?
    – Sergey
    16 апр 2016 в 10:13
  • А плохого ничего нет. Пока сами не почувствуете, что плохо плоучается, никто и не убедит.
    – Sergey
    16 апр 2016 в 10:20
  • База данных MySQL. Желательное не использовать наворотов не поддерживаемых в других базах данных. Переформулировал вопрос. 16 апр 2016 в 10:37
  • Скорее MySQL является наворотом (точнее недонаворотом), не поддерживающим стандарты SQL даже прошлого века. Так что перевернули всё с ног на голову:)
    – Sergey
    16 апр 2016 в 11:16
  • Вообще, существует несколько способов реализации иерархий в БД. Например, в этой статье описаны 4. 20 апр 2016 в 17:35

1 ответ 1

4

Если у вас большинство операций связаны с операцией чтения, то лучше воспользоваться шаблоном проектирования Вложенные Множества (Nested Set). В этом шаблоне вы заводите в каждом узле два поля: левая и правая граница (lft и rth). Причем при вставке и обновлении так пересчитываете границы узлов дерева, чтобы отрезок lft:rth потомка в дереве, всегда входил в корневой узел.

post_id  |  lft  |  rth
1        |  1    |  14
2        |  2    |  11
3        |  3    |  6
6        |  4    |  5
4        |  7    |  8
7        |  9    |  10
5        |  12   |  13

1     1 <-------------------------------------------> 14
2       2 <----------------------------> 11
3         3 <-----> 6
6           4 <-> 5
4                     7 <-> 8
7                              9 <-> 10
5                                           12 <-> 13

В этом случае чтобы извлечь все записи дерева или какого-то узла дерева, достаточно выполнить однотабличный запрос

SELECT * FROM tbl WHERE lft >= 1 AND rth <= 14

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

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.