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

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

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

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

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

  • Adjacency = [количество подуровней]
  • MPTT = 1
  • Путь = 1

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

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

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

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

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

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

Требуемые поля БД:

  • Adjacency = 1 (родительский)
  • MPTT = 3 (родительский, правый, левый)
  • Путь = 1 (путь)

Заключение

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

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

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

UPDATE:

Вот, по крайней мере, 2 вещи, которые MPTT может сделать из коробки, что не будет сохраненного пути:

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

Ответы

Ответ 1

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

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

  • Закрытие = 1

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

  • Закрытие = 1

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

  • Закрытие = 1

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

  • Закрытие = 1

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

  • Закрытие = 1

Требуемые поля БД:

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

Есть еще несколько соображений:

Поддержка неограниченной глубины:

  • Adjacency = yes
  • MPTT = yes
  • Путь = нет
  • Закрытие = да

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

  • Adjacency = yes
  • MPTT = нет
  • Путь = нет
  • Закрытие = да

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

Ответ 2

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

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

"Количество вызовов" на SQL-сервере может показаться хорошей метрикой для использования ( "look ma less code" ), но если результат - это программа, которая никогда не заканчивается, выполняется медленно или занимает много места, это на самом деле бесполезная метрика.

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

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