SQL結合を使用した効率的な最初の検索

Question

私はバイナリツリーを扱っています。

私はデータベースに、各ノードが最大2つの他のノードの親であるデータベーステーブルを持っています。私は効率的に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 

ので、代わりのように非効率的に行う - ノードあたり1デシベルコールを - 私がいた：あなたがそれを見たい場合は

そしてここでは、コードです考えてみると、親が2つ未満のすべてのノードのリストを作成し、ツリーを下に移動すると、各レベルは1つの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クエリの種類上の任意の情報を見つけるように見えることはできませんリスト。

私は2番目のクエリがかなりシンプルだと思います。オープンリストがあるのでwhere-in [list]句を使うことができます。私が思う最初のものは、私が苦労しているものです。

私に何かを教えてもらえますか、それとも私が本当に感謝してくれますか？あなたが列depthとchild_countを追加してインデックスを作成することができます

Answer 1

：

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を更新する必要があるため、挿入操作がわずかに遅くなります。