使用 sql 连接的高效广度优先搜索

Question

我正在处理二叉树。

所以我的数据库中有一个数据库 table，其中每个节点都是最多 2 个其他节点的父节点。我有一个计划可以有效地找到最顶层的节点（在给定节点下），该节点是少于 2 个其他节点的父节点。换句话说，我正在寻找最开放的位置来放置一个新节点。所以我将其实现为广度优先搜索。但是我为每个节点调用数据库的方式效率低下。我基本上是沿着树向下，在每个级别上生成一个运行节点列表，并检查每个节点是否是其他两个节点的父节点。

这是一张图表：

这里是代码，如果你想看的话：

  # breadth-first search
  def build_and_return_parent_id(breadth_list) do
        [ {node_id} | tail ] = breadth_list

        child_list = fetch_children_id(node_id)

        bc_list = tail ++ child_list

        case length(child_list) do
          x when x > 2 ->


            # recursion
            build_and_return_parent_id(bc_list)

          2 ->

            # recursion
            build_and_return_parent_id(bc_list)

          _ -> node_id
        end
  end

  def fetch_children_id(id) do
    Repo.all( from n in Node,
              where: n.parent_id == ^id,
              order_by: [asc: n.inserted_at],
              select: {n.id})
  end
end

因此，与其这样做效率低下——每个节点一个数据库调用——我在想，我如何生成一个包含少于两个父节点的所有节点的列表，然后沿着树向下移动，以供每个级别使用一个数据库调用来获取该级别上所有节点的列表，然后简单地比较这两个列表。如果两个列表中都有匹配的 ID，我发现一个节点下有一个可用位置。

这是一张图表：

问题是我对 sql 查询几乎一无所知。我的猜测是，这可以通过 table 上的某种自连接来完成。

node_id   |  parent_id
----------------------
1         |  nil
2         |  1
3         |  1
4         |  2
5         |  2
6         |  3
7         |  4
8         |  5
9         |  6
10        |  3

所以不管怎样，我确定这个方法是否有效，以前有人用过，但我似乎找不到任何关于 sql 查询类型的信息，这些查询将用于生成开放列表或级别列表。

现在我想第二个查询很简单。因为我们有一个开放列表，所以我们可以只使用 where-in-[list] 子句。第一个我认为是我正在努力解决的问题。

如果您有什么可以指点我或提供帮助，我将不胜感激。

Answer 1

您可以添加列 depth 和 child_count 并创建索引：

create index nodes_depth_1child_idx on nodes(depth) where child_count=1;

然后搜索应该基本上是即时的：

select node_id from nodes where child_count=1 order by depth limit 1;

您还应该创建触发器来维护这些值。这会稍微减慢插入操作的速度，因为插入操作必须读取父节点 depth 并更新父节点 child_count.

使用 sql 连接的高效广度优先搜索

efficient breadth first search using sql joins

sql

postgresql

breadth-first-search

binary-search-tree

ecto