Django 树 mustache AL、NS、MP 之间有什么区别

Question

我正在尝试制作一个模型来对某些对象进行分类。

我已经尝试使用 django-mptt 轻松检索相关类别，现在我正在搜索不同的解决方案以找到最佳的解决方案。

我无法找出物化路径、邻接列表和嵌套集之间的主要区别。维基百科没有给我一个简短的答案，我所知道的是 mptt 可能是 Nested Set...

谁能用几句话向我解释一下？

Answer 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

所以，Adams 知道它的全名是 Wiliam Blake Adams，因为它有 1.2.1 路径，指向第一层的 1 节点 — William —第 2 层的 1.2 节点 - Blake - 和第 3 层的 1.2.1 节点 - Adams。

邻接表是指通过保留某些相邻节点的链接来存储树。例如，您可以存储谁是 parent ，谁是下一个 sibling 。

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

请注意，如果我们不需要保持节点的子节点有序，那么它可以像仅存储父节点一样简单。现在 Adams 可以递归地获取他所有的祖先直到 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

所以，现在 Adams 可以通过查询谁的左下值和右值更高来找到它的祖先，并按左值对它们进行排序。

每种模型都有其优点和缺点。选择使用哪一种实际上取决于您的应用程序、您正在使用的数据库以及您最常执行的操作类型。你可以找到一个很好的对比here .

比较中提到了第四种模型，该模型不是很常见(除了我自己的实现之外，我不知道任何其他实现)并且非常复杂，很难用几句话解释:通过矩阵编码的嵌套间隔。

当您在嵌套集中插入新节点时，您必须重新枚举遍历中位于该节点之前的每个节点。嵌套间隔背后的想法是，任意两个整数之间存在无限多个有理数，因此您可以将新节点存储为其前一个和下一个节点的一部分。存储和查询分数可能很麻烦，这导致了矩阵编码技术的出现，它将这些分数转换为 2x2 矩阵，并且大多数运算可以通过一些乍一看并不明显但非常高效的矩阵代数来完成。

Treebeard 对物化路径、嵌套集和邻接列表中的每一个都有非常简单的实现，没有冗余。 django-mptt 实际上使用了嵌套集和邻接列表的混合，因为它还保留了到父级的链接，并且可以使用它来更有效地查询子级，并重建树，以防它被某人弄乱。