Хранение составных шаблонов (иерархических данных) в базе данных

Question

Что такое «лучшие практики» для сохранения составных шаблонов в реляционной базе данных?

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

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

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

Answer 1

Хотя поиск всех потомков подряд с помощью MPTT является быстрым, поиск всех детей может быть медленным. Однако вы сможете исправить это, добавив в свою таблицу поле parent_id, в котором (да, с избыточностью) записывается родительский элемент строки. Тогда поиск становится:

SELECT *
FROM tbl
WHERE parent_id = z

Да, parent_id содержит избыточную информацию, потенциально денормализующую вашу таблицу - но поскольку любая вставка / обновление / удаление уже требует глобальных изменений, поддержание parent_id в актуальном состоянии не так уж и дорого. В качестве альтернативы вы можете использовать поле level, которое записывает вертикальный уровень строки, хотя на самом деле more может измениться при определенных типах преобразований (например, при перемещении поддерева в другую точку дерева). ).

Простое старое представление «ссылка на родителя» (т. Е. Просто parent_id и отсутствие left_pos или right_pos), конечно, быстрее для рабочих нагрузок со вставкой / обновлением, но единственные запросы, на которые он может ответить эффективно «Найти родителя X» и «Найти детей Х». Большинство рабочих нагрузок включает в себя гораздо больше чтения, чем записи, поэтому обычно MPTT быстрее в целом - но, возможно, в вашем случае вам следует рассмотреть возможность перехода («назад») к ссылке «родитель»?

Answer 2

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