SQL内のツリーの深さ

Question

tree_nodeというテーブルがあり、それにはidというプライマリキーがあり、parent_idというNULL可能な列があり、テーブルにツリー構造（またはフォレスト）が埋め込まれていると仮定すると、どのようにしてツリー/フォレスト内のノードをSQLで効率的に使用する方法

Answer 1

再帰機能が必要です。再帰クエリ使用し、これは次のようになります。

WITH RECURSIVE node_ancestors(node_id, parent_id) AS (
     SELECT id, id FROM tree_node WHERE id IN (1, 2, 3) 
    UNION ALL 
     SELECT na.node_id, tree_node.parent_id 
      FROM node_ancestors AS na, tree_node 
      WHERE tree_node.id = na.parent_id AND tree_node.parent_id IS NOT NULL 
) 
SELECT node_id, COUNT(parent_id) AS depth FROM node_ancestors GROUP BY node_id; 

他のオプションは、ストアド・プロシージャで再帰を行うアプリケーションでの再帰を行うと、再帰の量を制限し、加入の多くを使用しています。

Answer 2

深度が無制限の場合、問題は再帰的であり、実際には簡単で効率的な解決策はありません。スキーマの制御があり、この種のデータに定期的にアクセスする必要がある場合、ネストしたセットとしてテーブルをリファクタリングすることができます。ネストされたセットとして、各要素の左と右の包含境界があります。これは、およそ、基本的な条件を備えた単一のクエリ内のノードの深さを計算できるようになる：木を処理する

select count(*) from tree_node 
    where left < myLeft 
    and right > myRight 

Answer 3

一般的な方法は、KEYと親の通常の列に加えて、あなたも持っている、ですパスを構成するノードのキーを含む文字列値を含むPATH型の列（ルートからノード自体まで）、キーの一部ではない文字で区切られた列自体。

例を挙げましょう：

KEY  PARENT   PATH 
1   -    *1* 
    2  1    *1*2* 
    3  1    *1*3* 
    4  3    *1*3*4* 
    5  1    *1*5* 
    6  5    *1*5*6* 

。これは主に、部門階層または類似のように、あまり変化していない木が使用されています。

このような文字列は、複数のルール（マルチキー、複数値フィールドなど）を無効にするように見えるため、正規化理論に厳密に従っているわけではありませんが、多くのシナリオではあなたが求めているもの

あなたの場合、問題のノードのTREE値を取得するだけで、最も簡単なものに応じて、区切り文字の数を数えたり、置換関数でそれらを削除したり、長さ

ここで彼らの深さで、あなたのノードの上のリストを与えるために、SQLです：

select KEY, PARENT, LEN(PATH)-LEN(REPLACE(PATH, '*', ''))-1 as DEPTH 
from NODES 

（注）このアプローチは、再帰的SQLのデータベースエンジンにより、特別な構文やサポートを必要とし、非常に適していないこと索引付けにもうまくいきます。