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

Question

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

MP (文档)的django-treebeard实现：

1. 为了保持一致的性能，路径的每一步都是固定的长度。
2. 每个节点都包含depth和numchild字段(以最小的代价快速读取)。
3. path字段被索引(使用标准的b-树索引)： 物化路径方法在数据库中大量使用LIKE，其中的子句如WHERE路径(如“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索引(文档)。

我不清楚ltree为django-treebeard的实现提供了哪些好处。这个文章认为只有ltree才能回答get_ancestors问题，但正如前面所演示的那样，找出节点的祖先(或后代)是微不足道的。

图书馆- [https://github.com/mariocesar/django-ltree] ]。

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

附加链接

在关系数据库中存储分层数据的选项是什么？

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

Answer 1

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

对于那些对血淋淋的细节感兴趣的人。

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

一个明显的区别是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

第一个查询显然可以通过物化路径实现。最后一个也是可以实现的，您可以将查询调整为同级查找。然而，在中间情况下，单次索引查找是无法直接实现的。您要么将其分解为两个查询(所有后代+所有祖先)，要么求助于表扫描。

然后有非常复杂的查询，比如这个查询(也来自docs)：

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

在这里，物化路径索引将是无用的，需要进行完整的表扫描才能处理这个问题。如果您想要将其作为SARGable查询来执行，L-树是唯一的选择。

但是对于标准的层次化操作，可以找到以下任何一种：

• 父级
• 孩子们
• 后人
• 根节点
• 叶节

物化路径将和l树一样工作。与上文链接的文章相反，使用b树搜索共同祖先的所有后代是非常可行的。查询格式WHERE path LIKE 'A.%'是SARGable，前提是您的索引准备得很好(我必须使用varchar_pattern_ops显式标记路径索引，才能使其正常工作)。

此列表中缺少的是为后代查找所有祖先。不幸的是，查询格式WHERE 'A.B.C.D' LIKE path || '.%'不会使用索引。一些库实现的一个解决方法是解析路径中的祖先节点，并直接查询它们：WHERE id IN ('A', 'B', 'C')。但是，只有当您针对已经检索到路径的特定节点的祖先时，这才会有效。L树会赢这场比赛的。