使用邻接表示法进行即时路径枚举的预订遍历
来自以下嵌套集：
这是我看到的唯一有效的遍历方式，代价是更新速度较慢。这可能是大多数人想要的预订方式。
https://dev59.com/BnVC5IYBdhLWcg3ww0Hr#192462中的闭包表很有趣，但我不知道如何在其中强制执行预订：MySQL Closure Table hierarchical database - How to pull information out in the correct order
仅供娱乐，这里提供了一种基于父ID/子索引表示法，在最后计算1.3.2.5.前缀并按其排序的递归方法。
优点：
缺点：
- 对于超深的树，最坏情况下需要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（
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使用的父级信息。问题在于，在树被移动时，很难/不可能区分兄弟和父母，我需要这个来决定在关闭间隙时是否要减少右侧。
左/大小与左/右：您可以将其存储在数据库中的任何一种方式，但我认为左/右可以更有效，因为您可以使用多列索引（左、右）对DB进行索引，然后用于加速祖先查询，这些查询的类型为：
left < curLeft AND right > curLeft
在Ubuntu 22.04、PostgreSQL 14.5和SQLite 3.34.0上进行了测试。
