Postgres物化路径-使用ltree有什么好处？

Question

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

MP（django-treebeard）的docs实现：

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

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

3. 路径字段已被索引（带有标准b树索引）：

   物化路径方法在数据库中大量使用LIKE，并使用WHERE path LIKE'002003％'之类的子句。如果您认为LIKE太慢，那是对的，但是在这种情况下，路径字段已在数据库中建立索引，并且所有不以％字符开头的LIKE子句都将使用索引。这就是使物化路径方法如此快速的原因。

get_ancestors（link）的实现：

匹配具有包含当前路径子集的路径的节点（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（link）的实现：

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

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

此方法的潜在缺点：

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

Postgres包含ltree扩展名，它提供了自定义GiST索引（docs）。

我不清楚ltree比django-treebeard的实现有哪些优势。 article认为只有ltree可以回答get_ancestors问题，但是如前所述，弄清楚节点的祖先（或后代）是微不足道的。

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

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

其他链接

What are the options for storing hierarchical data in a relational database?

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

Answer 1

TL; DR使用物化路径索引无法完成针对多个后代节点的可重用标签，复杂的搜索模式和祖先搜索。

---

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

首先，仅当您不重用节点描述中的任何标签时，您的问题才有意义。如果是的话，l树实际上是两者中的唯一选择。但是物化路径实现通常不需要它，因此我们将其放在一边。

一个明显的区别是l树为您提供的搜索类型的灵活性。考虑以下示例（来自您问题中链接的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树一样有效。与article linked above相反，使用b树搜索同一个祖先的所有后代非常可行。如果您的索引准备正确，则查询格式WHERE path LIKE 'A.%'是SARGable的（我必须用varchar_pattern_ops显式标记我的路径索引才能使之工作）。

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