Управление иерархиями в SQL: MPTT / вложенные множества против списков смежности против путей хранения

Question

Какое-то время я боролся с тем, как лучше всего обращаться с иерархиями в SQL.Разочарованный ограниченностью списков смежности и сложностью MPTT / вложенных множеств, я начал думать о простом хранении ключевых путей вместо этого в виде простой строки node_key/node_key/....Я решил собрать все плюсы и минусы трех методов:

Количество вызовов, необходимых для создания / удаления / перемещения узла:

• Смежность = 1
• MPTT = 3
• Path = 1 (Заменить старый путь узла новым путем ко всем узлам, содержащим этот путь)

Количество вызовов, необходимых для получения дерева:

• Смежность = [количество подуровней]
• MPTT = 1
• Path = 1

Количество вызовов, необходимых для получения пути кузел / происхождение:

• Смежность = [количество суперуровней]
• MPTT = 1
• Path = 0

Количество вызовов, необходимое для получения количества подузлов:

• Смежность = [количество подуровней]
• MPTT = 0 (может быть вычислено из правого / левого значений)
• Path = 1

Количество вызовов, необходимых для получения глубины узла:

• Смежность = [количество суперуровней]
• MPTT= 1
• Путь = 0

Обязательные поля БД:

• Смежность = 1 (родитель)
• MPTT = 3 (родитель, справа, слева)
• Path =1 (путь)

Заключение

Техника хранимого пути использует те же или меньшие вызовы, чем другие методики, в каждом случае использования, кроме одного.Благодаря такому анализу хранение путей становится явным победителем.Не говоря уже о том, что это намного проще в реализации, удобочитаемо и т. Д.

Таким образом, вопрос в том, не должны ли хранимые пути считаться более сильной техникой, чем MPTT?Почему хранимые пути не являются более распространенным методом, и почему бы вам не использовать их поверх MPTT в данном случае?

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

ОБНОВЛЕНИЕ:

Вот как минимум две вещи, которые MPTT может сделать из коробки, которые хранятся в памяти.Путь решения не будет:

1. Позволяет вычислять количество подузлов для каждого узла без каких-либо дополнительных запросов (упомянуто выше).
2. Наложение порядка для узлов на данном уровне.Другие решения неупорядочены.

Answer 1

Вы могли бы также рассмотреть дизайн таблицы закрытия, который я описал в своем ответе на Какой самый эффективный / элегантный способ разбить плоский стол на дерево?

Вызовы, необходимые для создания/ удалить / переместить узел:

• Закрытие = 1

Вызовы, необходимые для получения дерева:

• Закрытие = 1

Вызовы, необходимые для получения пути к узлу / происхождению:

• Closure = 1

Вызовы, необходимые для получения количества подузлов:

• Закрытие = 1

Вызовы, необходимые для получения глубины узла:

• Закрытие = 1

Обязательные поля БД:

• Смежность = еще 1 поле / строка
• Путь = еще 1 поле / строка
• MPTT = еще 2 или 3 поля / строки
• Закрытие = 2 или 3 поля в дополнительной таблице.Эта таблица содержит O (n ^ 2) строк наихудший случай , но в большинстве практических случаев она намного меньше, чем в этом случае.

Существует несколько других соображений:

Поддерживает неограниченную глубину:

• Смежность = да
• MPTT = да
• Путь = нет
• Закрытие = да

Поддерживает ссылочную целостность:

• Смежность = да
• MPTT = нет
• Путь = нет
• Закрытие = да

В своей презентации я также рассмотрю таблицу замыканий Модели для иерархических данных с использованием SQL и PHP и мою книгу Антипаттерны SQL: предотвращение ловушек программирования баз данных .

Answer 2

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

Сокращая валидность метода до «количества вызовов», вы фактически игнорируете все проблемы, которые пытаются понять хорошо структурированные структуры данных и алгоритмы; то есть самое быстрое выполнение и нехватка памяти и ресурсов.

«Количество вызовов» к серверу SQL может показаться хорошим показателем для использования («выгляди без кода»), но если в результате получается программа, которая никогда не завершается, работает медленно или занимает много места , на самом деле это бесполезная метрика.

Сохраняя путь для каждого узла, вы не создаете древовидную структуру данных. Вместо этого вы создаете список. Любая операция, оптимизированная для дерева, теряется.

Это может быть трудно увидеть с небольшими наборами дат (а во многих случаях с небольшими деревьями список лучше), попробуйте несколько примеров для наборов данных размером 500, 1000, 10k - вы быстро поймете, почему нужно хранить все путь не очень хорошая идея.