Джанго Древобород, в чем различия между АЛ, НС, МП
Я пытаюсь сделать модель для классификации некоторых объектов.
Я уже пытался использовать django-mptt для простого поиска связанных категорий, и сейчас я ищу различные решения, чтобы найти лучшее.
Однако я не могу выяснить, каковы основные различия между Материализованным путем, Списком смежности и Вложенным множеством. Википедия не дала мне короткого ответа, все, что я знаю, это, вероятно, mptt - Nested Set...
Может кто-нибудь объяснить мне это в нескольких словах?
1 ответ
Это проще объяснить примерами, чем несколькими словами. Рассмотрим пример дерева, в котором хранятся имена:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Материализованный путь означает, что каждый узел хранит свой полный путь в кодировке. Например, вы можете сохранить его индекс, используя точку в качестве разделителя
Name Path
William 1
Jones 1.1
Blake 1.2
Adams 1.2.1
Tyler 1.3
Joseph 2
Miller 2.1
Flint 2.2
Итак, Адамс знает, что его полное имя Вильям Блейк Адамс, потому что он имеет 1.2.1 путь, указывающий на 1 узел на первом уровне - Уильям - к 1.2 узел на уровне 2 - Блейк - и 1.2.1 узел на уровне 3 - Адамс.
Список смежности означает, что дерево хранится путем сохранения ссылки на некоторые смежные узлы. Например, вы можете хранить, кто является родителем, а кто следующий брат.
Name Parent Next
William null Joseph
Jones William Blake
Blake William Tyler
Adams Blake null
Tyler William null
Joseph null null
Miller Joseph Flint
Flint Joseph null
Обратите внимание, что это может быть так же просто, как просто сохранить родительский элемент, если нам не нужно сохранять порядок дочерних узлов. Теперь Адамс может рекурсивно получить всех своих предков до нуля, чтобы найти его полное имя.
Вложенные наборы означают, что вы сохраняете каждый узел с некоторым индексом, обычно левым и правым значением, присваиваемым каждому при обходе дерева в порядке DFS, так что вы знаете, что его потомки находятся в этих значениях. Вот как числа будут назначены в дерево примеров:
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
И это будет храниться как:
Name left right
William 1 10
Jones 2 3
Blake 4 7
Adams 5 6
Tyler 8 9
Joseph 11 16
Miller 12 13
Flint 14 15
Итак, теперь Адамс может найти своих предков, запросив, у кого есть нижнее левое И более высокое правое значение, и отсортировать их по левому значению.
У каждой модели есть свои сильные и слабые стороны. Выбор того, какой из них использовать, действительно зависит от вашего приложения, базы данных, которую вы используете, и какие операции вы будете выполнять чаще всего. Вы можете найти хорошее сравнение здесь.
Сравнение упоминает четвертую модель, которая не очень распространена (я не знаю какой-либо другой реализации, кроме моей собственной) и которую очень сложно объяснить в нескольких словах: Вложенный интервал с помощью матричного кодирования.
Когда вы вставляете новый узел во вложенный набор, вы должны пересчитывать всех, кто опережает его в обходе. Идея, лежащая в основе вложенных интервалов, заключается в том, что между любыми двумя целыми числами существует бесконечное число рациональных чисел, поэтому вы можете сохранить новый узел как часть его предыдущего и следующего узлов. Хранение и запрос дробей может быть проблематичным, и это приводит к методу матричного кодирования, который преобразует эти дроби в матрицу 2x2, и большинство операций может выполняться некоторой алгеброй матриц, которая на первый взгляд неочевидна, но может быть очень эффективной.
Treebeard имеет очень простые реализации каждого из Материализованного Пути, Вложенных Наборов и Списков Смежности, без избыточности. На самом деле django-mptt использует смесь вложенных наборов и списков смежности, поскольку он также сохраняет ссылку на родительский элемент и может использовать ее для более эффективного запроса дочерних элементов и для перестройки дерева на случай, если кто-то его испортит.