如何用Python遍历存储在SQL数据库中的树？

Question

我有一个根树，存储在SQL数据库中，使用的是物化路径（为每一行存储路径字符串）。

有没有什么好的方法可以访问每个节点，而不需要每次都从根节点开始？物化路径适合我的方法吗？

Harry
├── Jane
│   ├── Mark
│   └── Diane
│       ├── Mary
│       └── George
│           └── Jill
└── Bill

我希望代码首先从Harry开始，然后访问Jane、Diane、George和Jill。要访问Mary，就需要从Jill回到上一层，然后访问Mary。Mary没有孩子，我们已经访问了这一层的每个节点（George和Mary），所以我们再回到上一层去访问Mark。这一层没有其他孩子了，所以我们再回到Jane这一层，但这一层也没有其他节点了，所以我们再回去。最后，这一层只有Bill，我们访问他。当所有节点都被访问完后，我们就完成了。

我也考虑过把树的每一层存储在不同的表中，并在另一个表中存储对这些表的引用，但这似乎有点低效，因为我需要存储当前遍历在哪一层，并且还要处理这些数据。

Level_0_table:
Harry,
Bill

Level_1_table:
Jane

Level_2_table:
Mark,
Diane

Level_3_table:
Mary,
George

Level_4_table:
Jill

Answer 1

我不太确定“物化路径”这种数据结构是否是最好的选择，因为它看起来有点冗余。也许你可以考虑使用邻接列表（也就是为每个条目存储 id 和 parent_id）或者嵌套集合（存储 id、left 和 right 的邻居ID）。这里有一个关于这两种结构的不错概述。你想要做的是在你的树上执行一个深度优先搜索（DFS）。不久前，这个问题在这个讨论串中被提到过，所以你可能会觉得有用。通过SQL查询来执行DFS是可行的，但具体实现可能会依赖于你使用的数据库软件。无论如何，你可以通过使用一个栈来存储你还需要访问的元素的ID来实现DFS。每次访问后，你将节点的子节点推入栈中，然后继续处理下一个弹出的元素。这里有一个不错的例子。