基于邻接表示的动态路径枚举的预序截线
嵌套集来自:
Konchog https://stackoverflow.com/a/42781302/895245
约翰尼·布坎南https://stackoverflow.com/a/194031/895245
是我见过的唯一有效的遍历方式，但代价是更新速度较慢。这可能是大多数人想要预订的。
来自https://stackoverflow.com/a/192462/895245的闭包表很有趣，但我不知道如何强制提前:MySQL闭包表分层数据库-如何以正确的顺序拉出信息
主要是为了好玩，这里有一个递归计算1.3.2.5的方法。前缀，并在最后根据它们进行排序，仅基于父ID/子索引表示。
好处:
更新只需要更新每个兄弟节点的索引
缺点:
N ^2内存使用量对于超深树来说是最坏的情况。这可能是相当严重的，这就是为什么我说这种方法可能主要只是为了好玩。但也许在某些超高更新的情况下，有人会想要使用它?谁知道
递归查询，所以读的效率比嵌套集要低
创建并填充表:
CREATE TABLE "ParentIndexTree" (
"id" INTEGER PRIMARY KEY,
"parentId" INTEGER,
"childIndex" INTEGER NOT NULL,
"value" INTEGER NOT NULL,
"name" TEXT NOT NULL,
FOREIGN KEY ("parentId") REFERENCES "ParentIndexTree"(id)
)
;
INSERT INTO "ParentIndexTree" VALUES
(0, NULL, 0, 1, 'one' ),
(1, 0, 0, 2, 'two' ),
(2, 0, 1, 3, 'three'),
(3, 1, 0, 4, 'four' ),
(4, 1, 1, 5, 'five' )
;
代表树:
1
/ \
2 3
/ \
4 5
然后，对于像PostgreSQL这样的数组DBMS (https://www.postgresql.org/docs/14/arrays.html):
WITH RECURSIVE "TreeSearch" (
"id",
"parentId",
"childIndex",
"value",
"name",
"prefix"
) AS (
SELECT
"id",
"parentId",
"childIndex",
"value",
"name",
array[0]
FROM "ParentIndexTree"
WHERE "parentId" IS NULL
UNION ALL
SELECT
"child"."id",
"child"."parentId",
"child"."childIndex",
"child"."value",
"child"."name",
array_append("parent"."prefix", "child"."childIndex")
FROM "ParentIndexTree" AS "child"
JOIN "TreeSearch" AS "parent"
ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;
这将创建动态的表单前缀:
1 -> 0
2 -> 0, 0
3 -> 0, 1
4 -> 0, 0, 0
5 -> 0, 0, 1
然后PostgreSQL按字母顺序排序:
1 -> 0
2 -> 0, 0
4 -> 0, 0, 0
5 -> 0, 0, 1
3 -> 0, 1
这就是我们想要的预购结果。
对于像SQLite这样没有数组的DBMS，可以通过使用固定宽度的整数字符串来编码前缀。二进制是理想的，但我不知道怎么做，所以十六进制可以工作。当然，这意味着你必须选择一个最大深度，以适应所选字节的数量，例如下面我选择6，允许每个节点最多16^6个子节点。
WITH RECURSIVE "TreeSearch" (
"id",
"parentId",
"childIndex",
"value",
"name",
"prefix"
) AS (
SELECT
"id",
"parentId",
"childIndex",
"value",
"name",
'000000'
FROM "ParentIndexTree"
WHERE "parentId" IS NULL
UNION ALL
SELECT
"child"."id",
"child"."parentId",
"child"."childIndex",
"child"."value",
"child"."name",
"parent"."prefix" || printf('%06x', "child"."childIndex")
FROM "ParentIndexTree" AS "child"
JOIN "TreeSearch" AS "parent"
ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;
一些嵌套的集合注释
在看了其他嵌套的答案后，这里有几个点让我有点困惑。
Jonny Buchanan展示了他的嵌套设置:
__________________________________________________________________________
| Root 1 |
| ________________________________ ________________________________ |
| | Child 1.1 | | Child 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14
| |________________________________| |________________________________| |
|__________________________________________________________________________|
这让我想知道为什么不使用更简单的外观:
__________________________________________________________________________
| Root 1 |
| ________________________________ _______________________________ |
| | Child 1.1 | | Child 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________| 4___________| | 5 6___________| 7___________| | |
| |________________________________| |_______________________________| |
|_________________________________________________________________________|
每个端点都没有额外的数字。
但当我真正尝试实现它时，我注意到很难/不可能实现这样的更新查询，除非我有Konchog所使用的父级信息。问题是，当树被移动时，在某种情况下很难/不可能区分兄弟姐妹和父母，我需要这来决定是否要在缩小差距时减少右手边。
左/大小vs左/右:你可以在数据库中以任何一种方式存储它，但我认为左/右可以更有效，因为你可以用多列索引(左，右)索引DB，然后可以用来加速祖先查询，这是类型:
left < curLeft AND right > curLeft
在Ubuntu 22.04, PostgreSQL 14.5, SQLite 3.34.0上测试。
