SQL 中的树的深度排序

引言

本文概述了一种特定的技术，用于从数据库中的树获取深度优先排序，如果树是使用修改的邻接表模型跟踪的。如果您还不熟悉在数据库中存储树，我将参考两种常见的结构和解释如何使用它们的优秀文章。

背景

修改后的邻接表模型是在 SQL 中保存层次结构数据或树的常用结构。它在 Eugene Lepekhin 的文章“SQL 数据库中的树”中得到了很好的呈现。我不会详细介绍这个结构。我们先来确定它的基本要素。有一个基本表，它具有层次关系，即父子关系，然后还有一个单独的表，它保存所有父子关系以及它们之间的距离。这里所有的关系意味着，它不仅有父节点的子节点，还有孙子节点和曾孙节点等等。这些表可以像这样。 [我将使用与 Lepekhin 相同的命名。如果您还不熟悉此内容，您可以并且应该参考他的文章了解详细信息。]

这里有一棵树，供本文的其余部分参考

这些表将包含示例树的值，如下所示

您必须对层次结构数据进行的主要选择是检索一个子树。SQL 代码大致如下所示

Select n.* From Node n, Tree t Where n.NodeId=t.ChildId and t.ParentId=B

问题

现在，我面临的问题是如何对在该子树中检索到的数据进行排序。

对于一棵树，有两种标准的方式来排序节点：广度优先和深度优先。广度优先意味着您希望先横向遍历再纵向遍历。在这里，只需在 Tree 表中的 Level 列上排序即可。对我们的示例进行广度优先排序将返回：A, B, E, C, D, F。

以下是执行此操作的代码

Select n.* From Node n, Tree t Where n.NodeId=t.ChildId and t.ParentId=A Order By t.Level

真正的问题在于您想要进行深度优先排序。深度优先排序意味着树的检索方式是先到每个分支的底部，然后再转到下一个分支。使用我们的示例，深度优先排序将返回：A, B, C, D, F, E。

解决方案

我发现的解决方案是在基本表中使用路径枚举列并按其排序。此列跟踪从根节点到当前节点的路径。这也是一种众所周知的技术，可以在 Joe Celko 的文章“层次结构 SQL”中找到。它本身是一种在数据库中跟踪层次结构数据的方式，可以作为修改后的邻接表模式的替代方案。但是，您不会希望以这种方式使用它，因为字符串的模式匹配非常慢。路径枚举的机制可以在触发器中处理，就像邻接表模型一样，我将留给读者参考 Celko 的文章。

我们的新 Node 表现在看起来像这样

使用我们上面示例树，这是 Node 的值（取决于您对路径格式的一些实现选择）

有了路径枚举列，它就可以用于深度优先排序树的内容。对选择的唯一补充是按 NodePath 排序，并且检索到的数据集是深度优先排序的。在此字符串上排序将确保每个级别的每个分支都按 ID 的值顺序呈现。

Select n.* From Node n, Tree t Where n.NodeId=t.ChildId and t.ParentId=A 
                                                     Order By n.NodePath

我不知道这两种层次结构数据模型像这样一起使用，但它很容易解决这个问题。此技术在您不介意由于触发器导致插入和更新时稍微增加开销以获得选择速度的情况下非常有用。