Ответ 1
Это проще объяснить примерами, чем несколькими словами. Рассмотрим дерево образцов, сохранив имена:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Материализованный путь означает, что каждый node сохраняет свой полный путь в кодировке. Например, вы можете сохранить свой индекс, используя точку в качестве разделителя
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
Итак, Адамс знает, что его полное имя Wiliam Blake Adams, потому что у него есть путь 1.2.1, указывающий на 1 node на первом уровне - William - на 1.2 node на уровне 2 - Блейк - и 1.2.1 node на уровне 3 - Адамс.
Adjacency List означает, что дерево хранится, сохраняя ссылку на некоторые соседние узлы. Например, вы можете сохранить, кто является родителем, и кто следующий брат.
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
Обратите внимание, что это может быть так просто, как просто хранить родительский элемент, если нам не нужно сохранять дочерние элементы node упорядоченными. Теперь Адамс может вернуть всех своих предков до нуля, чтобы найти свое полное имя.
Вложенные наборы означают, что вы храните каждый node с некоторым индексом, обычно с левым и правым значением, назначенным каждому, когда вы пересекаете дерево в порядке 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
Итак, теперь Адамс может найти своих предков, запросив, кто имеет нижний левый И более высокое правильное значение, и отсортировать их по левому значению.
Каждая модель имеет свои сильные и слабые стороны. Выбор того, какой из них использовать, зависит от вашего приложения, используемой базы данных и того, какие операции вы будете делать чаще всего. Вы можете найти хорошее сравнение здесь.
В сравнении упоминается четвертая модель, которая не очень распространена (я не знаю ни одной другой реализации, кроме моей) и очень сложно объяснить в нескольких словах: Вложенный интервал с помощью Matrix Encoding.
Когда вы вставляете новый node во вложенный набор, вы должны повторно перечислять всех, кто впереди, в обход. Идея вложенных интервалов заключается в том, что существует бесконечное число рациональных чисел между любыми двумя целыми числами, поэтому вы можете сохранить новый node как часть его предыдущего и следующего узлов. Хранение и запрос фракций может быть проблематичным, и это приводит к методу матричной кодировки, который преобразует эти фракции в матрице 2x2, и большинство операций может быть выполнено с помощью некоторой матричной алгебры, которая не очевидна с первого взгляда, но может быть очень эффективной.
Treebeard имеет очень простые реализации каждого из материалов Materialized Path, Nested Sets и Adjacency Lists без избыточности. django-mptt на самом деле использует сочетание списков вложенных наборов и списков соответствия, поскольку он также поддерживает связь с родителем и может использовать его как для более эффективного запроса детей, так и для восстановления дерева в случае, если кто-то его перепутает.