6

Materialized Path 是一种在 SQL 中表示层次结构的方法。每个节点都包含路径本身及其所有祖先 ( grandparent/parent/self)。

django-treebeardMP（文档）的实现：

  1. 路径的每一步都是固定长度，以实现一致的性能。

  2. 每个节点都包含depth和numchild字段（以最低的写入成本快速读取）。

  3. 路径字段被索引（使用标准的 b 树索引）：

    物化路径方法在数据库中大量使用 LIKE，其中包含 WHERE path LIKE '002003%' 之类的子句。如果你认为 LIKE 太慢了，你是对的，但是这种情况下 path 字段在数据库中是索引的，所有不以 % 字符开头的 LIKE 子句都会使用索引。这就是使物化路径方法如此快速的原因。

实施get_ancestors（链接）：

将节点与包含当前路径子集的路径匹配（steplen是步长的固定长度）。

paths = [
    self.path[0:pos]
    for pos in range(0, len(self.path), self.steplen)[1:]
]
return get_result_class(self.__class__).objects.filter(
    path__in=paths).order_by('depth')

实施get_descendants（链接）：

匹配深度大于自身的节点和以当前路径开始的路径。

return cls.objects.filter(
    path__startswith=parent.path,
    depth__gte=parent.depth
).order_by(
    'path'
)

这种方法的潜在缺点：

  1. 深度嵌套的层次结构会导致路径过长，这会损害读取性能。
  2. 移动一个节点需要更新所有后代的路径。

Postgres 包含ltree提供自定义GiST索引 ( docs ) 的扩展。

我不清楚哪些好处ltree提供了 overdjango-treebeard的实施。本文认为只能ltree回答这个get_ancestors问题，但如前所述，找出节点的祖先（或后代）是微不足道的。

[顺便说一句，如果找到这个 Djangoltree库 - https://github.com/mariocesar/django-ltree]。

两种方法都使用索引（django-treebeard使用 b-tree，ltree使用自定义 GiST）。我有兴趣了解ltreeGiST 的实现，以及为什么对于这个特定用例（物化路径），它可能是比标准 b 树更有效的索引。

附加链接

在关系数据库中存储分层数据的选项有哪些？

https://news.ycombinator.com/item?id=709970

4

1 回答 1

6

TL;DR可重用标签、复杂搜索模式和针对多个后代节点（或尚未检索到路径的单个节点）的祖先搜索无法使用物化路径索引来完成。

对于那些对血腥细节感兴趣的人......

首先，只有当您没有在节点描述中重用任何标签时，您的问题才有意义。如果你是，l-tree 真的是两者中唯一的选择。但是物化路径实现通常不需要这个，所以让我们把它放在一边。

一个明显的区别在于 l-tree 为您提供的搜索类型的灵活性。考虑这些示例（来自ltree您问题中链接的文档）：

foo         Match the exact label path foo
*.foo.*     Match any label path containing the label foo
*.foo       Match any label path whose last label is foo

第一个查询显然可以通过物化路径实现。最后一个也是可以实现的，您可以将查询调整为同级查找。但是，中间情况不能通过单个索引查找直接实现。您要么必须将其分解为两个查询（所有后代 + 所有祖先），要么诉诸表扫描。

然后有像这样的非常复杂的查询（也来自文档）：

Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain

物化路径索引在这里是没有用的，需要进行全表扫描来处理这个问题。如果您想将其作为 SARGable 查询执行，则 l-tree 是唯一的选择。

但是对于标准的分层操作，找到以下任何一个：

  • 父母
  • 孩子们
  • 子孙
  • 根节点
  • 叶节点

物化路径与 l-tree 一样有效。与上面链接的文章相反，使用 b-tree 搜索一个共同祖先的所有后代是非常可行的。查询格式WHERE path LIKE 'A.%'是 SARGable，前提是您的索引准备妥当（我必须明确标记我的路径索引varchar_pattern_ops才能使其正常工作）。

此列表中缺少的是为后代找到所有祖先。不幸的是，查询格式WHERE 'A.B.C.D' LIKE path || '.%'不会使用索引。一些库实现的一种解决方法是从路径中解析出祖先节点，并直接查询它们WHERE id IN ('A', 'B', 'C')：但是，这仅在您针对已检索其路径的特定节点的祖先时才有效。l-tree 将在这一点上获胜。

于 2019-12-02T16:47:24.897 回答