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

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

The django-treebeard实施MP（docs https://django-treebeard.readthedocs.io/en/latest/mp_tree.html):

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

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

3. 路径字段已建立索引（使用标准 B 树索引）：

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

实施get_ancestors (link https://github.com/django-treebeard/django-treebeard/blob/8042ee939cb45394909237da447f8925e3cc6aa3/treebeard/mp_tree.py#L1052):

将节点与包含当前路径子集的路径（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 https://github.com/django-treebeard/django-treebeard/blob/8042ee939cb45394909237da447f8925e3cc6aa3/treebeard/mp_tree.py#L958):

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

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

这种方法的潜在缺点：

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

Postgres 包括ltree提供自定义扩展GiST https://en.wikipedia.org/wiki/GiST index (docs https://www.postgresql.org/docs/current/ltree.html).

不太清楚有什么好处ltree提供超过django-treebeard的实施。这article http://patshaughnessy.net/2017/12/15/looking-inside-postgres-at-a-gist-index认为只有ltree可以回答get_ancestors问题，但如前所述，找出节点的祖先（或后代）是微不足道的。

[顺便说一句，我发现了这个 Djangoltree库 - https://github.com/mariocesar/django-ltree]。

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

附加链接

在关系数据库中存储分层数据有哪些选项？ https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database

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

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

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

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

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

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

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

• parent
• children
• 后人
• 根节点
• 叶节点

物化路径与 l 树一样有效。与此相反上面链接的文章 http://patshaughnessy.net/2017/12/15/looking-inside-postgres-at-a-gist-index，使用 B 树搜索共同祖先的所有后代是非常可行的。查询格式WHERE path LIKE 'A.%'如果您的索引已正确准备，则可SARGable（我必须使用以下命令显式标记我的路径索引）varchar_pattern_ops使其发挥作用）。

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