2

次のようなテーブルがあるとします。

CREATE TABLE IF NOT EXISTS `node_list` (
    `nid` int(11) NOT NULL AUTO_INCREMENT,
    `parent` int(11)
        COMMENT \'Node`s parent (nid).\',
    PRIMARY KEY (`nid`)
)

特定のノード ID について、そのすべての子孫の数を取得したいと考えています。でも：

SELECT COUNT(*) FROM `node_list` WHERE `parent`=?

直接の子の数のみを返します。forループを混乱させずにこれを行う良い方法はどのようなものでしょうか?

4

4 に答える 4

1

これらの制約を考えると、方法はありません。そのような場合、すべてのツリーを取得して「ヒル」クライアント側を構築するか、特定のケースで最もパフォーマンスが高いものは何でも、再帰クエリを実行します。

固定数の階層レベルを持つという追加の制約により、複数の JOIN でこれを行うことができます。

一般的なケースでは、これらの制約を克服できるように、いくつかの構造変更があります。実際には、「これは私のテーブル構造です」という制約を緩和し、フィールドを追加できるようにします。

たとえば、ノード構造をleft_id値で補足し、深さ優先でツリーにアクセスしたときにすべてのノード ID が順番に並んでいることを確認できます。

1 --- 2 -+- 3 -+- 4
         |     |
         |     +- 5
         +- 6 --- 7

この場合、ノード 3 は値「5」を格納し、ノード 6 は値「7」を格納し、ノード 2 も値「7」を格納します。各ノードは、その子の LeftID とそれ自身の ID の間の最大値を LeftID に格納します。

そのため、子のないノードの LeftID はその ID と同じです。ノード 1 の LeftID は 7 になります。これは、6 から取得した LeftID が 2 であるためです。

この状況では、シーケンスに穴がなければ、ノードのカウントは簡単です。ノードのすべての子孫は、ID が開始ノードの ID とその LeftID の間にあるノードです。リーフは、ID と等しい LeftID を持つことによって識別されます。

したがって、「ノード ID 17 から派生するすべてのリーフ」は次のようになります。

SELECT child.* FROM table AS parent JOIN table AS child ON (child.id > parent.id AND child.id <= parent.leftid ) /* 子孫/ WHERE child.id = child.leftid /リーフ/ AND 親.id = 17; /親は17歳

この構造は、プルーニングとブランチを実行できるようにしたい場合、維持するのが面倒です。なぜなら、プルーニングのポイントからブランチのポイントまでの間のすべてのノードと、移動したノードの番号を付け直す必要があるからです。

カウントのみに関心がある場合の別の可能性は、子カウンターを保持することです。これは、反復的に更新し、すべての葉を選択してそれらのカウンターを 0 に設定することで維持できます (LEFT JOIN を通じて葉を識別します)。次に、非 NULL カウンターを持つ子を持つ NULL カウンターを持つすべての親が、それらのカウンターをSUM()子のカウンターのCOUNT()と子自体の に更新します。すべてのノードのカウンターが NULL でないため、更新された行の数がゼロになるまで続行します。剪定と分岐の後、すべてのカウンターを NULL に設定して繰り返すだけです。

この最後の方法では、階層レベルごとに反射結合が必要になります。

于 2012-10-04T20:42:21.437 に答える
0

もう少し掘って…

With Nodes As 
( 
Select s.nid, s.parent
From nodelist s
Where s.nid = @ParentID 
Union All 
Select s2.nid, s2.parent
From nodelist s2
    Join Nodes
        On Nodes.nid = s2.parent 
) 
Select Count(*)
From Nodes
于 2012-10-04T20:03:42.700 に答える
-1

層の最大数が既知の階層の場合、結合のカスケードを使用して単一のクエリを実行して、レコード数を見つけることができます。階層の数が 3 つまたは 4 つを超える場合、これはうまくいかないかもしれませんが、うまくいくはずです。

select count(*)
from node_list n1
outer join node_list n2 on n2.parent = n1.nid
outer join node_list n3 on n3.parent = n2.nid
outer join node_list n4 on n4.parent = n3.nid

...など、必要な数のレベルについて。ただし、あまり多くしないようにしてください。そうしないと、パフォーマンスが低下する可能性があります。

現実の世界では、ほとんどの階層システムは実際にはその深さがかなり制限されています。理論的には無制限であっても。たとえば、サイト メニューでは構造のレベルを無制限にすることができますが、3 つまたは 4 つを超えると使いにくくなります。ネストに制限を課すかどうかはあなた次第ですが、それにより作業が簡単になる場合があります。

ただし、どこまで深くなるかわからない無限の階層がある場合、または上記のクエリが遅すぎる場合は、ループが必要になります。そのループが MySQL ストアド プロシージャにあるか、PHP にあるかは重要ではありません。いずれかの方法でループが必要になります。forただし、心配しているループの混乱である必要はありません。

私は再帰的なPHP関数でそれを行います。多分このようなもの：

function countDescendants($db, $nid) {
    $total = 0;
    $query = "select nid from Nodes where parent = ".(int)$nid;
    $res = $db->query($query);
    foreach($res as $data) {
        $total += countDescendants($db, $data['nid']);
    }
    $total += $res->num_rows;
    return $total;
}

次に、それを呼び出して、1 行のコードで答えを得ることができます。

$number_of_descendants = countDescendants($starting_nid);

mysqliかなり単純な再帰関数 ( DB に使用していて、関数に渡すために接続が既にソートされていると仮定しました)。

確かに、非常に巨大な階層がある場合や、何度もクエリを実行している場合は、少し遅くなる可能性がありますが、私が示したこの基本的な例を改善することで速度を上げる方法があります。たとえば、準備済みステートメント クエリを使用して、同じステートメントに異なる nid 値を入力するだけで済みます。これにより、DB 作業の大部分を節約できます。しかし、小さな階層で単純に使用する場合は、上記のコードで問題ありません。

これらの手法の 1 つの大きな落とし穴は、ノード構造にループがある場合です。つまり、親 ID として独自の子孫の 1 つを持つノードです。このシナリオでは、上記の PHP コードで無限ループが発生し、ネストされた結合 SQL クエリの場合にレコード数がひどく偏る原因になります。どちらの場合でも、システムでこのような状況が発生する可能性がある場合は、それに対するコードを作成する必要があります。しかし、それは物事を複雑にするので、ここでは触れません。

それが役立つことを願っています。

（注：上記のコードはテストされていません：実行せずに回答に直接入力しました。タイプミスがある場合はお詫びします）

于 2012-10-04T20:40:54.827 に答える