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

所以,亚当斯知道它的全名是威廉姆斯布莱克亚当斯,因为它有1.2.1路径,指向1第一级节点 - 威廉 - 指向1.22级节点 - 布莱克 - 和1.2.13级节点 - 亚当斯.

邻接列表表示通过保持到某些相邻节点的链接来存储树.例如,您可以存储谁是父母,谁是下一个兄弟.

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实际上使用了嵌套集和邻接列表的混合,因为它还保留了与父节点的链接,并且可以使用它来更有效地查询子节点,并在遇到某人搞砸的情况下重建树.