用例子来解释比用几句话更容易解释。考虑示例树,存储名称:
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 知道它的全名是 William Blake Adams,因为它有1.2.1
路径,指向1
第一级节点 - William - 到1.2
2 级节点 — Blake — 以及1.2.1
第 3 级节点 — 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 可以通过查询谁的左下值和右值更高来找到它的祖先,并按左值对它们进行排序。
每个模型都有其优点和缺点。选择使用哪一种实际上取决于您的应用程序、您正在使用的数据库以及您最常执行的操作类型。你可以找到一个很好的比较here http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals-vs-adjacency-list-comparison/.
比较中提到了第四种模型,该模型不是很常见(除了我自己的实现之外,我不知道任何其他实现)并且非常复杂,用几句话来解释:通过矩阵编码的嵌套间隔。
当您在嵌套集中插入新节点时,您必须重新枚举遍历中位于该节点之前的每个节点。嵌套间隔背后的想法是,任意两个整数之间存在无限多个有理数,因此您可以将新节点存储为其前一个和下一个节点的一部分。存储和查询分数可能很麻烦,这导致了矩阵编码技术的出现,它将这些分数转换为 2x2 矩阵,并且大多数运算可以通过一些乍一看并不明显但非常有效的矩阵代数来完成。
Treebeard 对物化路径、嵌套集和邻接列表中的每一种都有非常简单的实现,没有冗余。 django-mptt 实际上混合使用了嵌套集和邻接列表,因为它还保留了到父级的链接,并且可以使用它来更有效地查询子级,并重建树,以防它被某人弄乱。