使用sql連接的高效廣度優先搜索

我正在處理二叉樹。使用sql連接的高效廣度優先搜索

因此，我在我的數據庫中有一個數據庫表，其中每個節點都是父節點，最多可以連接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

所以不是這樣做的效率很低 - 每個節點有一個DB調用 - 我是想一想，我如何生成一個所有父節點少於兩個的節點列表，然後沿樹遍歷，爲每個級別使用一個數據庫調用來獲取該級別上所有節點的列表，然後簡單地比較兩個列表。如果兩個列表中都有匹配的ID，我發現一個節點下有一個可用的位置。

這裏有一個圖：

問題是，我幾乎一無所知的SQL查詢。我的猜測是，這可以通過桌面上的某種自我加入完成。

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]子句。 Byt第一個我認爲是我正在努力的人。

如果您有任何事情可以指點或幫助您提供，我會非常感激。

來源

2017-06-04 Legit Stack

這是這個ecto？哪個數據庫引擎？ PostgreSQL的？這些比「join」，「self-join」更重要。 – trincot

@trincot它是ecto，是的，它是postgresql –

SQL是一種聲明性語言，您對使用的方法或操作順序沒有真正的影響。但是*可能*遞歸查詢將以你想要的分層方式建立查詢結果。生成一個'level'表達式，對它進行排序，並且一旦找到沒有孩子的第一個元組，就停止查詢似乎是可行的。 – wildplasser

您可以添加列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。

來源

2017-06-04 19:50:51 Tometzky

使用sql連接的高效廣度優先搜索

回答

相關問題