django - Django treebeard AL、NS、MP 有什么区别

Question

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

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

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

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

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——指向第二层的1.2节点——Blake——和第三层的节点1.2.1——Adams。

邻接表意味着通过保持到一些相邻节点的链接来存储树。例如，您可以存储谁是父母，谁是下一个兄弟姐妹。

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 可以通过查询谁的左下角和右下角的值来找到它的祖先，并按左值排序。

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

比较提到了第四个模型，它不是很常见（我不知道除了我自己的任何其他实现）并且用几句话来解释非常复杂：通过矩阵编码的嵌套间隔。

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

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