postgresql - Postgres 实体化路径 - 使用 ltree 有什么好处？

Question

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

MP ( docs ) 的 django-treebeard 实现:

路径的每一步都是固定长度，以保持一致的性能。

每个节点都包含 depth 和 numchild 字段(以最小的写入成本快速读取)。

对路径字段进行索引(使用标准的 b 树索引):

The materialized path approach makes heavy use of LIKE in your database, with clauses like WHERE path LIKE '002003%'. If you think that LIKE is too slow, you’re right, but in this case the path field is indexed in the database, and all LIKE clauses that don’t start with a % character will use the index. This is what makes the materialized path approach so fast.

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 ) 的实现:

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

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

这种方法的潜在缺点:

深度嵌套的层次结构将导致路径过长，这会损害读取性能。

移动一个节点需要更新所有后代的路径。

Postgres 包含 ltree 扩展，它提供了一个自定义的 GiST 索引( docs )。

我不清楚 ltree 比 django-treebeard 的实现提供哪些好处。这个 article 认为只有 ltree 可以回答 get_ancestors 问题，但如前所述，找出节点的祖先(或后代)是微不足道的。

[顺便说一句，如果找到了这个 Django ltree 库 - o​​jit_a 。

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

附加链接

https://github.com/mariocesar/django-ltree]

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

Answer 1

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 是唯一的选择。

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

父

child

的后代

根节点

叶节点

物化路径与 l-tree 一样有效。与 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-tree 将在这一点上获胜。